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