Own digits power sum: Difference between revisions
m (→{{header|Pascal}}: Nearly 1s for all up to 19 digits. Creating combination with included update of used digits.) |
|||
Line 677: | Line 677: | ||
<lang pascal>program PowerOwnDigits; |
<lang pascal>program PowerOwnDigits; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
//{$R+,O+} |
|||
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON} |
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON} |
||
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} |
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} |
||
Line 690: | Line 689: | ||
tDgtCnt = 0..MaxDgtCount; |
tDgtCnt = 0..MaxDgtCount; |
||
tValues = 0..MaxDgtVal; |
tValues = 0..MaxDgtVal; |
||
tUsedDigits = array[0.. |
tUsedDigits = array[0..23] of Int8; |
||
tpUsedDigits = ^tUsedDigits; |
|||
tPower = array[tValues] of Uint64; |
tPower = array[tValues] of Uint64; |
||
var |
var |
||
PowerDgt: array[tDgtCnt] of tPower; |
PowerDgt: array[tDgtCnt] of tPower; |
||
Min10Pot : array[tDgtCnt] of Uint64; |
Min10Pot : array[tDgtCnt] of Uint64; |
||
gblUD : tUsedDigits; |
|||
CombIdx: array of Int8; |
CombIdx: array of Int8; |
||
Numbers : array of Uint64; |
Numbers : array of Uint64; |
||
rec_cnt : NativeInt; |
rec_cnt : NativeInt; |
||
procedure OutUD(const UD:tUsedDigits); |
|||
var |
|||
i : integer; |
|||
begin |
|||
For i in tValues do |
|||
write(UD[i]:3); |
|||
writeln; |
|||
For i := 0 to MaxDgtCount do |
|||
write(CombIdx[i]:3); |
|||
writeln; |
|||
end; |
|||
function InitCombIdx(ElemCount: Byte): pbyte; |
function InitCombIdx(ElemCount: Byte): pbyte; |
||
Line 704: | Line 717: | ||
Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0); |
Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0); |
||
Result := @CombIdx[0]; |
Result := @CombIdx[0]; |
||
Fillchar(gblUD[0], sizeOf(gblUD[0]) * (ElemCount + 1), #0); |
|||
gblUD[0]:= 1; |
|||
end; |
end; |
||
Line 728: | Line 743: | ||
end; |
end; |
||
result := InitCombIdx(ElemCount); |
result := InitCombIdx(ElemCount); |
||
gblUD[0]:= 1; |
|||
end; |
end; |
||
function GetPowerSum(minpot:nativeInt;digits:pbyte;var UD :tUsedDigits):NativeInt; |
|||
function NextCombWithRep(pComb: pByte; MaxVal, ElemCount: UInt32): boolean; |
|||
var |
|||
i,dgt: NativeInt; |
|||
begin |
|||
i := -1; |
|||
repeat |
|||
i += 1; |
|||
dgt := pComb[i]; |
|||
if dgt < MaxVal then |
|||
break; |
|||
until i > ElemCount; |
|||
Result := i >= ElemCount; |
|||
dgt +=1; |
|||
repeat |
|||
pComb[i] := dgt; |
|||
i -= 1; |
|||
until i < 0; |
|||
end; |
|||
function GetPowerSum(minpot:nativeInt;digits:pbyte;var UD_tmp :tUsedDigits):NativeInt; |
|||
var |
var |
||
pPower : pUint64; |
pPower : pUint64; |
||
Line 757: | Line 753: | ||
begin |
begin |
||
r := Min10Pot[minpot]; |
r := Min10Pot[minpot]; |
||
pPower := @PowerDgt[minpot,0]; |
|||
dgt := minpot; |
dgt := minpot; |
||
res := 0; |
res := 0; |
||
pPower := @PowerDgt[minpot,0]; |
|||
repeat |
repeat |
||
dgt -=1; |
dgt -=1; |
||
Line 765: | Line 761: | ||
until dgt=0; |
until dgt=0; |
||
//check if res within bounds of digitCnt |
//check if res within bounds of digitCnt |
||
result := 0; |
|||
if (res<r) or (res>r*MAXBASE) then EXIT(1); |
|||
if (res<r) or (res>r*MAXBASE) then EXIT; |
|||
//convert res into digits |
//convert res into digits |
||
result := minPot; |
|||
repeat |
repeat |
||
dec(result); |
|||
r := res DIV MAXBASE; |
r := res DIV MAXBASE; |
||
result+=1; |
|||
UD[res-r*MAXBASE]-= 1; |
|||
res := r; |
res := r; |
||
until r = 0; |
until r = 0; |
||
end; |
end; |
||
Line 783: | Line 780: | ||
i: nativeInt; |
i: nativeInt; |
||
begin |
begin |
||
UD := gblUD; |
|||
If GetPowerSum(minpot,digits,UD) <>0 then |
|||
Begin |
|||
UD[digits[i]]+=1; |
|||
//don't check 0 |
|||
i := GetPowerSum(minpot,digits,UD); |
|||
i := 1; |
|||
repeat |
|||
If UD[i] <> 0 then |
|||
Break; |
|||
if i = 0 then |
|||
begin |
|||
while (i <= minPot) and (UD[digits[i]] = 0) do |
|||
i +=1; |
i +=1; |
||
until i > MaxDgtVal; |
|||
if i > MaxDgtVal then |
|||
begin |
begin |
||
res := 0; |
res := 0; |
||
for i := minpot-1 downto 0 do |
for i := minpot-1 downto 0 do |
||
res += PowerDgt[minpot,digits[i]]; |
res += PowerDgt[minpot,digits[i]]; |
||
setlength(Numbers, Length(Numbers) + 1); |
setlength(Numbers, Length(Numbers) + 1); |
||
Numbers[high(Numbers)] := res; |
Numbers[high(Numbers)] := res; |
||
Line 807: | Line 802: | ||
end; |
end; |
||
function NextCombWithRep(pComb: pByte;pUD :tpUsedDigits;MaxVal, ElemCount: UInt32): boolean; |
|||
var |
|||
i,dgt: NativeInt; |
|||
begin |
|||
i := -1; |
|||
repeat |
|||
i += 1; |
|||
dgt := pComb[i]; |
|||
if dgt < MaxVal then |
|||
break; |
|||
dec(pUD^[dgt]); |
|||
until i >= ElemCount; |
|||
Result := i >= ElemCount; |
|||
if i = 0 then |
|||
begin |
|||
dec(pUD^[dgt]); |
|||
dgt +=1; |
|||
pComb[i] := dgt; |
|||
inc(pUD^[dgt]); |
|||
end |
|||
else |
|||
begin |
|||
//decrements digit 0 too.This is false, but not checked. |
|||
dec(pUD^[dgt]); |
|||
dgt +=1; |
|||
pUD^[dgt]:=i+1; |
|||
repeat |
|||
pComb[i] := dgt; |
|||
i -= 1; |
|||
until i < 0; |
|||
end; |
|||
end; |
|||
var |
var |
||
digits : pByte; |
digits : pByte; |
||
Line 824: | Line 852: | ||
calcnum(i,digits); |
calcnum(i,digits); |
||
inc(rec_cnt); |
inc(rec_cnt); |
||
until NextCombWithRep(digits,MaxDgtVal,i); |
until NextCombWithRep(digits,@gblUD,MaxDgtVal,i); |
||
writeln(i:3,' digits with ',Length(Numbers):3,' solutions in ',GetTickCount64-T0:5,' ms'); |
|||
end; |
end; |
||
T0 := GetTickCount64-T0; |
T0 := GetTickCount64-T0; |
||
writeln(rec_cnt,' recursions |
writeln(rec_cnt,' recursions'); |
||
writeln('found ',length(Numbers)); |
|||
//sort |
//sort |
||
for i := 0 to High(Numbers) - 1 do |
for i := 0 to High(Numbers) - 1 do |
||
Line 843: | Line 871: | ||
for i := 0 to High(Numbers) do |
for i := 0 to High(Numbers) do |
||
writeln(i+1:3,Numbers[i]:20); |
writeln(i+1:3,Numbers[i]:20); |
||
setlength(Numbers, 0); |
|||
setlength(CombIdx,0); |
|||
{$IFDEF WINDOWS} |
{$IFDEF WINDOWS} |
||
readln; |
readln; |
||
{$ENDIF} |
{$ENDIF} |
||
end. |
|||
setlength(Numbers, 0); |
|||
</lang> |
|||
setlength(CombIdx,0); |
|||
end.</lang> |
|||
{{out}} |
{{out}} |
||
<pre style="height:180px"> |
<pre style="height:180px"> |
||
TIO.RUN |
|||
TIO.RUN //18 digits 13123099 recursions in runtime 911.00 ms found 37 |
|||
2 digits with 0 solutions in 0 ms |
|||
20029999 recursions in runtime 1434.00 ms |
|||
3 digits with 4 solutions in 0 ms |
|||
found 41 |
|||
4 digits with 7 solutions in 0 ms |
|||
5 digits with 10 solutions in 0 ms |
|||
6 digits with 11 solutions in 0 ms |
|||
7 digits with 15 solutions in 0 ms |
|||
8 digits with 18 solutions in 1 ms |
|||
9 digits with 22 solutions in 3 ms |
|||
10 digits with 23 solutions in 6 ms |
|||
11 digits with 31 solutions in 13 ms |
|||
12 digits with 31 solutions in 25 ms |
|||
13 digits with 31 solutions in 46 ms |
|||
14 digits with 32 solutions in 82 ms |
|||
15 digits with 32 solutions in 141 ms |
|||
16 digits with 34 solutions in 238 ms |
|||
17 digits with 37 solutions in 395 ms |
|||
18 digits with 37 solutions in 644 ms |
|||
19 digits with 41 solutions in 1028 ms |
|||
20029999 recursions |
|||
1 153 |
1 153 |
||
2 370 |
2 370 |
Revision as of 13:14, 5 November 2021
- Description
For the purposes of this task, an own digits power sum is a decimal integer which is N digits long and is equal to the sum of its individual digits raised to the power N.
- Example
The three digit integer 153 is an own digits power sum because 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.
- Task
Find and show here all own digits power sums for N = 3 to N = 8 inclusive.
Optionally, do the same for N = 9 which may take a while for interpreted languages.
ALGOL 68
Non-recursive, generates the possible combinations ands the own digits power sums in reverse order, without duplication.
Uses ideas from various solutions on this page, particularly the observation that the own digits power sum is independent of the order of the digits. Uses the minimum possible highest digit for the number of digits (width) and maximum number of zeros for the width to avoid some combinations. This trys 73 359 combinations.
<lang algol68>BEGIN
# counts of used digits, check is a copy used to check the number is an own digit power sum # [ 0 : 9 ]INT used, check; FOR i FROM 0 TO 9 DO check[ i ] := 0 OD; [ 1 : 9, 1 : 9 ]LONG INT power; # table of digit powers # FOR i TO 9 DO power[ 1, i ] := i OD; FOR j FROM 2 TO 9 DO FOR i TO 9 DO power[ j, i ] := power[ j - 1, i ] * i OD OD; # find the lowest possible first digit for each digit combination # # this is the roughly the low3est n where P*n^p > 10^p # [ 1 : 9 ]INT lowest digit; lowest digit[ 2 ] := lowest digit[ 1 ] := -1; LONG INT p10 := 100; FOR i FROM 3 TO 9 DO FOR p FROM 2 TO 9 WHILE LONG INT np = power[ i, p ] * i; np < p10 DO lowest digit[ i ] := p OD; p10 *:= 10 OD; # find the maximum number of zeros possible for each width and max digit # [ 1 : 9, 1 : 9 ]INT max zeros; FOR i TO 9 DO FOR j TO 9 DO max zeros[ i, j ] := 0 OD OD; p10 := 1000; FOR w FROM 3 TO 9 DO FOR d FROM lowest digit[ w ] TO 9 DO INT nz := 9; WHILE IF nz < 0 THEN FALSE ELSE LONG INT np := power[ w, d ] * nz; np > p10 FI DO nz -:= 1 OD; max zeros[ w, d ] := IF nz > w THEN 0 ELSE w - nz FI OD; p10 *:= 10 OD; # find the numbers, works backeards through the possible combinations of # # digits, starting from all 9s # [ 1 : 100 ]LONG INT numbers; # will hold the own digit power sum numbers # INT n count := 0; # count of the own digit power sums # INT try count := 0; # count of digit combinations tried # [ 1 : 9 ]INT digits; # the latest digit combination to try # FOR d TO 9 DO digits[ d ] := 9 OD; FOR d FROM 0 TO 8 DO used[ d ] := 0 OD; used[ 9 ] := 9; INT width := 9; # number of digits # INT last := width; # final digit position # p10 := 100 000 000; # min value for a width digit power sum # WHILE width > 2 DO try count +:= 1; LONG INT dps := 0; # construct the digit power sum # check := used; FOR i TO 9 DO IF used[ i ] /= 0 THEN dps +:= used[ i ] * power[ width, i ] FI OD; # reduce the count of each digit by the number of times it appear in the digit power sum # LONG INT n := dps; WHILE check[ SHORTEN ( n MOD 10 ) ] -:= 1; # reduce the count of this digit # ( n OVERAB 10 ) > 0 DO SKIP OD; BOOL reduce width := dps <= p10; IF NOT reduce width THEN # dps is not less than the minimum possible width number # # check there are no non-zero check counts left and so result is # # equal to its digit power sum # INT z count := 0; FOR i FROM 0 TO 9 WHILE check[ i ] = 0 DO z count +:= 1 OD; IF z count = 10 THEN numbers[ n count +:= 1 ] := dps FI; # prepare the next digit combination: reduce the last digit # used[ digits[ last ] ] -:= 1; digits[ last ] -:= 1; IF digits[ last ] = 0 THEN # the last digit is now zero - check this number of zeros is possible # IF used[ 0 ] >= max zeros[ width, digits[ 1 ] ] THEN # have exceeded the maximum number of zeros for the first digit in this width # digits[ last ] := -1 FI FI; IF digits[ last ] >= 0 THEN # still processing the last digit # used[ digits[ last ] ] +:= 1 ELSE # last digit is now -1, start processing the previous digit # INT prev := last; WHILE IF ( prev -:= 1 ) < 1 THEN # processed all digits # FALSE ELSE # have another digit # used[ digits[ prev ] ] -:= 1; digits[ prev ] -:= 1; digits[ prev ] < 0 FI DO SKIP OD; IF prev > 0 THEN # still some digits to process # IF prev = 1 THEN IF digits[ 1 ] <= lowest digit[ width ] THEN # just finished the lowest possible maximum digit for this width # prev := 0 FI FI; IF prev /= 0 THEN # OK to try a lower digit # used[ digits[ prev ] ] +:= 1; FOR i FROM prev + 1 TO width DO digits[ i ] := digits[ prev ]; used[ digits[ prev ] ] +:= 1 OD FI FI; IF prev <= 0 THEN # processed all the digits for this width # reduce width := TRUE FI FI FI; IF reduce width THEN # reduce the number of digits # width := last -:= 1; IF last > 0 THEN # iniialise for fewer digits # FOR d TO last DO digits[ d ] := 9 OD; FOR d FROM last + 1 TO 9 DO digits[ d ] := -1 OD; FOR d FROM 0 TO 9 DO used[ d ] := 0 OD; used[ 9 ] := last; p10 OVERAB 10 FI FI OD; # show the own digit power sums # print( ( "Own digits power sums for N = 3 to 9 inclusive:", newline ) ); FOR i FROM n count BY -1 TO LWB numbers DO print( ( whole( numbers[ i ], 0 ), newline ) ) OD; print( ( "Considered ", whole( try count, 0 ), " digit combinations" ) )
END</lang>
- Output:
Own digits power sums for N = 3 to 9 inclusive: 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153 Considered 73359 digit combinations
C
Iterative (slow)
Takes about 1.9 seconds to run (GCC 9.3.0 -O3).
<lang c>#include <stdio.h>
- include <math.h>
- define MAX_DIGITS 9
int digits[MAX_DIGITS];
void getDigits(int i) {
int ix = 0; while (i > 0) { digits[ix++] = i % 10; i /= 10; }
}
int main() {
int n, d, i, max, lastDigit, sum, dp; int powers[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}; printf("Own digits power sums for N = 3 to 9 inclusive:\n"); for (n = 3; n < 10; ++n) { for (d = 2; d < 10; ++d) powers[d] *= d; i = (int)pow(10, n-1); max = i * 10; lastDigit = 0; while (i < max) { if (!lastDigit) { getDigits(i); sum = 0; for (d = 0; d < n; ++d) { dp = digits[d]; sum += powers[dp]; } } else if (lastDigit == 1) { sum++; } else { sum += powers[lastDigit] - powers[lastDigit-1]; } if (sum == i) { printf("%d\n", i); if (lastDigit == 0) printf("%d\n", i + 1); i += 10 - lastDigit; lastDigit = 0; } else if (sum > i) { i += 10 - lastDigit; lastDigit = 0; } else if (lastDigit < 9) { i++; lastDigit++; } else { i++; lastDigit = 0; } } } return 0;
}</lang>
- Output:
Same as Wren example.
Recursive (very fast)
Down now to 14ms. <lang c>#include <stdio.h>
- include <string.h>
- define MAX_BASE 10
typedef unsigned long long ulong;
int usedDigits[MAX_BASE]; ulong powerDgt[MAX_BASE][MAX_BASE]; ulong numbers[60]; int nCount = 0;
void initPowerDgt() {
int i, j; powerDgt[0][0] = 0; for (i = 1; i < MAX_BASE; ++i) powerDgt[0][i] = 1; for (j = 1; j < MAX_BASE; ++j) { for (i = 0; i < MAX_BASE; ++i) { powerDgt[j][i] = powerDgt[j-1][i] * i; } }
}
ulong calcNum(int depth, int used[MAX_BASE]) {
int i; ulong result = 0, r, n; if (depth < 3) return 0; for (i = 1; i < MAX_BASE; ++i) { if (used[i] > 0) result += powerDgt[depth][i] * used[i]; } if (result == 0) return 0; n = result; do { r = n / MAX_BASE; used[n-r*MAX_BASE]--; n = r; depth--; } while (r); if (depth) return 0; i = 1; while (i < MAX_BASE && used[i] == 0) i++; if (i >= MAX_BASE) numbers[nCount++] = result; return 0;
}
void nextDigit(int dgt, int depth) {
int i, used[MAX_BASE]; if (depth < MAX_BASE-1) { for (i = dgt; i < MAX_BASE; ++i) { usedDigits[dgt]++; nextDigit(i, depth+1); usedDigits[dgt]--; } } if (dgt == 0) dgt = 1; for (i = dgt; i < MAX_BASE; ++i) { usedDigits[i]++; memcpy(used, usedDigits, sizeof(usedDigits)); calcNum(depth, used); usedDigits[i]--; }
}
int main() {
int i, j; ulong t; initPowerDgt(); nextDigit(0, 0);
// sort and remove duplicates for (i = 0; i < nCount-1; ++i) { for (j = i + 1; j < nCount; ++j) { if (numbers[j] < numbers[i]) { t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; } } } j = 0; for (i = 1; i < nCount; ++i) { if (numbers[i] != numbers[j]) { j++; t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; } } printf("Own digits power sums for N = 3 to 9 inclusive:\n"); for (i = 0; i <= j; ++i) printf("%lld\n", numbers[i]); return 0;
}</lang>
- Output:
Same as before.
F#
<lang fsharp> // Own digits power sum. Nigel Galloway: October 2th., 2021 let fN g=let N=[|for n in 0..9->pown n g|] in let rec fN g=function n when n<10->N.[n]+g |n->fN(N.[n%10]+g)(n/10) in (fun g->fN 0 g) {3..9}|>Seq.iter(fun g->let fN=fN g in printf $"%d{g} digit are:"; {pown 10 (g-1)..(pown 10 g)-1}|>Seq.iter(fun g->if g=fN g then printf $" %d{g}"); printfn "") </lang>
- Output:
3 digit are: 153 370 371 407 4 digit are: 1634 8208 9474 5 digit are: 54748 92727 93084 6 digit are: 548834 7 digit are: 1741725 4210818 9800817 9926315 8 digit are: 24678050 24678051 88593477 9 digit are: 146511208 472335975 534494836 912985153
FreeBASIC
<lang freebasic> dim as uinteger N, curr, temp, dig, sum
for N = 3 to 9
for curr = 10^(N-1) to 10^N-1 sum = 0 temp = curr do dig = temp mod 10 temp = temp \ 10 sum += dig ^ N loop until temp = 0 if sum = curr then print curr next curr
next N </lang>
- Output:
As above.
Go
Iterative (slow)
Takes about 16.5 seconds to run including compilation time. <lang go>package main
import (
"fmt" "math" "rcu"
)
func main() {
powers := [10]int{0, 1, 4, 9, 16, 25, 36, 49, 64, 81} fmt.Println("Own digits power sums for N = 3 to 9 inclusive:") for n := 3; n < 10; n++ { for d := 2; d < 10; d++ { powers[d] *= d } i := int(math.Pow(10, float64(n-1))) max := i * 10 lastDigit := 0 sum := 0 var digits []int for i < max { if lastDigit == 0 { digits = rcu.Digits(i, 10) sum = 0 for _, d := range digits { sum += powers[d] } } else if lastDigit == 1 { sum++ } else { sum += powers[lastDigit] - powers[lastDigit-1] } if sum == i { fmt.Println(i) if lastDigit == 0 { fmt.Println(i + 1) } i += 10 - lastDigit lastDigit = 0 } else if sum > i { i += 10 - lastDigit lastDigit = 0 } else if lastDigit < 9 { i++ lastDigit++ } else { i++ lastDigit = 0 } } }
}</lang>
- Output:
Same as Wren example.
Recursive (very fast)
Down to about 128 ms now including compilation time. Actual run time only 8 ms!
<lang go>package main
import "fmt"
const maxBase = 10
var usedDigits = [maxBase]int{} var powerDgt = [maxBase][maxBase]uint64{} var numbers []uint64
func initPowerDgt() {
for i := 1; i < maxBase; i++ { powerDgt[0][i] = 1 } for j := 1; j < maxBase; j++ { for i := 0; i < maxBase; i++ { powerDgt[j][i] = powerDgt[j-1][i] * uint64(i) } }
}
func calcNum(depth int, used [maxBase]int) uint64 {
if depth < 3 { return 0 } result := uint64(0) for i := 1; i < maxBase; i++ { if used[i] > 0 { result += uint64(used[i]) * powerDgt[depth][i] } } if result == 0 { return 0 } n := result for { r := n / maxBase used[n-r*maxBase]-- n = r depth-- if r == 0 { break } } if depth != 0 { return 0 } i := 1 for i < maxBase && used[i] == 0 { i++ } if i >= maxBase { numbers = append(numbers, result) } return 0
}
func nextDigit(dgt, depth int) {
if depth < maxBase-1 { for i := dgt; i < maxBase; i++ { usedDigits[dgt]++ nextDigit(i, depth+1) usedDigits[dgt]-- } } if dgt == 0 { dgt = 1 } for i := dgt; i < maxBase; i++ { usedDigits[i]++ calcNum(depth, usedDigits) usedDigits[i]-- }
}
func main() {
initPowerDgt() nextDigit(0, 0)
// sort and remove duplicates for i := 0; i < len(numbers)-1; i++ { for j := i + 1; j < len(numbers); j++ { if numbers[j] < numbers[i] { numbers[i], numbers[j] = numbers[j], numbers[i] } } } j := 0 for i := 1; i < len(numbers); i++ { if numbers[i] != numbers[j] { j++ numbers[i], numbers[j] = numbers[j], numbers[i] } } numbers = numbers[0 : j+1] fmt.Println("Own digits power sums for N = 3 to 9 inclusive:") for _, n := range numbers { fmt.Println(n) }
}</lang>
- Output:
Same as before.
Haskell
Using a function from the Combinations with Repetitions task: <lang haskell>import Data.List (sort)
OWN DIGITS POWER SUM -----------------
ownDigitsPowerSums :: Int -> [Int] ownDigitsPowerSums n = sort (ns >>= go)
where ns = combsWithRep n [0 .. 9] go xs | digitsMatch m xs = [m] | otherwise = [] where m = foldr ((+) . (^ n)) 0 xs
digitsMatch :: Show a => a -> [Int] -> Bool digitsMatch n ds =
sort ds == sort (digits n)
TEST -------------------------
main :: IO () main = do
putStrLn "N ∈ [3 .. 8]" mapM_ print ([3 .. 8] >>= ownDigitsPowerSums) putStrLn "" putStrLn "N=9" mapM_ print $ ownDigitsPowerSums 9
GENERIC ------------------------
combsWithRep ::
(Eq a) => Int -> [a] -> a
combsWithRep k xs = comb k []
where comb 0 ys = ys comb n [] = comb (pred n) (pure <$> xs) comb n peers = comb (pred n) (peers >>= nextLayer) where nextLayer ys@(h : _) = (: ys) <$> dropWhile (/= h) xs
digits :: Show a => a -> [Int] digits n = (\x -> read [x] :: Int) <$> show n</lang>
- Output:
N ∈ [3 .. 8] 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 N=9 146511208 472335975 534494836 912985153
Julia
<lang julia>function isowndigitspowersum(n::Integer, base=10)
dig = digits(n, base=base) exponent = length(dig) return mapreduce(x -> x^exponent, +, dig) == n
end
for i in 10^2:10^9-1
isowndigitspowersum(i) && println(i)
end
</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Pascal
recursive solution.Just counting the different combination of digits
See Combinations_with_repetitions
<lang pascal>program PowerOwnDigits;
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF} uses
SysUtils;
const
MAXBASE = 10; MaxDgtVal = MAXBASE - 1; MaxDgtCount = 19;
type
tDgtCnt = 0..MaxDgtCount; tValues = 0..MaxDgtVal; tUsedDigits = array[0..23] of Int8; tpUsedDigits = ^tUsedDigits; tPower = array[tValues] of Uint64;
var
PowerDgt: array[tDgtCnt] of tPower; Min10Pot : array[tDgtCnt] of Uint64; gblUD : tUsedDigits; CombIdx: array of Int8; Numbers : array of Uint64; rec_cnt : NativeInt;
procedure OutUD(const UD:tUsedDigits); var i : integer; begin For i in tValues do write(UD[i]:3); writeln; For i := 0 to MaxDgtCount do write(CombIdx[i]:3); writeln; end;
function InitCombIdx(ElemCount: Byte): pbyte; begin setlength(CombIdx, ElemCount + 1); Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0); Result := @CombIdx[0]; Fillchar(gblUD[0], sizeOf(gblUD[0]) * (ElemCount + 1), #0); gblUD[0]:= 1; end;
function Init(ElemCount:byte):pByte; var pP1,Pp2 : pUint64; i, j: Int32; begin Min10Pot[0]:= 0; Min10Pot[1]:= 1; for i := 2 to High(tDgtCnt) do Min10Pot[i]:=Min10Pot[i-1]*MAXBASE;
pP1 := @PowerDgt[low(tDgtCnt)]; for i in tValues do pP1[i] := 1; pP1[0] := 0; for j := low(tDgtCnt) + 1 to High(tDgtCnt) do Begin pP2 := @PowerDgt[j]; for i in tValues do pP2[i] := pP1[i]*i; pP1 := pP2; end; result := InitCombIdx(ElemCount); gblUD[0]:= 1; end;
function GetPowerSum(minpot:nativeInt;digits:pbyte;var UD :tUsedDigits):NativeInt; var pPower : pUint64; res,r : Uint64; dgt :Int32; begin r := Min10Pot[minpot]; dgt := minpot; res := 0; pPower := @PowerDgt[minpot,0]; repeat dgt -=1; res += pPower[digits[dgt]]; until dgt=0; //check if res within bounds of digitCnt result := 0; if (res<r) or (res>r*MAXBASE) then EXIT;
//convert res into digits repeat r := res DIV MAXBASE; result+=1; UD[res-r*MAXBASE]-= 1; res := r; until r = 0;
end;
procedure calcNum(minPot:Int32;digits:pbyte); var UD :tUsedDigits; res: Uint64; i: nativeInt; begin UD := gblUD; If GetPowerSum(minpot,digits,UD) <>0 then Begin //don't check 0 i := 1; repeat If UD[i] <> 0 then Break; i +=1; until i > MaxDgtVal;
if i > MaxDgtVal then begin res := 0; for i := minpot-1 downto 0 do res += PowerDgt[minpot,digits[i]]; setlength(Numbers, Length(Numbers) + 1); Numbers[high(Numbers)] := res; end; end; end;
function NextCombWithRep(pComb: pByte;pUD :tpUsedDigits;MaxVal, ElemCount: UInt32): boolean; var i,dgt: NativeInt; begin i := -1; repeat i += 1; dgt := pComb[i]; if dgt < MaxVal then break; dec(pUD^[dgt]); until i >= ElemCount; Result := i >= ElemCount;
if i = 0 then begin dec(pUD^[dgt]); dgt +=1; pComb[i] := dgt; inc(pUD^[dgt]); end else begin //decrements digit 0 too.This is false, but not checked. dec(pUD^[dgt]); dgt +=1; pUD^[dgt]:=i+1; repeat pComb[i] := dgt; i -= 1; until i < 0; end; end;
var
digits : pByte; T0 : Int64; tmp: Uint64; i, j : Int32;
begin
digits := Init(MaxDgtCount); T0 := GetTickCount64; rec_cnt := 0; // i > 0 For i := 2 to MaxDgtCount do Begin digits := InitCombIdx(MaxDgtCount); repeat calcnum(i,digits); inc(rec_cnt); until NextCombWithRep(digits,@gblUD,MaxDgtVal,i); writeln(i:3,' digits with ',Length(Numbers):3,' solutions in ',GetTickCount64-T0:5,' ms'); end; T0 := GetTickCount64-T0; writeln(rec_cnt,' recursions');
//sort for i := 0 to High(Numbers) - 1 do for j := i + 1 to High(Numbers) do if Numbers[j] < Numbers[i] then begin tmp := Numbers[i]; Numbers[i] := Numbers[j]; Numbers[j] := tmp; end;
setlength(Numbers, j + 1); for i := 0 to High(Numbers) do writeln(i+1:3,Numbers[i]:20); setlength(Numbers, 0); setlength(CombIdx,0); {$IFDEF WINDOWS} readln; {$ENDIF}
end. </lang>
- Output:
TIO.RUN 2 digits with 0 solutions in 0 ms 3 digits with 4 solutions in 0 ms 4 digits with 7 solutions in 0 ms 5 digits with 10 solutions in 0 ms 6 digits with 11 solutions in 0 ms 7 digits with 15 solutions in 0 ms 8 digits with 18 solutions in 1 ms 9 digits with 22 solutions in 3 ms 10 digits with 23 solutions in 6 ms 11 digits with 31 solutions in 13 ms 12 digits with 31 solutions in 25 ms 13 digits with 31 solutions in 46 ms 14 digits with 32 solutions in 82 ms 15 digits with 32 solutions in 141 ms 16 digits with 34 solutions in 238 ms 17 digits with 37 solutions in 395 ms 18 digits with 37 solutions in 644 ms 19 digits with 41 solutions in 1028 ms 20029999 recursions 1 153 2 370 3 371 4 407 5 1634 6 8208 7 9474 8 54748 9 92727 10 93084 11 548834 12 1741725 13 4210818 14 9800817 15 9926315 16 24678050 17 24678051 18 88593477 19 146511208 20 472335975 21 534494836 22 912985153 23 4679307774 24 32164049650 25 32164049651 26 40028394225 27 42678290603 28 44708635679 29 49388550606 30 82693916578 31 94204591914 32 28116440335967 33 4338281769391370 34 4338281769391371 35 21897142587612075 36 35641594208964132 37 35875699062250035 38 1517841543307505039 39 3289582984443187032 40 4498128791164624869 41 4929273885928088826
Perl
Brute Force
Use Parallel::ForkManager
to obtain concurrency, trading some code complexity for less-than-infinite run time. Still very slow.
<lang perl>use strict;
use warnings;
use feature 'say';
use List::Util 'sum';
use Parallel::ForkManager;
my %own_dps; my($lo,$hi) = (3,9); my $cores = 8; # configure to match hardware being used
my $start = 10**($lo-1); my $stop = 10**$hi - 1; my $step = int(1 + ($stop - $start)/ ($cores+1));
my $pm = Parallel::ForkManager->new($cores);
RUN: for my $i ( 0 .. $cores ) {
$pm->run_on_finish ( sub { my ($pid, $exit_code, $ident, $exit_signal, $core_dump, $data_ref) = @_; $own_dps{$ident} = $data_ref; } );
$pm->start($i) and next RUN;
my @values; for my $n ( ($start + $i*$step) .. ($start + ($i+1)*$step) ) { push @values, $n if $n == sum map { $_**length($n) } split , $n; }
$pm->finish(0, \@values)
}
$pm->wait_all_children;
say $_ for sort { $a <=> $b } map { @$_ } values %own_dps;</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Combinatorics
Leverage the fact that all combinations of digits give same DPS. Much faster than brute force, as only non-redundant values tested. <lang perl>use strict; use warnings; use List::Util 'sum'; use Algorithm::Combinatorics qw<combinations_with_repetition>;
my @own_dps; for my $d (3..9) {
my $iter = combinations_with_repetition([0..9], $d); while (my $p = $iter->next) { my $dps = sum map { $_**$d } @$p; next unless $d == length $dps and join(, @$p) == join , sort split , $dps; push @own_dps, $dps; }
}
print join "\n", sort { $a <=> $b } @own_dps;</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Python
Python :: Procedural
slower
<lang python>""" Rosetta code task: Own_digits_power_sum """
def isowndigitspowersum(integer):
""" true if sum of (digits of number raised to number of digits) == number """ digits = [int(c) for c in str(integer)] exponent = len(digits) return sum(x ** exponent for x in digits) == integer
print("Own digits power sums for N = 3 to 9 inclusive:") for i in range(100, 1000000000):
if isowndigitspowersum(i): print(i)
</lang>
- Output:
Same as Wren example. Takes over a half hour to run.
faster
Same output.
<lang python>""" Rosetta code task: Own_digits_power_sum (recursive method)"""
MAX_BASE = 10 POWER_DIGIT = [[1 for _ in range(MAX_BASE)] for _ in range(MAX_BASE)] USED_DIGITS = [0 for _ in range(MAX_BASE)] NUMBERS = []
def calc_num(depth, used):
""" calculate the number at a given recurse depth """ result = 0 if depth < 3: return 0 for i in range(1, MAX_BASE): if used[i] > 0: result += used[i] * POWER_DIGIT[depth][i] if result != 0: num, rnum = result, 1 while rnum != 0: rnum = num // MAX_BASE used[num - rnum * MAX_BASE] -= 1 num = rnum depth -= 1 if depth == 0: i = 1 while i < MAX_BASE and used[i] == 0: i += 1 if i >= MAX_BASE: NUMBERS.append(result) return 0
def next_digit(dgt, depth):
""" get next digit at the given depth """ if depth < MAX_BASE - 1: for i in range(dgt, MAX_BASE): USED_DIGITS[dgt] += 1 next_digit(i, depth + 1) USED_DIGITS[dgt] -= 1
if dgt == 0: dgt = 1 for i in range(dgt, MAX_BASE): USED_DIGITS[i] += 1 calc_num(depth, USED_DIGITS.copy()) USED_DIGITS[i] -= 1
for j in range(1, MAX_BASE):
for k in range(MAX_BASE): POWER_DIGIT[j][k] = POWER_DIGIT[j - 1][k] * k
next_digit(0, 0) print(NUMBERS) NUMBERS = list(set(NUMBERS)) NUMBERS.sort() print('Own digits power sums for N = 3 to 9 inclusive:') for n in NUMBERS:
print(n)</lang>
Python :: Functional
Using a function from the Combinations with Repetitions task: <lang python>Own digit power sums
from itertools import accumulate, chain, islice, repeat from functools import reduce
- ownDigitsPowerSums :: Int -> [Int]
def ownDigitsPowerSums(n):
All own digit power sums of digit length N def go(xs): m = reduce(lambda a, x: a + (x ** n), xs, 0) return [m] if digitsMatch(m)(xs) else []
return concatMap(go)( combinationsWithRepetitions(n)(range(0, 1 + 9)) )
- digitsMatch :: Int -> [Int] -> Bool
def digitsMatch(n):
True if the digits in ds contain exactly the digits of n, in any order. def go(ds): return sorted(ds) == sorted(digits(n)) return go
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Own digit power sums for digit lengths 3..9 print( '\n'.join([ 'N ∈ [3 .. 8]', *map(str, concatMap(ownDigitsPowerSums)( range(3, 1 + 8) )), '\nN=9', *map(str, ownDigitsPowerSums(9)) ]) )
- ----------------------- GENERIC ------------------------
- combinationsWithRepetitions :: Int -> [a] -> [kTuple a]
def combinationsWithRepetitions(k):
Combinations with repetitions. A list of tuples, representing sets of cardinality k, with elements drawn from xs. def f(a, x): def go(ys, xs): return xs + [[x] + y for y in ys] return accumulate(a, go)
def combsBySize(xs): return [ tuple(x) for x in next(islice( reduce( f, xs, chain( [[[]]], islice(repeat([]), k) ) ), k, None )) ] return combsBySize
- concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
A concatenated list over which a function has been mapped. The list monad can be derived by using a function f which wraps its output in a list, (using an empty list to represent computational failure). def go(xs): return list(chain.from_iterable(map(f, xs))) return go
- digits :: Int -> [Int]
def digits(n):
The individual digits of n as integers return [int(c) for c in str(n)]
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
N ∈ [3 .. 8] 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 N=9 146511208 472335975 534494836 912985153
Raku
<lang perl6>(3..8).map: -> $p {
my %pow = (^10).map: { $_ => $_ ** $p }; my $start = 10 ** ($p - 1); my $end = 10 ** $p; my @temp; for ^9 -> $i { ([X] ($i..9) xx $p).race.map: { next unless [<=] $_; my $sum = %pow{$_}.sum; next if $sum < $start; next if $sum > $end; @temp.push: $sum if $sum.comb.Bag eqv $_».Str.Bag } } .say for unique sort @temp;
}</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477
Combinations with repetitions
Using code from Combinations with repetitions task, a version that runs relatively quickly, and scales well. <lang perl6>proto combs_with_rep (UInt, @ ) { * } multi combs_with_rep (0, @ ) { () } multi combs_with_rep ($, []) { () } multi combs_with_rep (1, @a) { map { $_, }, @a } multi combs_with_rep ($n, [$head, *@tail]) {
|combs_with_rep($n - 1, ($head, |@tail)).map({ $head, |@_ }), |combs_with_rep($n, @tail);
}
say sort gather {
for 3..9 -> $d { for combs_with_rep($d, [^10]) -> @digits { .take if $d == .comb.elems and @digits.join == .comb.sort.join given sum @digits X** $d; } }
}</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Ring
<lang ring> see "working..." + nl see "Own digits power sum for N = 3 to 9 inclusive:" + nl
for n = 3 to 9
for curr = pow(10,n-1) to pow(10,n)-1 sum = 0 temp = curr while temp != 0 dig = temp % 10 temp = floor(temp/10) sum += pow(dig,n) end if sum = curr see "" + curr + nl ok next
next
see "done..." + nl </lang>
- Output:
working... Own digits power sum for N = 3 to 9 inclusive: 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153 done...
Ruby
Repeated combinations allow for N=18 in less than a minute. <lang ruby>DIGITS = (0..9).to_a range = (3..18)
res = range.map do |s|
powers = {} DIGITS.each{|n| powers[n] = n**s} DIGITS.repeated_combination(s).filter_map do |combi| sum = powers.values_at(*combi).sum sum if sum.digits.sort == combi.sort end.sort
end
puts "Own digits power sums for N = #{range}:", res</lang>
- Output:
Own digits power sums for 3..18 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153 4679307774 32164049650 32164049651 40028394225 42678290603 44708635679 49388550606 82693916578 94204591914 28116440335967 4338281769391370 4338281769391371 21897142587612075 35641594208964132 35875699062250035
Visual Basic .NET
<lang vbnet>Option Strict On Option Explicit On
Imports System.IO
<summary> Finds n digit numbers N such that the sum of the nth powers of their digits = N </summary> Module OwnDigitsPowerSum
Public Sub Main
' counts of used digits, check is a copy used to check the number is an own digit power sum Dim used(9) As Integer Dim check(9) As Integer Dim power(9, 9) As Long For i As Integer = 0 To 9 check(i) = 0 Next i For i As Integer = 1 To 9 power(1, i) = i Next i For j As Integer = 2 To 9 For i As Integer = 1 To 9 power(j, i) = power(j - 1, i) * i Next i Next j ' find the lowest possible first digit for each digit combination ' this is the roughly the low3est n where P*n^p > 10^p Dim lowestDigit(9) As Integer lowestDigit(1) = -1 lowestDigit(2) = -1 Dim p10 As Long = 100 For i As Integer = 3 To 9 For p As Integer = 2 To 9 Dim np As Long = power(i, p) * i If Not ( np < p10) Then Exit For lowestDigit(i) = p Next p p10 *= 10 Next i ' find the maximum number of zeros possible for each width and max digit Dim maxZeros(9, 9) As Integer For i As Integer = 1 To 9 For j As Integer = 1 To 9 maxZeros(i, j) = 0 Next j Next i p10 = 1000 For w As Integer = 3 To 9 For d As Integer = lowestDigit(w) To 9 Dim nz As Integer = 9 Do If nz < 0 Then Exit Do Else Dim np As Long = power(w, d) * nz IF Not ( np > p10) Then Exit Do End If nz -= 1 Loop maxZeros(w, d) = If(nz > w, 0, w - nz) Next d p10 *= 10 Next w ' find the numbers, works backeards through the possible combinations of ' digits, starting from all 9s Dim numbers(100) As Long ' will hold the own digit power sum numbers Dim nCount As Integer = 0 ' count of the own digit power sums Dim tryCount As Integer = 0 ' count of digit combinations tried Dim digits(9) As Integer ' the latest digit combination to try For d As Integer = 1 To 9 digits(d) = 9 Next d For d As Integer = 0 To 8 used(d) = 0 Next d used(9) = 9 Dim width As Integer = 9 ' number of digits Dim last As Integer = width ' final digit position p10 = 100000000 ' min value for a width digit power sum Do While width > 2 tryCount += 1 Dim dps As Long = 0 ' construct the digit power sum check(0) = used(0) For i As Integer = 1 To 9 check(i) = used(i) If used(i) <> 0 Then dps += used(i) * power(width, i) End If Next i ' reduce the count of each digit by the number of times it appear in the digit power sum Dim n As Long = dps Do check(CInt(n Mod 10)) -= 1 ' reduce the count of this digit n \= 10 Loop Until n <= 0 Dim reduceWidth As Boolean = dps <= p10 If Not reduceWidth Then ' dps is not less than the minimum possible width number ' check there are no non-zero check counts left and so result is ' equal to its digit power sum Dim zCount As Integer = 0 For i As Integer = 0 To 9 If check(i) <> 0 Then Exit For zCount+= 1 Next i If zCount = 10 Then nCount += 1 numbers(nCount) = dps End If ' prepare the next digit combination: reduce the last digit used(digits(last)) -= 1 digits(last) -= 1 If digits(last) = 0 Then ' the last digit is now zero - check this number of zeros is possible If used(0) >= maxZeros(width, digits(1)) Then ' have exceeded the maximum number of zeros for the first digit in this width digits(last) = -1 End If End If If digits(last) >= 0 Then ' still processing the last digit used(digits(last)) += 1 Else ' last digit is now -1, start processing the previous digit Dim prev As Integer = last Do prev -= 1 If prev < 1 Then Exit Do Else used(digits(prev)) -= 1 digits(prev) -= 1 IF digits(prev) >= 0 Then Exit Do End If Loop If prev > 0 Then ' still some digits to process If prev = 1 Then If digits(1) <= lowestDigit(width) Then ' just finished the lowest possible maximum digit for this width prev = 0 End If End If If prev <> 0 Then ' OK to try a lower digit used(digits(prev)) += 1 For i As Integer = prev + 1 To width digits(i) = digits(prev) used(digits(prev)) += 1 Next i End If End If If prev <= 0 Then ' processed all the digits for this width reduceWidth = True End If End If End If If reduceWidth Then ' reduce the number of digits last -= 1 width = last If last > 0 Then ' iniialise for fewer digits For d As Integer = 1 To last digits(d) = 9 Next d For d As Integer = last + 1 To 9 digits(d) = -1 Next d For d As Integer = 0 To 8 used(d) = 0 Next d used(9) = last p10 \= 10 End If End If Loop ' show the own digit power sums Console.Out.WriteLine("Own digits power sums for N = 3 to 9 inclusive:") For i As Integer = nCount To 1 Step -1 Console.Out.WriteLine(numbers(i)) Next i Console.Out.WriteLine("Considered " & tryCount & " digit combinations")
End Sub
End Module</lang>
- Output:
Own digits power sums for N = 3 to 9 inclusive: 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153 Considered 73359 digit combinations
Wren
Iterative (slow)
Includes some simple optimizations to try and quicken up the search. However, getting up to N = 9 still took a little over 4 minutes on my machine. <lang ecmascript>import "./math" for Int
var powers = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] System.print("Own digits power sums for N = 3 to 9 inclusive:") for (n in 3..9) {
for (d in 2..9) powers[d] = powers[d] * d var i = 10.pow(n-1) var max = i * 10 var lastDigit = 0 var sum = 0 var digits = null while (i < max) { if (lastDigit == 0) { digits = Int.digits(i) sum = digits.reduce(0) { |acc, d| acc + powers[d] } } else if (lastDigit == 1) { sum = sum + 1 } else { sum = sum + powers[lastDigit] - powers[lastDigit-1] } if (sum == i) { System.print(i) if (lastDigit == 0) System.print(i + 1) i = i + 10 - lastDigit lastDigit = 0 } else if (sum > i) { i = i + 10 - lastDigit lastDigit = 0 } else if (lastDigit < 9) { i = i + 1 lastDigit = lastDigit + 1 } else { i = i + 1 lastDigit = 0 } }
}</lang>
- Output:
Own digits power sums for N = 3 to 9 inclusive: 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Recursive (very fast)
Astonishing speed-up. Runtime now only 0.5 seconds! <lang ecmascript>import "./seq" for Lst
var maxBase = 10 var usedDigits = List.filled(maxBase, 0) var powerDgt = List.filled(maxBase, null) var numbers = []
var initPowerDgt = Fn.new {
for (i in 0...maxBase) powerDgt[i] = List.filled(maxBase, 0) for (i in 1...maxBase) powerDgt[0][i] = 1 for (j in 1...maxBase) { for (i in 0...maxBase) powerDgt[j][i] = powerDgt[j-1][i] * i }
}
var calcNum = Fn.new { |depth, used|
if (depth < 3) return 0 var result = 0 for (i in 1...maxBase) { if (used[i] > 0) result = result + used[i] * powerDgt[depth][i] } if (result == 0) return 0 var n = result while (true) { var r = (n/maxBase).floor used[n - r*maxBase] = used[n - r*maxBase] - 1 n = r depth = depth - 1 if (r == 0) break } if (depth != 0) return 0 var i = 1 while (i < maxBase && used[i] == 0) i = i + 1 if (i >= maxBase) numbers.add(result) return 0
}
var nextDigit // recursive function nextDigit = Fn.new { |dgt, depth|
if (depth < maxBase-1) { for (i in dgt...maxBase) { usedDigits[dgt] = usedDigits[dgt] + 1 nextDigit.call(i, depth + 1) usedDigits[dgt] = usedDigits[dgt] - 1 } } if (dgt == 0) dgt = 1 for (i in dgt...maxBase) { usedDigits[i] = usedDigits[i] + 1 calcNum.call(depth, usedDigits.toList) usedDigits[i] = usedDigits[i] - 1 }
}
initPowerDgt.call() nextDigit.call(0, 0) numbers = Lst.distinct(numbers) numbers.sort() System.print("Own digits power sums for N = 3 to 9 inclusive:") System.print(numbers.map { |n| n.toString }.join("\n"))</lang>
- Output:
Same as iterative version.