Digit fifth powers: Difference between revisions
Content deleted Content added
Add Seed7 |
m →{{header|Wren}}: Changed to Wren S/H |
||
(12 intermediate revisions by 9 users not shown) | |||
Line 9:
=={{header|11l}}==
<
R sum(String(n).map(c -> Int(c) ^ 5))
print(sum((2..999999).filter(i -> i == fifth_power_digit_sum(i))))</
{{out}}
Line 20:
=={{header|8080 Assembly}}==
<
puts: equ 9 ; CP/M syscall to print a string
org 100h
Line 170:
dcr b ; Any more digits?
jnz dgaddl
jmp restor</
{{out}}
<pre>4150
Line 181:
=={{header|Ada}}==
<
procedure Digit_Fifth_Powers is
Line 209:
Put ("Sum: ");
Put_Line (Natural'Image (Sum));
end Digit_Fifth_Powers;</
{{out}}
<pre> 4150
Line 222:
As noted by the Julia sample, we need only consider up to 6 digit numbers.<br>
Also note, the digit fifth power sum is independent of the order of the digits.
<
[]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 #
Line 285:
print( ( newline ) );
print( ( "Total: ", whole( total, 0 ), newline ) )
END</
{{out}}
<pre>
Line 294:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
{{out}}
<pre>443839</pre>
=={{header|AppleScript}}==
Simple solution:
<syntaxhighlight lang="applescript">on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on digit5thPowers()
set sums to {}
set total to 0
repeat with n from (2 ^ 5) to ((9 ^ 5) * 6)
set temp to n
set sum to (temp mod 10) ^ 5
repeat while (temp > 9)
set temp to temp div 10
set sum to sum + (temp mod 10) ^ 5
end repeat
if (sum = n) then
set end of sums to n
set total to total + n
end if
end repeat
return join(sums, " + ") & " = " & total
end digit5thPowers
digit5thPowers()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839"</syntaxhighlight>
Faster alternative (about 55 times as fast) using the "start with the digits" approach suggested by other contributors. Its iterative structure requires prior knowledge that six digits will be needed.
<syntaxhighlight lang="applescript">on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on digit5thPowers()
set hits to {}
set total to 0
repeat with d1 from 1 to 9
set s1 to (d1 ^ 5)
repeat with d2 from 1 to d1
set s2 to s1 + (d2 ^ 5)
repeat with d3 from 0 to d2
set s3 to s2 + (d3 ^ 5)
repeat with d4 from 0 to d3
set s4 to s3 + (d4 ^ 5)
repeat with d5 from 0 to d4
set s5 to s4 + (d5 ^ 5)
repeat with d6 from 0 to d5
set sum to s5 + (d6 ^ 5) as integer
set temp to sum
set d to temp mod 10
set digits to {d1, d2, d3, d4, d5, d6}
repeat while (digits contains {d})
repeat with i from 1 to 6
if (digits's item i = d) then
set digits's item i to missing value
exit repeat
end if
end repeat
set temp to temp div 10
set d to temp mod 10
end repeat
if (((count digits each integer) = 0) and (sum > (2 ^ 5))) then
set end of hits to sum
set total to total + sum
end if
end repeat
end repeat
end repeat
end repeat
end repeat
end repeat
return join(hits, " + ") & " = " & total
end digit5thPowers
digit5thPowers()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839"</syntaxhighlight>
Recursive version of the above. This takes the power as a parameter and is believed to be good for powers between 3 and 13. (No matches found when the power is 12.)
<syntaxhighlight lang="applescript">on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on digitNthPowers(pwr)
if ((pwr < 2) or (pwr > 13)) then return missing value -- Clear non-starter or too high for AppleScript.
-- Trusting the theory in the Julia solution, work out how many digits are needed.
set digits to {missing value}
set digitCount to 1
repeat until ((9 ^ pwr) * digitCount < (10 ^ digitCount))
set digitCount to digitCount + 1
set end of digits to missing value
end repeat
set hits to {}
set total to 0
script o
on dnp(slot, dmin, dmax, sum)
-- Recursive handler. Inherits the variables set before this script object.
-- slot: current slot in digits.
-- dmin, dmax: range of digit values to try in it.
-- sum: sum of 5th powers at the calling level.
repeat with d from dmin to dmax
set digits's item slot to d
if (slot < digitCount) then
dnp(slot + 1, 0, d, sum + d ^ pwr)
else
copy digits to checklist
set sum to (sum + (d ^ pwr)) div 1
set temp to sum
set d to temp mod 10
repeat while (checklist contains {d})
repeat with i from 1 to digitCount
if (checklist's item i = d) then
set checklist's item i to missing value
exit repeat
end if
end repeat
set temp to temp div 10
set d to temp mod 10
end repeat
if (((count checklist each integer) = 0) and (sum > (2 ^ pwr))) then
set end of hits to sum
set total to total + sum
end if
end if
end repeat
end dnp
end script
o's dnp(1, 1, 9, 0.0)
if (hits = {}) then return missing value
return join(hits, " + ") & " = " & total
end digitNthPowers
join({digitNthPowers(4), digitNthPowers(5), digitNthPowers(13)}, linefeed)</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"1634 + 8208 + 9474 = 19316
4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839
5.64240140138E+11 = 5.64240140138E+11"</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">fifthDigitSum?: function [n]->
n = sum map digits n 'd -> d^5
print dec sum select 1..1000000 => fifthDigitSum?</syntaxhighlight>
{{out}}
<pre>443839</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f DIGIT_FIFTH_POWERS.AWK
BEGIN {
Line 320 ⟶ 489:
return(total)
}
</syntaxhighlight>
{{out}}
<pre>
Line 348 ⟶ 517:
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
<
dim as string ns = str(n)
dim as uinteger ret = 0
Line 366 ⟶ 535:
next i
print "Their sum is ", sum</
{{out}}<pre>
4150
Line 377 ⟶ 546:
==={{header|GW-BASIC}}===
<
20 FOR I! = 2 TO 999999!
30 GOSUB 80
Line 391 ⟶ 560:
130 NEXT J
140 RETURN
</syntaxhighlight>
{{out}}<pre>
4150
Line 401 ⟶ 570:
Total = 443839</pre>
==={{header|QB64}}===
<
DIM AS LONG num, sum, digitSum
DIM digit AS _BYTE
Line 425 ⟶ 594:
PRINT "The sum is"; sum
</syntaxhighlight>
{{out}}
<pre>
Line 438 ⟶ 607:
=={{header|BQN}}==
<
+´(⊢=Sum5)¨⊸/ 2↓↕6×9⋆5</
{{out}}
<pre>443839</pre>
=={{header|C}}==
<
#include<stdlib.h>
#include<math.h>
Line 464 ⟶ 633:
printf( "Total is %d\n", sum );
return 0;
}</
{{out}}<pre>4150
4151
Line 475 ⟶ 644:
=={{header|C++}}==
Fast version. Checks numbers up to 399,999, which is above the requirement of 6 * 9<sup>5</sup> and well below the overkill value of 999,999.
<
#include <cmath>
#include <chrono>
Line 499 ⟶ 668:
std::cout << t << " " <<
duration_cast<nanoseconds>(et - st).count() / 1000.0 << " μs";
}</
{{out|Output @ Tio.run}}
<pre>443839 250.514 μs</pre>
=={{header|CLU}}==
<
sum: int := 0
while n > 0 do
Line 526 ⟶ 695:
stream$putright(po, int$unparse(total), 6)
stream$putc(po, '\n')
end start_up</
{{out}}
<pre> 4150
Line 538 ⟶ 707:
=={{header|COBOL}}==
<
PROGRAM-ID. DIGIT-FIFTH-POWER.
Line 577 ⟶ 746:
ADD-DIGIT-POWER.
COMPUTE POWER-SUM = POWER-SUM + DIGITS(DIGIT) ** 5.</
{{out}}
<pre> 4150
Line 589 ⟶ 758:
=={{header|Comal}}==
<
0020 sum:=0
0030 WHILE n>0 DO sum:+(n MOD 10)^5;n:=n DIV 10
Line 605 ⟶ 774:
0150 PRINT "------ +"
0160 PRINT USING "######":total
0170 END</
{{out}}
<pre> 4150
Line 617 ⟶ 786:
=={{header|Cowgol}}==
<
sub pow5(n: uint32): (p: uint32) is
Line 646 ⟶ 815:
print("Total: ");
print_i32(total);
print_nl();</
{{out}}
<pre>4150
Line 658 ⟶ 827:
=={{header|Factor}}==
Thanks to to the [http://rosettacode.org/wiki/Digit_fifth_powers#Julia Julia entry] for the tip about the upper bound of the search.
<
math.vectors prettyprint sequences ;
2 9 5 ^ 6 * [a,b] [ dup 1 digit-groups 5 v^n sum = ] filter sum .</
{{out}}
<pre>
Line 668 ⟶ 837:
=={{header|Fermat}}==
<
sum:=0;
for i=2 to 999999 do if i=Sumfp(i) then sum:=sum+i; !!i fi od;
!!('The sum was ', sum );</
{{out}}<pre>
4150
Line 680 ⟶ 849:
194979
The sum was 443839</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Optimized for speed - runs in 60 ms on a Ryzen 7.
<syntaxhighlight lang="Delphi">
const Power5: array [0..9] of integer = (0,1,32,243,1024,3125,7776,16807,32768,59049);
function SumFifthPower(N: integer): integer;
var S: string;
var I: integer;
begin
S:=IntToStr(N);
Result:=0;
for I:=1 to Length(S) do
Result:=Result+Power5[byte(S[I])-$30];
end;
procedure ShowFiftPowerDigits(Memo: TMemo);
var I,Sum: integer;
begin
Sum:=0;
for I:=2 to 354424 do
begin
if I = SumFifthPower(I) then
begin
Memo.Lines.Add(Format('%8.0n',[I*1.0]));
Sum:=Sum+I;
end;
end;
Memo.Lines.Add('========');
Memo.Lines.Add(Format('%8.0n',[Sum*1.0]));
end;
</syntaxhighlight>
{{out}}
<pre>
4,150
4,151
54,748
92,727
93,084
194,979
========
443,839
</pre>
=={{header|FOCAL}}==
<
01.20 S T=0
01.30 F C=2,M;D 3
Line 699 ⟶ 917:
03.30 T %6,C,!
03.40 S T=T+C
03.50 R</
{{out}}
<pre>= 4150
Line 712 ⟶ 930:
{{trans|Wren}}
{{libheader|Go-rcu}}
<
import (
Line 745 ⟶ 963:
}
fmt.Printf(" = %d\n", sum)
}</
{{out}}
Line 754 ⟶ 972:
=={{header|J}}==
<
{{out}}
<pre>443839</pre>
Line 765 ⟶ 983:
'''Preliminaries'''
<
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
Line 771 ⟶ 989:
# Output: a stream of integers
def digits: tostring | explode[] | [.] | implode | tonumber;</
'''The Task'''
<
def dp5: [range(0;10) | power(5)];
Line 783 ⟶ 1,001:
| select(. == $s) ) ;
"The sum of all numbers that can be written as the sum of the 5th powers of their digits is:", task</
{{out}}
<pre>
Line 794 ⟶ 1,012:
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.
<
arr = [i for i in 2 : 9^5 * 6 if mapreduce(x -> x^5, +, digits(i)) == i]
println(join(arr, " + "), " = ", sum(arr))
</
<pre>
Numbers > 1 that can be written as the sum of fifth powers of their digits:
Line 804 ⟶ 1,022:
=={{header|MAD}}==
<
INTERNAL FUNCTION(X)
Line 836 ⟶ 1,054:
VECTOR VALUES NUM = $S7,I6*$
VECTOR VALUES TOT = $7HTOTAL: ,I6*$
END OF PROGRAM </
{{out}}
<pre> 4150
Line 845 ⟶ 1,063:
194979
TOTAL: 443839</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[FifthPowerSumQ]
FifthPowerSumQ[n_Integer] := Total[IntegerDigits[n]^5] == n
sol = Select[Range[2, 10000000], FifthPowerSumQ]
Total[sol]</syntaxhighlight>
{{out}}
<pre>{4150, 4151, 54748, 92727, 93084, 194979}
443839</pre>
=={{header|PARI/GP}}==
<
s=0;
for(i=2,999999,if(i==sumfp(i),s=s+i;print(i)));
print("Total: ",s);</
{{out}}<pre>4150
4151
Line 861 ⟶ 1,088:
=={{header|Pascal}}==
slightly modified [[Own_digits_power_sum]] checks decimals up to power 19.
<
{$IFDEF FPC}
{$R+,O+}
Line 1,075 ⟶ 1,302:
{$ENDIF}
setlength(CombIdx,0);
end.</
{{out|Output @ Tio.run}}
<pre style="height:260px">
Line 1,133 ⟶ 1,360:
=={{header|Perl}}==
<
use warnings;
use feature 'say';
Line 1,144 ⟶ 1,371:
}
say "\nSum of powers of n**$power: " . join(' + ', @matches) . ' = ' . sum @matches;
}</
{{out}}
<pre>Sum of powers of n**3: 153 + 370 + 371 + 407 = 1301
Line 1,152 ⟶ 1,379:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">sum5</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 1,167 ⟶ 1,394:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s = %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">),</span><span style="color: #000000;">total</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 1,174 ⟶ 1,401:
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">
(de sum5th (N)
(sum
Line 1,191 ⟶ 1,418:
(prinl "Their sum is " (apply + solutions))
(bye)
</syntaxhighlight>
{{Out}}
<pre>
Line 1,199 ⟶ 1,426:
</pre>
=={{header|PILOT}}==
<
:sum=0
:n=2
Line 1,216 ⟶ 1,443:
J (n<max):*number
T :Total: #sum
E :</
{{out}}
<pre>4150
Line 1,227 ⟶ 1,454:
=={{header|PL/M}}==
<
/* BDOS ROUTINES */
BDOS: PROCEDURE (F,A); DECLARE F BYTE, A ADDRESS; GO TO 5; END BDOS;
Line 1,337 ⟶ 1,564:
CALL NEWLINE;
CALL EXIT;
EOF</
{{out}}
<pre>4150
Line 1,349 ⟶ 1,576:
=={{header|Python}}==
Comparing conventional vs. faster.
<
# conventional
Line 1,382 ⟶ 1,609:
if np == nm:
if nm > 1: numbers.append(nm)
print(sum(numbers), " ", (time() - st) * 1000, "ms", end = "")</
{{out|Output @ Tio.run}}
<pre>443839 195.04594802856445 ms
443839 22.282838821411133 ms</pre>Around eight times faster.
=={{header|Quackery}}==
Credit to the Julia example for deducing that 9^5*6 is an upper bound.
The <code>1 -</code> at the end is to deduct the precluded solution, <code>1</code>.
<syntaxhighlight lang="Quackery"> [ [] swap
[ 10 /mod
rot join swap
dup 0 = until ]
drop ] is digits ( n --> [ )
0
9 5 ** 6 * times
[ i^ 0 over digits
witheach [ 5 ** + ]
= if [ i^ + ] ]
1 - echo</syntaxhighlight>
{{out}}
<pre>443839</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku"
Sum of all integers (except 1 for some mysterious reason ¯\_(ツ)_/¯),
for which the individual digits to the nth power sum to itself.
Line 1,400 ⟶ 1,651:
my $threshold = 9**$power * $power;
put .join(' + '), ' = ', .sum with cache
(2..$threshold).
state %p = ^10 .map: { $_ => $_ ** $power };
$_ if %p{.comb}.sum == $_
}
}</
{{out}}
<pre>Sum of all integers (except 1 for some mysterious reason ¯\_(ツ)_/¯),
Line 1,422 ⟶ 1,673:
=={{header|REXX}}==
<
maximum = 9**5 * 6
Line 1,443 ⟶ 1,694:
result = result + substr(num, i, 1) ** 5
end
return result</
{{out}}
<pre>4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839</pre>
Line 1,449 ⟶ 1,700:
=={{header|Ring}}==
===Conventional===
<
sumEnd = 0
Line 1,478 ⟶ 1,729:
? "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..."</
{{out}}
<pre>
Line 1,489 ⟶ 1,740:
===Faster===
Around six times faster than the conventional version.
<
lst9 = 1:10 lst3 = 1:4
p5 = [] m5 = [] m4 = [] m3 = [] m2 = [] m1 = []
Line 1,510 ⟶ 1,761:
next next next next next next
et = clock()
put t + " = " + s + " " + (et - st) / clockspersecond() + " sec"</
{{out|Output @ Tio.run}}
<pre>4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839 4.90 sec</pre>
=={{header|RPL}}==
===Brute force approach===
The code below could have worked... if the time dog of the RPL emulator did not interrupt the execution after a few minutes.
≪ 2 999999 '''FOR''' n
n →STR DUP SIZE 0 1 ROT '''FOR''' j
OVER j DUP SUB STR→ 5 ^ +
'''NEXT'''
'''IF''' n ≠ '''THEN''' DROP '''END'''
'''NEXT'''
≫
===Smarter approach===
{{works with|Halcyon Calc|4.2.7}}
So as not to wake the time dog, the execution has been broken into several parts and the algorithm has been improved:
# the program does not generate all the compliant numbers, but only provides the next value of the sequence, given the first ones
# since 9^5 = 59094, we do not need to check if the sum of the powered digits matches for numbers with a 9 and less than 59094
# on the other side, 6 * 7^5 = 100842, which means that 6-digit numbers above this value must have at least an 8 or a 9 in their digits to comply
# as 6 * 9^5 = 354424, there can't be any compliant 6-digit number above this value
≪ DUP SIZE 0 1 ROT '''FOR''' j
OVER j DUP SUB STR→ 5 ^ +
'''NEXT'''
SWAP DROP
'''IF''' DUP2 == '''THEN''' 1 SF ROT + SWAP '''ELSE''' DROP '''END'''
≫
'Chk5p' STO
≪ DROP
'''IF''' DUP SIZE '''THEN''' DUP LIST→ →ARRY RNRM 1 + '''ELSE''' 2 '''END'''
1 CF '''DO'''
DUP →STR
'''IF''' OVER 59094 ≤
'''THEN IF''' DUP "9" POS NOT '''THEN''' Chk5p '''ELSE''' DROP '''END'''
'''ELSE IF''' OVER 100842 ≥
'''THEN IF''' DUP "9" POS OVER "8" POS OR '''THEN''' Chk5p '''ELSE''' DROP '''END'''
'''ELSE''' Chk5p
'''END'''
'''END'''
1 +
'''UNTIL''' 1 FS? DUP 354424 == OR '''END'''
DROP DUP LIST→ →ARRY CNRM
≫
'NXT5P' STO
{} 0 NXT5P
NXT5P
NXT5P
NXT5P
NXT5P
NXT5P
{{out}}
<pre>
2: { 194979 93084 92727 54748 4151 4150 }
1: 443839
</pre>
=={{header|Ruby}}==
Translation of Julia.
<syntaxhighlight lang="ruby">arr = (2..9**5*6).select{|n| n.digits.sum{|d| d**5} == n }
puts "#{arr.join(" + ")} = #{arr.sum}"
</syntaxhighlight>
{{out}}
<pre>4150 + 4151 + 54748 + 92727 + 93084 + 194979 = 443839
</pre>
=={{header|Seed7}}==
<
const proc: main is func
Line 1,536 ⟶ 1,851:
end for;
writeln(sum);
end func;</
{{out}}
<pre>
Line 1,543 ⟶ 1,858:
=={{header|Sidef}}==
<
var D = @(^base)
Line 1,563 ⟶ 1,878:
var a = digit_nth_powers(n)
say "Sum of #{n}-th powers of their digits: #{a.join(' + ')} = #{a.sum}"
}</
{{out}}
<pre>
Line 1,577 ⟶ 1,892:
{{libheader|Wren-math}}
Using the Julia entry's logic to arrive at an upper bound:
<
// cache 5th powers of digits
Line 1,593 ⟶ 1,908:
}
}
System.print(" = %(sum)")</
{{out}}
Line 1,603 ⟶ 1,918:
=={{header|XPL0}}==
Since 1 is not actually a sum, it should not be included. Thus the answer should be 443839.
<
\7*9^5 is still only a 6-digit number, so 6 digits are sufficient
Line 1,648 ⟶ 1,963:
IntOut(0, S);
CrLf(0);
]</
{{out}}
Line 1,665 ⟶ 1,980:
=={{header|Zig}}==
<
fn sum5(n: u32) u32 {
Line 1,689 ⟶ 2,004:
try stdout.print("Total: {d:6}\n", .{total});
}</
{{out}}
<pre> 4150
|