Digit fifth powers: Difference between revisions
(→{{header|C++}}: exchanged autos for ints) |
m (→{{header|Pascal}}: checking runtime like C++. Restricted to RDTSC on x86-CPU. ~ 523 µs for Power 5.) |
||
Line 488:
Total: 443839</pre>
=={{header|Pascal}}==
slightly modified [[Own_digits_power_sum]] checks decimals up to power 19.
<lang pascal>program PowerOwnDigits2;
{$IFDEF FPC}
Line 498:
uses
SysUtils,StrUtils;
const
CPU_hz = 1000*1000*1000;
const
MAXBASE = 10;
Line 516 ⟶ 517:
Numbers : array of Uint64;
rec_cnt : NativeInt;
function GetCPU_Time: Uint64;
type
TCpu = record
HiCpu,
LoCpu : Dword;
end;
var
Cput : TCpu;
begin
{$ASMMODE INTEL}
asm
RDTSC;
MOV Dword Ptr [CpuT.LoCpu],EAX; MOV Dword Ptr [CpuT.HiCpu],EDX
end;
with Cput do result := Uint64(HiCPU) shl 32 + LoCpu;
end;
function InitCombIdx(ElemCount: Byte): pbyte;
Line 631 ⟶ 649:
var
digits : pByte;
T0,T1 :
tmp : Uint64;
Pot,dgtCnt,i, j : Int32;
begin
T0 := GetCPU_Time;
For pot := 2 to MaxDgtCount do
begin
Write('Exponent : ',Pot,' used ');
T1 := GetCPU_Time;
digits := Init(MaxDgtCount,pot);
rec_cnt := 0;
// i > 0
Line 651 ⟶ 670:
until NextCombWithRep(digits,@gblUD,MaxDgtVal,dgtCnt);
end;
writeln(rec_cnt,' recursions in ',(GetCPU_Time-T1)/CPU_hz:0:6,' GigaCyles');▼
T0 := GetTickCount64-T0;▼
▲ writeln(rec_cnt,' recursions');
If length(numbers) > 0 then
Begin
Line 678 ⟶ 696:
setlength(Numbers,0);
end;
Writeln('Max Uint64 ',Numb2USA(IntToStr(High(Uint64))));
writeln('Total runtime : ',T0/CPU_hz:0:6,' GigaCyles');
{$IFDEF WINDOWS}
readln;
Line 684 ⟶ 704:
setlength(CombIdx,0);
end.</lang>
{{out|Output @ Tio.run}}
<pre style="height:260px">
TIO.RUN User time: 12.905 s //Total runtime : 29.470650 GigaCyles estimated ~2,28 Ghz
Exponent : 2 used 275 recursions in 0.000030 GigaCyles▼
▲Exponent : 2 used 275 recursions
Exponent : 3 used 990 recursions in 0.000161 GigaCyles
153 + 370 + 371 + 407 = sum to 1,301
Exponent : 4 used 2992 recursions in 0.000367 GigaCyles
1,634 + 8,208 + 9,474 = sum to 19,316
Exponent : 5 used 7997 recursions in 0.001193 GigaCyles // /2.28 -> 523 µs
4,150 + 4,151 + 54,748 + 92,727 + 93,084 + 194,979 = sum to 443,839
Exponent : 6 used 19437 recursions in 0.003013 GigaCyles
548,834 = sum to 548,834
Exponent : 7 used 43747 recursions in 0.007827 GigaCyles
1,741,725 + 4,210,818 + 9,800,817 + 9,926,315 + 14,459,929 = sum to 40,139,604
Exponent : 8 used 92367 recursions in 0.017619 GigaCyles
24,678,050 + 24,678,051 + 88,593,477 = sum to 137,949,578
Exponent : 9 used 184745 recursions in 0.037308 GigaCyles
146,511,208 + 472,335,975 + 534,494,836 + 912,985,153 = sum to 2,066,327,172
Exponent : 10 used 352705 recursions in 0.090797 GigaCyles
4,679,307,774 = sum to 4,679,307,774
Exponent : 11 used 646635 recursions in 0.207819 GigaCyles
32,164,049,650 + 32,164,049,651 + 40,028,394,225 + 42,678,290,603 + 44,708,635,679 + 49,388,550,606 + 82,693,916,578 + 94,204,591,914 = sum to 418,030,478,906
Exponent : 12 used 1144055 recursions in 0.295691 GigaCyles
Exponent : 13 used 1961245 recursions in 0.532789 GigaCyles
564,240,140,138 = sum to 564,240,140,138
Exponent : 14 used 3268749 recursions in 0.937579 GigaCyles
28,116,440,335,967 = sum to 28,116,440,335,967
Exponent : 15 used 5311724 recursions in 1.623457 GigaCyles
Exponent : 16 used 8436274 recursions in 2.680338 GigaCyles
4,338,281,769,391,370 + 4,338,281,769,391,371 = sum to 8,676,563,538,782,741
Exponent : 17 used 13123099 recursions in 4.432118 GigaCyles
233,411,150,132,317 + 21,897,142,587,612,075 + 35,641,594,208,964,132 + 35,875,699,062,250,035 = sum to 93,647,847,008,958,559
Exponent : 18 used 20029999 recursions in 7.169892 GigaCyles
Exponent : 19 used 30045004 recursions in 11.431518 GigaCyles
1,517,841,543,307,505,039 + 3,289,582,984,443,187,032 + 4,498,128,791,164,624,869 + 4,929,273,885,928,088,826 = sum to 14,234,827,204,843,405,766
Max Uint64 18,446,744,073,709,551,615
Total runtime : 29.470650 GigaCyles</pre>
=={{header|Perl}}==
|
Revision as of 14:38, 6 November 2021
- Task
Task desciption is taken from Project Euler (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
APL
<lang apl>+/(⊢(/⍨)(⊢=(+/5*⍨⍎¨∘⍕))¨)1↓⍳6×9*5</lang>
- Output:
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
QB64
<lang qbasic>CONST LIMIT& = 9 ^ 5 * 6 ' we don't need to search higher than this in base 10 DIM AS LONG num, sum, digitSum DIM digit AS _BYTE DIM FifthPowers(9) AS _UNSIGNED INTEGER
FOR i% = LBOUND(FifthPowers) TO UBOUND(FifthPowers)
FifthPowers(i%) = i% ^ 5
NEXT i%
FOR i& = 2 TO LIMIT&
num& = i& digitSum& = 0 WHILE num& > 0 digit%% = num& MOD 10 digitSum& = digitSum& + FifthPowers(digit%%) num& = INT(num& / 10) WEND IF digitSum& = i& THEN PRINT digitSum& sum& = sum& + digitSum& END IF
NEXT i&
PRINT "The sum is"; sum </lang>
- Output:
4150 4151 54748 92727 93084 194979 The sum is 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
C++
Fast version. Checks numbers up to 399,999, which is above the requirement of 6 * 95 and well below the overkill value of 999,999. <lang cpp>#include <iostream>
- include <cmath>
- include <chrono>
using namespace std; using namespace chrono; int main() {
auto st = steady_clock::now(); int nums[] = { 0,1,2,3,4,5,6,7,8,9 }, nu[] = { 0,1,2,3 }, p5[10], t = 0; for (int i : nums) p5[i] = pow(i, 5); for (int i : nu) { int im = i * 100000, ip = p5[i]; for (int j : nums) { int jm = im + j * 10000, jp = ip + p5[j]; for (int k : nums) { int km = jm + k * 1000, kp = jp + p5[k]; for (int l : nums) { int lm = km + l * 100, lp = kp + p5[l]; for (int m : nums) { int mm = lm + m * 10, mp = lp + p5[m]; for (int n : nums) { int nm = mm + n; if (nm == mp + p5[n] && nm > 1) t += nm; } } } } } } auto et = steady_clock::now(); std::cout << t << " " << duration_cast<nanoseconds>(et - st).count() / 1000.0 << " μs";
}</lang>
- Output @ Tio.run:
443839 437.436 μs
COBOL
<lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. DIGIT-FIFTH-POWER.
DATA DIVISION. WORKING-STORAGE SECTION. 01 VARIABLES. 03 CANDIDATE PIC 9(6). 03 MAXIMUM PIC 9(6). 03 DIGITS PIC 9 OCCURS 6 TIMES, REDEFINES CANDIDATE. 03 DIGIT PIC 9. 03 POWER-SUM PIC 9(6). 03 TOTAL PIC 9(6).
01 OUT-FORMAT. 03 OUT-NUM PIC Z(5)9.
PROCEDURE DIVISION. BEGIN. MOVE ZERO TO TOTAL. COMPUTE MAXIMUM = 9 ** 5 * 6. PERFORM TEST-NUMBER VARYING CANDIDATE FROM 2 BY 1 UNTIL CANDIDATE IS GREATER THAN MAXIMUM. DISPLAY '------ +'. DISPLAY TOTAL. STOP RUN.
TEST-NUMBER. MOVE ZERO TO POWER-SUM. PERFORM ADD-DIGIT-POWER VARYING DIGIT FROM 1 BY 1 UNTIL DIGIT IS GREATER THAN 6. IF POWER-SUM IS EQUAL TO CANDIDATE, MOVE CANDIDATE TO OUT-NUM, DISPLAY OUT-NUM, ADD CANDIDATE TO TOTAL. ADD-DIGIT-POWER. COMPUTE POWER-SUM = POWER-SUM + DIGITS(DIGIT) ** 5.</lang>
- Output:
4150 4151 54748 92727 93084 194979 ------ + 443839
Cowgol
<lang cowgol>include "cowgol.coh";
sub pow5(n: uint32): (p: uint32) is
p := n*n * n*n * n;
end sub;
sub sum5(n: uint32): (r: uint32) is
r := 0; while n != 0 loop r := r + pow5(n % 10); n := n / 10; end loop;
end sub;
var total: uint32 := 0; var n: uint32 := 2; var max: uint32 := pow5(9) * 6;
while n <= max loop
if n == sum5(n) then total := total + n; print_i32(n); print_nl(); end if; n := n + 1;
end loop;
print("Total: "); print_i32(total); print_nl();</lang>
- Output:
4150 4151 54748 92727 93084 194979 Total: 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
FOCAL
<lang focal>01.10 S M=9^5*6 01.20 S T=0 01.30 F C=2,M;D 3 01.40 T "TOTAL",T,! 01.50 Q
02.10 S X=C 02.20 S S=0 02.30 S Y=FITR(X/10) 02.40 S S=S+(X-Y*10)^5 02.50 S X=Y 02.60 I (-X)2.3
03.10 D 2 03.20 I (C-S)3.5,3.3,3.5 03.30 T %6,C,! 03.40 S T=T+C 03.50 R</lang>
- Output:
= 4150 = 4151 = 54748 = 92727 = 93084 = 194979 TOTAL= 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
J
<lang j>(([=[:+/10&#.^:_1^5:)"0+/@#])2}.i.6*9^5</lang>
- Output:
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
Pascal
slightly modified Own_digits_power_sum checks decimals up to power 19. <lang pascal>program PowerOwnDigits2; {$IFDEF FPC}
{$R+,O+} {$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
SysUtils,StrUtils;
const
CPU_hz = 1000*1000*1000;
const
MAXBASE = 10; MaxDgtVal = MAXBASE - 1; MaxDgtCount = 19;
type
tDgtCnt = 0..MaxDgtCount; tValues = 0..MaxDgtVal; tUsedDigits = array[tValues] of Int8; tpUsedDigits = ^tUsedDigits;
tPower = array[tValues] of Uint64;
var
PowerDgt: tPower; gblUD : tUsedDigits; CombIdx : array of Int8; Numbers : array of Uint64; rec_cnt : NativeInt;
function GetCPU_Time: Uint64; type TCpu = record HiCpu, LoCpu : Dword; end; var Cput : TCpu; begin {$ASMMODE INTEL} asm RDTSC; MOV Dword Ptr [CpuT.LoCpu],EAX; MOV Dword Ptr [CpuT.HiCpu],EDX end; with Cput do result := Uint64(HiCPU) shl 32 + LoCpu; 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(tUsedDigits), #0); gblUD[0]:= 1; end;
function Init(ElemCount:byte;Expo:byte):pByte; var pP1 : pUint64; p: Uint64; i,j: Int32; begin pP1 := @PowerDgt[0]; for i in tValues do Begin p := 1; for j := 1 to Expo do p *= i; pP1[i] := p; end; result := InitCombIdx(ElemCount); gblUD[0]:= 1; end;
function GetPowerSum(minpot:nativeInt;digits:pbyte;var UD :tUsedDigits):NativeInt; var res,r : Uint64; dgt :Int32; begin dgt := minpot; res := 0; repeat dgt -=1; res += PowerDgt[digits[dgt]]; until dgt=0; result := 0; //convert res into digits repeat r := res DIV MAXBASE; result+=1; dgt := res-r*MAXBASE; //substract from used digits UD[dgt] -= 1; res := r; until r = 0; end;
procedure calcNum(minPot:Int32;digits:pbyte); var UD :tUsedDigits; res: Uint64; i: nativeInt; begin UD := gblUD; i:= GetPowerSum(minpot,digits,UD); if i = minPot 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[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 dec(pUD^[dgt]); dgt +=1; pUD^[dgt]:=i+1; repeat pComb[i] := dgt; i -= 1; until i < 0; end; end;
var
digits : pByte; T0,T1 : UInt64; tmp : Uint64; Pot,dgtCnt,i, j : Int32;
begin
T0 := GetCPU_Time; For pot := 2 to MaxDgtCount do begin Write('Exponent : ',Pot,' used '); T1 := GetCPU_Time; digits := Init(MaxDgtCount,pot); rec_cnt := 0; // i > 0 For dgtCnt := 2 to pot+1 do Begin digits := InitCombIdx(Pot); repeat calcnum(dgtCnt,digits); inc(rec_cnt); until NextCombWithRep(digits,@gblUD,MaxDgtVal,dgtCnt); end; writeln(rec_cnt,' recursions in ',(GetCPU_Time-T1)/CPU_hz:0:6,' GigaCyles'); If length(numbers) > 0 then Begin //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;
tmp := 0; for i := 0 to High(Numbers)-1 do begin write(Numb2USA(IntToStr(Numbers[i])),' + '); tmp +=Numbers[i]; end; write(Numb2USA(IntToStr(Numbers[High(Numbers)])),' = '); tmp +=Numbers[High(Numbers)]; writeln('sum to ',Numb2USA(IntToStr(tmp))); end; writeln; setlength(Numbers,0); end; T0 := GetCPU_Time-T0; Writeln('Max Uint64 ',Numb2USA(IntToStr(High(Uint64)))); writeln('Total runtime : ',T0/CPU_hz:0:6,' GigaCyles'); {$IFDEF WINDOWS} readln; {$ENDIF} setlength(CombIdx,0);
end.</lang>
- Output @ Tio.run:
TIO.RUN User time: 12.905 s //Total runtime : 29.470650 GigaCyles estimated ~2,28 Ghz Exponent : 2 used 275 recursions in 0.000030 GigaCyles Exponent : 3 used 990 recursions in 0.000161 GigaCyles 153 + 370 + 371 + 407 = sum to 1,301 Exponent : 4 used 2992 recursions in 0.000367 GigaCyles 1,634 + 8,208 + 9,474 = sum to 19,316 Exponent : 5 used 7997 recursions in 0.001193 GigaCyles // /2.28 -> 523 µs 4,150 + 4,151 + 54,748 + 92,727 + 93,084 + 194,979 = sum to 443,839 Exponent : 6 used 19437 recursions in 0.003013 GigaCyles 548,834 = sum to 548,834 Exponent : 7 used 43747 recursions in 0.007827 GigaCyles 1,741,725 + 4,210,818 + 9,800,817 + 9,926,315 + 14,459,929 = sum to 40,139,604 Exponent : 8 used 92367 recursions in 0.017619 GigaCyles 24,678,050 + 24,678,051 + 88,593,477 = sum to 137,949,578 Exponent : 9 used 184745 recursions in 0.037308 GigaCyles 146,511,208 + 472,335,975 + 534,494,836 + 912,985,153 = sum to 2,066,327,172 Exponent : 10 used 352705 recursions in 0.090797 GigaCyles 4,679,307,774 = sum to 4,679,307,774 Exponent : 11 used 646635 recursions in 0.207819 GigaCyles 32,164,049,650 + 32,164,049,651 + 40,028,394,225 + 42,678,290,603 + 44,708,635,679 + 49,388,550,606 + 82,693,916,578 + 94,204,591,914 = sum to 418,030,478,906 Exponent : 12 used 1144055 recursions in 0.295691 GigaCyles Exponent : 13 used 1961245 recursions in 0.532789 GigaCyles 564,240,140,138 = sum to 564,240,140,138 Exponent : 14 used 3268749 recursions in 0.937579 GigaCyles 28,116,440,335,967 = sum to 28,116,440,335,967 Exponent : 15 used 5311724 recursions in 1.623457 GigaCyles Exponent : 16 used 8436274 recursions in 2.680338 GigaCyles 4,338,281,769,391,370 + 4,338,281,769,391,371 = sum to 8,676,563,538,782,741 Exponent : 17 used 13123099 recursions in 4.432118 GigaCyles 233,411,150,132,317 + 21,897,142,587,612,075 + 35,641,594,208,964,132 + 35,875,699,062,250,035 = sum to 93,647,847,008,958,559 Exponent : 18 used 20029999 recursions in 7.169892 GigaCyles Exponent : 19 used 30045004 recursions in 11.431518 GigaCyles 1,517,841,543,307,505,039 + 3,289,582,984,443,187,032 + 4,498,128,791,164,624,869 + 4,929,273,885,928,088,826 = sum to 14,234,827,204,843,405,766 Max Uint64 18,446,744,073,709,551,615 Total runtime : 29.470650 GigaCyles
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