Own digits power sum: Difference between revisions
(→{{header|Go}}: Added Pascal translation.) |
(→{{header|C}}: Added Pascal translation.) |
||
Line 107: | Line 107: | ||
=={{header|C}}== |
=={{header|C}}== |
||
===Iterative (slow)=== |
|||
Takes about 1.9 seconds to run (GCC 9.3.0 -O3). |
|||
{{trans|Wren}} |
{{trans|Wren}} |
||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
Line 168: | Line 170: | ||
<pre> |
<pre> |
||
Same as Wren example. |
Same as Wren example. |
||
</pre> |
|||
<br> |
|||
===Recursive (very fast)=== |
|||
{{trans|Pascal}} |
|||
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> |
|||
{{out}} |
|||
<pre> |
|||
Same as before. |
|||
</pre> |
</pre> |
||
Revision as of 15:42, 26 October 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
Avoids spliting the digits using division and modulo operations. Includes the Wren optimisation of if the last digit = 0 then the same number but with last digit = 1 is also a suitable number. <lang algol68># find n digit numbers N such that the sum of the nth powers of their digits = N # FOR n FROM 3 TO 9 DO
INT fdigit = 10 - n; [ 1 : 8 ]INT f; FOR i TO 8 DO f[ i ] := IF i = fdigit THEN 1 ELSE 0 FI OD; [ 1 : 8 ]INT t; FOR i TO 8 DO t[ i ] := IF i < fdigit THEN 0 ELSE 9 FI OD; [ 0 : 10 ]INT power; FOR i FROM LWB power TO UPB power DO power[ i ] := i ^ n OD; INT max n = power[ 10 ]; FOR d1 FROM f[ 1 ] TO t[ 1 ] DO INT p1 = power[ d1 ]; INT s1 = d1 * 10; FOR d2 FROM f[ 2 ] TO t[ 2 ] WHILE INT p2 = power[ d2 ] + p1; p2 < max n DO INT s2 = ( s1 + d2 ) * 10; FOR d3 FROM f[ 3 ] TO t[ 3 ] WHILE INT p3 = power[ d3 ] + p2; p3 < max n DO INT s3 = ( s2 + d3 ) * 10; FOR d4 FROM f[ 4 ] TO t[ 4 ] WHILE INT p4 = power[ d4 ] + p3; p4 < max n DO INT s4 = ( s3 + d4 ) * 10; FOR d5 FROM f[ 5 ] TO t[ 5 ] WHILE INT p5 = power[ d5 ] + p4; p5 < max n DO INT s5 = ( s4 + d5 ) * 10; FOR d6 FROM f[ 6 ] TO t[ 6 ] WHILE INT p6 = power[ d6 ] + p5; p6 < max n DO INT s6 = ( s5 + d6 ) * 10; FOR d7 FROM f[ 7 ] TO t[ 7 ] WHILE INT p7 = power[ d7 ] + p6; p7 < max n DO INT s7 = ( s6 + d7 ) * 10; FOR d8 FROM f[ 8 ] TO t[ 8 ] WHILE INT p8 = power[ d8 ] + p7; p8 < max n DO INT s8 = ( s7 + d8 ) * 10; IF s8 = p8 THEN # found a number with 0 as the final digit # # the same number with a final digit of 1 # # must also match the requirements # print( ( whole( s8, 0 ), newline ) ); print( ( whole( s8 + 1, 0 ), newline ) ) FI; FOR d9 FROM 2 TO 9 WHILE INT p9 = power[ d9 ] + p8; p9 < max n DO INT s9 = s8 + d9; IF s9 = p9 THEN print( ( whole( s9, 0 ), newline ) ) FI OD OD OD OD OD OD OD OD OD
OD</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
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.
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.
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 472335975 534494836 912985153
Pascal
recursive solution. <lang pascal>program PowerOwnDigits;
uses
SysUtils;
const
Maxbase = 10; MaxDgtVal = Maxbase - 1;
type
tDgtVal = 0..MaxDgtVal; tUsedDigits = array[tDgtVal] of Int32;
var
UsedDigits: array[tDgtVal] of Int32; PowerDgt: array[tDgtVal, tDgtVal] of Uint64; NUmbers: array of Uint64;
procedure InitPowerDgt; var i, j: tDgtVal; begin PowerDgt[0, 0] := 0; for i := low(tDgtVal) + 1 to High(tDgtVal) do PowerDgt[low(tDgtVal), i] := 1;
for j := low(tDgtVal) + 1 to High(tDgtVal) do for i := low(tDgtVal) to High(tDgtVal) do PowerDgt[j, i] := PowerDgt[j - 1, i] * i; end;
function calcNum(depth: Int32; UsedDigits: tUsedDigits): Uint64; var n, r: Uint64; i: integer; begin Result := 0; if depth < 3 then exit; for i := 1 to High(tDgtVal) do begin if usedDigits[i] > 0 then Result += UsedDigits[i] * PowerDgt[depth, i]; end; if Result = 0 then EXIT;
n := Result; repeat r := n div MAxBase; Dec(UsedDigits[n - r * maxBase]); n := r; Dec(depth); until r = 0;
if depth <> 0 then EXIT(0); i := 1; while (i <= MaxDgtVal) and (UsedDigits[i] = 0) do Inc(i); if i > MaxDgtVal then begin setlength(NUmbers, Length(numbers) + 1); NUmbers[high(numbers)] := Result; end; end;
procedure NextDigit(dgt, depth: tDgtVal); var i: tDgtVal; begin if depth < High(tDgtVal) then begin for i := dgt to High(tDgtVal) do begin Inc(UsedDigits[dgt]); NextDigit(i, depth + 1); Dec(UsedDigits[dgt]); end; end; if dgt = 0 then dgt := 1;
for i := dgt to High(tDgtVal) do begin Inc(UsedDigits[i]); calcNum(depth, UsedDigits); Dec(UsedDigits[i]); end; end;
var
T0 : Int64; min, tmp: Uint64; i, j, max: Int32;
begin
T0 := GetTickCount64; InitPowerDgt; NextDigit(0, 0);
{ 9800817 9800817 24678050 24678050 146511208 146511208 146511208 ... }
// 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; //delete doublettes tmp := numbers[0]; j := 0; for i := 1 to High(numbers) do if numbers[i] <> tmp then begin Inc(j); tmp := numbers[i]; numbers[j] := tmp; end; setlength(numbers, j + 1); T0 := GetTickCount64-T0; writeln(' runtime ',T0,' ms'); for i := 0 to High(numbers) do writeln(numbers[i]); {$IFDEF WINDOWS} readln;
{$ENDIF} end.</lang>
- Output:
TIO.RUN runtime 25 ms 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Perl
Use Parallel::ForkManager
to obtain concurrency, trading some code complexity for less-than-infinite run time.
<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
Python
<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.
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 For n As Integer = 3 To 9 Dim fdigit As Integer = 10 - n Dim f(8) As Integer For i As Integer = 1 To 8 f(i) = If(i = fdigit, 1, 0) Next i Dim t(8) As Integer For i As Integer = 1 To 8 t(i) = If(i < fdigit, 0, 9) Next i Dim power(10) As Integer For i As Integer = 0 To UBound(power) power(i) = Cint(i ^ n) Next i Dim maxN As Integer = power(10) For d1 As Integer = f(1) To t(1) Dim p1 As Integer = power(d1) Dim s1 As Integer = d1 * 10 For d2 As Integer = f(2) To t(2) Dim p2 As Integer = power(d2) + p1 If p2 >= maxN Then Exit For Dim s2 As Integer = (s1 + d2) * 10 For d3 As Integer = f(3) To t(3) Dim p3 As Integer = power(d3) + p2 If p3 >= maxN Then Exit For Dim s3 As Integer = (s2 + d3) * 10 For d4 As Integer = f(4) To t(4) Dim p4 As Integer = power(d4) + p3 If p4 >= maxN Then Exit For Dim s4 As Integer = (s3 + d4) * 10 For d5 As Integer = f(5) To t(5) Dim p5 As Integer = power(d5) + p4 If p5 >= maxN Then Exit For Dim s5 As Integer = (s4 + d5) * 10 For d6 As Integer = f(6) To t(6) Dim p6 As Integer = power(d6) + p5 If p6 >= maxN Then Exit For Dim s6 As Integer = (s5 + d6) * 10 For d7 As Integer = f(7) To t(7) Dim p7 As Integer = power(d7) + p6 If p7 >= maxN Then Exit For Dim s7 As Integer = (s6 + d7) * 10 For d8 As Integer = f(8) To t(8) Dim p8 As Integer = power(d8) + p7 If p8 >= maxN Then Exit For Dim s8 As Integer = (s7 + d8) * 10 If s8 = p8 Then ' found a number with 0 as the final digit ' the same number with a final digit of 1 ' must also match the requirements Console.Out.WriteLine(s8) Console.Out.WriteLine(s8 + 1) End If For d9 As Integer = 2 To 9 Dim p9 As Integer = power(d9) + p8 If p9 >= maxN Then Exit For Dim s9 As Integer = s8 + d9 If s9 = p9 Then Console.Out.WriteLine(s9) End If Next d9 Next d8 Next d7 Next d6 Next d5 Next d4 Next d3 Next d2 Next d1 Next n End Sub
End Module</lang>
- Output:
153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315 24678050 24678051 88593477 146511208 472335975 534494836 912985153
Real time: 7.553 s
User time: 7.044 s
Sys. time: 0.290 s on TIO.RUN using Visual Basic .NET (VBC)
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 var i = 1 while (i < maxBase && used[i] == 0) i = i + 1 if (i >= maxBase) numbers.add(result)
}
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.