Digit fifth powers: Difference between revisions
Not a robot (talk | contribs) (Add FOCAL) |
(added =={{header|Pascal}}== minimal modified Own_digits_power_sum) |
||
Line 462: | Line 462: | ||
194979 |
194979 |
||
Total: 443839</pre> |
Total: 443839</pre> |
||
=={{header|Pascal}}== |
|||
slightly modified [[Own_digits_power_sum]] |
|||
<lang pascal>program PowerOwnDigits2; |
|||
{$IFDEF FPC} |
|||
{$R+,O+} |
|||
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON} |
|||
{$ELSE} |
|||
{$APPTYPE CONSOLE} |
|||
{$ENDIF} |
|||
uses |
|||
SysUtils,StrUtils; |
|||
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 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 : Int64; |
|||
tmp : Uint64; |
|||
Pot,dgtCnt,i, j : Int32; |
|||
begin |
|||
For pot := 2 to MaxDgtCount do |
|||
begin |
|||
Writeln('Exponent : ',Pot); |
|||
digits := Init(MaxDgtCount,pot); |
|||
T0 := GetTickCount64; |
|||
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; |
|||
T0 := GetTickCount64-T0; |
|||
writeln(rec_cnt,' recursions'); |
|||
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) do |
|||
begin |
|||
writeln(Numb2USA(IntToStr(Numbers[i]))); |
|||
tmp +=Numbers[i]; |
|||
end; |
|||
writeln('sum to ',Numb2USA(IntToStr(tmp))); |
|||
end; |
|||
writeln; |
|||
setlength(Numbers,0); |
|||
end; |
|||
Writeln('Max Uint64 ',Numb2USA(IntToStr(High(Uint64)))); |
|||
{$IFDEF WINDOWS} |
|||
readln; |
|||
{$ENDIF} |
|||
setlength(CombIdx,0); |
|||
end.</lang> |
|||
{{Out}} |
|||
<pre style="height:190px"> |
|||
Up to 19 Digits: |
|||
TIO.RUN Real time: 10.699 s CPU share: 98.66 % |
|||
Exponent : 2 |
|||
275 recursions |
|||
Exponent : 3 |
|||
990 recursions |
|||
153 |
|||
370 |
|||
371 |
|||
407 |
|||
sum to 1,301 |
|||
Exponent : 4 |
|||
2992 recursions |
|||
1,634 |
|||
8,208 |
|||
9,474 |
|||
sum to 19,316 |
|||
Exponent : 5 |
|||
7997 recursions |
|||
4,150 |
|||
4,151 |
|||
54,748 |
|||
92,727 |
|||
93,084 |
|||
194,979 |
|||
sum to 443,839 |
|||
Exponent : 6 |
|||
19437 recursions |
|||
548,834 |
|||
sum to 548,834 |
|||
Exponent : 7 |
|||
43747 recursions |
|||
1,741,725 |
|||
4,210,818 |
|||
9,800,817 |
|||
9,926,315 |
|||
14,459,929 |
|||
sum to 40,139,604 |
|||
Exponent : 8 |
|||
92367 recursions |
|||
24,678,050 |
|||
24,678,051 |
|||
88,593,477 |
|||
sum to 137,949,578 |
|||
Exponent : 9 |
|||
184745 recursions |
|||
146,511,208 |
|||
472,335,975 |
|||
534,494,836 |
|||
912,985,153 |
|||
sum to 2,066,327,172 |
|||
Exponent : 10 |
|||
352705 recursions |
|||
4,679,307,774 |
|||
sum to 4,679,307,774 |
|||
Exponent : 11 |
|||
646635 recursions |
|||
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 |
|||
1144055 recursions |
|||
Exponent : 13 |
|||
1961245 recursions |
|||
564,240,140,138 |
|||
sum to 564,240,140,138 |
|||
Exponent : 14 |
|||
3268749 recursions |
|||
28,116,440,335,967 |
|||
sum to 28,116,440,335,967 |
|||
Exponent : 15 |
|||
5311724 recursions |
|||
Exponent : 16 |
|||
8436274 recursions |
|||
4,338,281,769,391,370 |
|||
4,338,281,769,391,371 |
|||
sum to 8,676,563,538,782,741 |
|||
Exponent : 17 |
|||
13123099 recursions |
|||
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 |
|||
20029999 recursions |
|||
Exponent : 19 |
|||
30045004 recursions |
|||
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</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
Revision as of 10:21, 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
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 <lang pascal>program PowerOwnDigits2; {$IFDEF FPC}
{$R+,O+} {$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
SysUtils,StrUtils;
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 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 : Int64; tmp : Uint64; Pot,dgtCnt,i, j : Int32;
begin
For pot := 2 to MaxDgtCount do begin Writeln('Exponent : ',Pot); digits := Init(MaxDgtCount,pot); T0 := GetTickCount64; 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; T0 := GetTickCount64-T0; writeln(rec_cnt,' recursions'); 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) do begin writeln(Numb2USA(IntToStr(Numbers[i]))); tmp +=Numbers[i]; end; writeln('sum to ',Numb2USA(IntToStr(tmp))); end; writeln; setlength(Numbers,0); end; Writeln('Max Uint64 ',Numb2USA(IntToStr(High(Uint64)))); {$IFDEF WINDOWS} readln; {$ENDIF} setlength(CombIdx,0);
end.</lang>
- Output:
Up to 19 Digits: TIO.RUN Real time: 10.699 s CPU share: 98.66 % Exponent : 2 275 recursions Exponent : 3 990 recursions 153 370 371 407 sum to 1,301 Exponent : 4 2992 recursions 1,634 8,208 9,474 sum to 19,316 Exponent : 5 7997 recursions 4,150 4,151 54,748 92,727 93,084 194,979 sum to 443,839 Exponent : 6 19437 recursions 548,834 sum to 548,834 Exponent : 7 43747 recursions 1,741,725 4,210,818 9,800,817 9,926,315 14,459,929 sum to 40,139,604 Exponent : 8 92367 recursions 24,678,050 24,678,051 88,593,477 sum to 137,949,578 Exponent : 9 184745 recursions 146,511,208 472,335,975 534,494,836 912,985,153 sum to 2,066,327,172 Exponent : 10 352705 recursions 4,679,307,774 sum to 4,679,307,774 Exponent : 11 646635 recursions 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 1144055 recursions Exponent : 13 1961245 recursions 564,240,140,138 sum to 564,240,140,138 Exponent : 14 3268749 recursions 28,116,440,335,967 sum to 28,116,440,335,967 Exponent : 15 5311724 recursions Exponent : 16 8436274 recursions 4,338,281,769,391,370 4,338,281,769,391,371 sum to 8,676,563,538,782,741 Exponent : 17 13123099 recursions 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 20029999 recursions Exponent : 19 30045004 recursions 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
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