Digit fifth powers
- Task
Task desciption is taken from Project Eulet(https://projecteuler.net/problem=30)
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
Even though 15 = 1, it is not expressed as a sum (a sum being the summation of a list of two or more numbers), and is therefore not included.
Ada
<lang Ada>with Ada.Text_Io;
procedure Digit_Fifth_Powers is
subtype Number is Natural range 000_002 .. 999_999;
function Sum_5 (N : Natural) return Natural
is
Pow_5 : constant array (0 .. 9) of Natural :=
(0 => 0**5, 1 => 1**5, 2 => 2**5, 3 => 3**5, 4 => 4**5,
5 => 5**5, 6 => 6**5, 7 => 7**5, 8 => 8**5, 9 => 9**5);
begin
return (if N = 0
then 0
else Pow_5 (N mod 10) + Sum_5 (N / 10));
End Sum_5;
use Ada.Text_Io; Sum : Natural := 0;
begin
for N in Number loop
if N = Sum_5 (N) then
Sum := Sum + N;
Put_Line (Number'Image (N));
end if;
end loop;
Put ("Sum: ");
Put_Line (Natural'Image (Sum));
end Digit_Fifth_Powers;</lang>
- Output:
4150 4151 54748 92727 93084 194979 Sum: 443839
ALGOL 68
As noted by the Julia sample, we need only consider up to 6 digit numbers.
Also note, the digit fifth power sum is independent of the order of the digits.
<lang algol68>BEGIN
[]INT fifth = []INT( 0, 1, 2^5, 3^5, 4^5, 5^5, 6^5, 7^5, 8^5, 9^5 )[ AT 0 ];
# as observed by the Julia sample, 9^5 * 7 has only 6 digits whereas 9^5 * 6 has 6 digits #
# so only up to 6 digit numbers need be considered #
# also, the digit fifth power sum is independent ofg the order of the digits #
[ 1 : 100 ]INT sums; FOR i TO UPB sums DO sums[ i ] := 0 OD;
[ 0 : 9 ]INT used; FOR i FROM 0 TO 9 DO used[ i ] := 0 OD;
INT s count := 0;
FOR d1 FROM 0 TO 9 DO
INT s1 = fifth[ d1 ];
used[ d1 ] +:= 1;
FOR d2 FROM d1 TO 9 DO
INT s2 = fifth[ d2 ] + s1;
used[ d2 ] +:= 1;
FOR d3 FROM d2 TO 9 DO
INT s3 = fifth[ d3 ] + s2;
used[ d3 ] +:= 1;
FOR d4 FROM d3 TO 9 DO
INT s4 = fifth[ d4 ] + s3;
used[ d4 ] +:= 1;
FOR d5 FROM d4 TO 9 DO
INT s5 = fifth[ d5 ] + s4;
used[ d5 ] +:= 1;
FOR d6 FROM d5 TO 9 DO
INT s6 = fifth[ d6 ] + s5;
used[ d6 ] +:= 1;
# s6 is the sum of the fifth powers of the digits #
# check it it is composed of the digits d1 - d6 #
[ 0 : 9 ]INT check; FOR i FROM 0 TO 9 DO check[ i ] := 0 OD;
INT v := s6;
FOR i TO 6 DO
check[ v MOD 10 ] +:= 1;
v OVERAB 10
OD;
BOOL same := TRUE;
FOR i FROM 0 TO 9 WHILE ( same := used[ i ] = check[ i ] ) DO SKIP OD;
IF same THEN
# found a number that is the sum of the fifth powers of its digits #
sums[ s count +:= 1 ] := s6
FI;
used[ d6 ] -:= 1
OD # d6 # ;
used[ d5 ] -:= 1
OD # d5 # ;
used[ d4 ] -:= 1
OD # d4 # ;
used[ d3 ] -:= 1
OD # d3 # ;
used[ d2 ] -:= 1
OD # d2 # ;
used[ d1 ] -:= 1
OD # d1 # ;
# sum and print the sums - ignore 0 and 1 #
INT total := 0;
print( ( "Numbers that are the sums of the fifth powers of their digits: " ) );
FOR i TO s count DO
IF sums[ i ] > 1 THEN
print( ( " ", whole( sums[ i ], 0 ) ) );
total +:= sums[ i ]
FI
OD;
print( ( newline ) );
print( ( "Total: ", whole( total, 0 ), newline ) )
END</lang>
- Output:
Numbers that are the sums of the fifth powers of their digits: 4150 4151 93084 92727 54748 194979 Total: 443839
BASIC
FreeBASIC
<lang freebasic>function dig5( n as uinteger ) as uinteger
dim as string ns = str(n)
dim as uinteger ret = 0
for i as ubyte = 2 to len(ns)
ret += val(mid(ns,i,1))^5
next i
return ret
end function
dim as uinteger i, sum = 0
for i = 0 to 999999
if i = dig5(i) then
print i
sum += i
end if
next i
print "Their sum is ", sum</lang>
- Output:
4150 4151 54748 92727 93084 194979
Their sum is 443839
GW-BASIC
<lang gwbasic>10 SUM! = 0 20 FOR I! = 2 TO 999999! 30 GOSUB 80 40 IF R! = I! THEN SUM! = SUM! + I! : PRINT I! 50 NEXT I! 60 PRINT "Total = ",SUM 70 END 80 N$ = STR$(I) 90 R! = 0 100 FOR J = 1 TO LEN(N$) 110 D = VAL(MID$(N$,J,1)) 120 R! = R! + D*D*D*D*D 130 NEXT J 140 RETURN </lang>
- Output:
4150 4151 54748 92727 93084 194979
Total = 443839
C
<lang c>#include<stdio.h>
- include<stdlib.h>
- include<math.h>
int sum5( int n ) {
if(n<10) return pow(n,5); return pow(n%10,5) + sum5(n/10);
}
int main(void) {
int i, sum = 0;
for(i=2;i<=999999;i++) {
if(i==sum5(i)) {
printf( "%d\n", i );
sum+=i;
}
}
printf( "Total is %d\n", sum );
return 0;
}</lang>
- Output:
41504151 54748 92727 93084 194979
Total is 443839
Factor
Thanks to to the Julia entry for the tip about the upper bound of the search. <lang factor>USING: kernel math math.functions math.ranges math.text.utils math.vectors prettyprint sequences ;
2 9 5 ^ 6 * [a,b] [ dup 1 digit-groups 5 v^n sum = ] filter sum .</lang>
- Output:
443839
Fermat
<lang fermat>Func Sumfp(n) = if n<10 then Return(n^5) else Return((n|10)^5 + Sumfp(n\10)) fi.; sum:=0; for i=2 to 999999 do if i=Sumfp(i) then sum:=sum+i; !!i fi od; !!('The sum was ', sum );</lang>
- Output:
4150 4151 54748 92727 93084 194979
The sum was 443839
Go
<lang go>package main
import (
"fmt" "rcu"
)
func main() {
// cache 5th powers of digits
dp5 := [10]int{0, 1}
for i := 2; i < 10; i++ {
ii := i * i
dp5[i] = ii * ii * i
}
fmt.Println("The sum of all numbers that can be written as the sum of the 5th powers of their digits is:")
limit := dp5[9] * 6
sum := 0
for i := 2; i <= limit; i++ {
digits := rcu.Digits(i, 10)
totalDp := 0
for _, d := range digits {
totalDp += dp5[d]
}
if totalDp == i {
if sum > 0 {
fmt.Printf(" + %d", i)
} else {
fmt.Print(i)
}
sum += i
}
}
fmt.Printf(" = %d\n", sum)
}</lang>
- Output:
The sum of all numbers that can be written as the sum of the 5th powers of their digits is: 4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839
Julia
In base 10, the largest digit is 9. If n is the number of digits, as n increases, 9^5 * n < 10^n. So we do not have to look beyond 9^5 * 6 since 9^5 * 6 < 1,000,000. <lang julia>println("Numbers > 1 that can be written as the sum of fifth powers of their digits:") arr = [i for i in 2 : 9^5 * 6 if mapreduce(x -> x^5, +, digits(i)) == i] println(join(arr, " + "), " = ", sum(arr))
</lang>
- Output:
Numbers > 1 that can be written as the sum of fifth powers of their digits: 4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839
PARI/GP
<lang parigp>sumfp(n)=if(n<10,n^5,(n%10)^5+sumfp(n\10)); s=0; for(i=2,999999,if(i==sumfp(i),s=s+i;print(i))); print("Total: ",s);</lang>
- Output:
41504151 54748 92727 93084 194979
Total: 443839
Perl
<lang perl>use strict; use warnings; use feature 'say'; use List::Util 'sum';
for my $power (3..6) {
my @matches;
for my $n (2 .. 9**$power * $power) {
push @matches, $n if $n == sum map { $_**$power } split , $n;
}
say "\nSum of powers of n**$power: " . join(' + ', @matches) . ' = ' . sum @matches;
}</lang>
- Output:
Sum of powers of n**3: 153 + 370 + 371 + 407 = 1301 Sum of powers of n**4: 1634 + 8208 + 9474 = 19316 Sum of powers of n**5: 4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839 Sum of powers of n**6: 548834 = 548834
Python
<lang>print(sum([n for n in range(2, 6*9**5) if sum(int(i)**5 for i in str(n)) == n]))</lang>
- Output:
443839
Raku
<lang perl6>print q:to/EXPANATION/; Sum of all integers (except 1 for some mysterious reason ¯\_(ツ)_/¯), for which the individual digits to the nth power sum to itself. EXPANATION
sub super($i) { $i.trans('0123456789' => '⁰¹²³⁴⁵⁶⁷⁸⁹') }
for 3..8 -> $power {
print "\nSum of powers of n{super $power}: ";
my $threshold = 9**$power * $power;
put .join(' + '), ' = ', .sum with cache
(2..$threshold).race.map: {
state %p = ^10 .map: { $_ => $_ ** $power };
$_ if %p{.comb}.sum == $_
}
}</lang>
- Output:
Sum of all integers (except 1 for some mysterious reason ¯\_(ツ)_/¯), for which the individual digits to the nth power sum to itself. Sum of powers of n³: 153 + 370 + 371 + 407 = 1301 Sum of powers of n⁴: 1634 + 8208 + 9474 = 19316 Sum of powers of n⁵: 4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839 Sum of powers of n⁶: 548834 = 548834 Sum of powers of n⁷: 1741725 + 4210818 + 9800817 + 9926315 + 14459929 = 40139604 Sum of powers of n⁸: 24678050 + 24678051 + 88593477 = 137949578
Ring
<lang ring>? "working..."
sumEnd = 0 sumList = ""
pow5 = [] for i = 1 to 9
add(pow5, pow(i, 5))
next
limitStart = 2 limitEnd = 6 * pow5[9]
for n = limitStart to limitEnd
sum = 0
m = n
while m > 0
d = m % 10
if d > 0 sum += pow5[d] ok
m = unsigned(m, 10, "/")
end
if sum = n
sumList += "" + n + " + "
sumEnd += n
ok
next
? "The sum of all the numbers that can be written as the sum of fifth powers of their digits:" ? substr(sumList, 1, len(sumList) - 2) + "= " + sumEnd ? "done..."</lang>
- Output:
working... The sum of all the numbers that can be written as the sum of fifth powers of their digits: 4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839 done...
Wren
Using the Julia entry's logic to arrive at an upper bound: <lang ecmascript>import "./math" for Int
// cache 5th powers of digits var dp5 = (0..9).map { |d| d.pow(5) }.toList
System.print("The sum of all numbers that can be written as the sum of the 5th powers of their digits is:") var limit = dp5[9] * 6 var sum = 0 for (i in 2..limit) {
var digits = Int.digits(i)
var totalDp = digits.reduce(0) { |acc, d| acc + dp5[d] }
if (totalDp == i) {
System.write((sum > 0) ? " + %(i)" : i)
sum = sum + i
}
} System.print(" = %(sum)")</lang>
- Output:
The sum of all numbers that can be written as the sum of the 5th powers of their digits is: 4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839
XPL0
Since 1 is not actually a sum, it should not be included. Thus the answer should be 443839. <lang XPL0>\upper bound: 6*9^5 = 354294 \7*9^5 is still only a 6-digit number, so 6 digits are sufficient
int A, B, C, D, E, F, \digits, A=LSD
A5, B5, C5, D5, E5, F5, \digits to 5th power
A0, B0, C0, D0, E0, F0, \digits multiplied by their decimal place
N, \number that can be written as the sum of its 5th pwrs
S; \sum of all numbers
[S:= 0;
for A:= 0, 9 do \for all digits
[A5:= A*A*A*A*A;
A0:= A;
for B:= 0, 9 do
[B5:= B*B*B*B*B;
B0:= B*10;
for C:= 0, 9 do
[C5:= C*C*C*C*C;
C0:= C*100;
for D:= 0, 9 do
[D5:= D*D*D*D*D;
D0:= D*1000;
for E:= 0, 9 do
[E5:= E*E*E*E*E;
E0:= E*10000;
for F:= 0, 3 do
[F5:= F*F*F*F*F;
F0:= F*100000;
[N:= F0 + E0 + D0 + C0 + B0 + A0;
if N = A5 + B5 + C5 + D5 + E5 + F5 then
[S:= S + N;
IntOut(0, N);
CrLf(0);
];
];
];
];
];
];
];
];
CrLf(0); IntOut(0, S); CrLf(0); ]</lang>
- Output:
0 4150 1 4151 93084 92727 54748 194979 443840