Own digits power sum
- 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.