Digit fifth powers: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(Added Quackery.) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (9 intermediate revisions by 7 users not shown) | |||
Line 297:
{{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">
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}}==
Line 1,399 ⟶ 1,617:
=={{header|Quackery}}==
The <code>1 -</code> at the end is to deduct the precluded solution, <code>1</code>.
<syntaxhighlight lang="Quackery"> [ [] swap
Line 1,409 ⟶ 1,629:
0
9 5 ** 6 * times
[ i^
1 - echo</syntaxhighlight>
{{out}}
Line 1,433 ⟶ 1,651:
my $threshold = 9**$power * $power;
put .join(' + '), ' = ', .sum with cache
(2..$threshold).
state %p = ^10 .map: { $_ => $_ ** $power };
$_ if %p{.comb}.sum == $_
Line 1,546 ⟶ 1,764:
{{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}}==
Line 1,610 ⟶ 1,892:
{{libheader|Wren-math}}
Using the Julia entry's logic to arrive at an upper bound:
<syntaxhighlight lang="
// cache 5th powers of digits
| |||