Euler's sum of powers conjecture: Difference between revisions
Content deleted Content added
imported>Pigeon768 |
|||
(44 intermediate revisions by 20 users not shown) | |||
Line 3:
There is a conjecture in mathematics that held for over two hundred years before it was disproved by the finding of a counterexample in 1966 by [http://www.ams.org/journals/mcom/1967-21-097/S0025-5718-1967-0220669-3/S0025-5718-1967-0220669-3.pdf Lander and Parkin].
This conjecture is called [[wp:Euler's sum of powers conjecture|Euler's sum of powers conjecture]] and can be stated as such:
:<big>At least k positive k<sup>th</sup> powers are required to sum to a k<sup>th</sup> power, except for the trivial case of one k<sup>th</sup> power: y<sup>k</sup> = y<sup>k</sup></big>.
In 1966, Leon J. Lander and Thomas R. Parkin used a brute-force search on a [[wp:CDC_6600|CDC 6600]] computer restricting numbers to those less than 250.
The task consists in writing a program to search for an integer solution of <math>x_0^5 + x_1^5 + x_2^5 + x_3^5 = y^5</math> where all <math>x_i</math> and <math>y</math> are distinct integers between 0 and 250 (exclusive). Show an answer here.
Related tasks are:
* [[Pythagorean quadruples]].
* [[Pythagorean triples]].
=={{header|11l}}==
{{trans|Python}}
<
V max_n = 250
V pow_5 = (0 .< max_n).map(n -> Int64(n) ^ 5
V pow5_to_n = Dict(0 .< max_n, n -> (Int64(n) ^ 5
L(x0) 1 .< max_n
Line 44 ⟶ 34:
V r = eulers_sum_of_powers()
print(‘#.^5 + #.^5 + #.^5 + #.^5 = #.^5’.format(r[0], r[1], r[2], r[3], r[4]))</
{{out}}
Line 52 ⟶ 42:
In the program we do not user System/360 integers (31 bits) unable to handle the problem, but System/360 packed decimal (15 digits). 250^5 needs 12 digits.<br>
This program could have been run in 1964. Here, for maximum compatibility, we use only the basic 360 instruction set. Macro instruction XPRNT can be replaced by a WTO.
<
USING EULERCO,R13
B 80(R15)
Line 171 ⟶ 161:
BUF DS CL80
YREGS
END </
{{out}}
<pre>
27 84 110 133 144
</pre>
=={{header|6502 Assembly}}==
This is long enough as it is, so the code here is just the main task body. Details like the BASIC loader (for a C-64, which is what I ran this on) and the output routines (including the very tedious conversion of a 40-bit integer to decimal) were moved into external include files. Also in an external file is the prebuilt table of the first 250 fifth powers ... actually, just for ease of referencing, it's the first 256, 0...255, in five tables each holding one byte of the value.
<syntaxhighlight lang="assembly">; Prove Euler's sum of powers conjecture false by finding
; positive a,b,c,d,e such that a⁵+b⁵+c⁵+d⁵=e⁵.
; we're only looking for the first counterexample, which occurs with all
; integers less than this value
max_value = $fa ; decimal 250
; this header turns our code into a LOADable and RUNnable BASIC program
.include "basic_header.s"
; this contains the first 256 integers to the power of 5 broken up into
; 5 tables of one-byte values (power5byte0 with the LSBs through
; power5byte4 with the MSBs)
.include "power5table.s"
; this defines subroutines and macros for printing messages to
; the console, including `puts` for printing out a NUL-terminated string,
; puthex to display a one-byte value in hexadecimal, and putdec through
; putdec5 to display an N-byte value in decimal
.include "output.s"
; label strings for the result output
.feature string_escapes
success: .asciiz "\r\rFOUND EXAMPLE:\r\r"
between: .asciiz "^5 + "
penult: .asciiz "^5 = "
eqend: .asciiz "^5\r\r(SUM IS "
; the BASIC loader program prints the elapsed time at the end, so we include a
; label for that, too
tilabel: .asciiz ")\r\rTIME:"
; ZP locations to store the integers to try
x0 = $f7
x1 = x0 + 1
x2 = x0 + 2
x3 = x0 + 3
; we use binary search to find integer roots; current bounds go here
low = x0 + 4
hi = x0 + 5
; sum of powers of current candidate integers
sum: .res 5
; when we find a sum with an integer 5th root, we put it here
x4: .res 1
main: ; loop for x0 from 1 to max_value
ldx #01
stx x0
loop0: ; loop for x1 from x0+1 to max_value
ldx x0
inx
stx x1
loop1: ; loop for x2 from x1+1 to max_value
ldx x1
inx
stx x2
loop2: ; loop for x3 from x2+1 to max_value
ldx x2
inx
stx x3
loop3: ; add up the fifth powers of the four numbers
; initialize to 0
lda #00
sta sum
sta sum+1
sta sum+2
sta sum+3
sta sum+4
; we use indexed addressing, taking advantage of the fact that the xn's
; are consecutive, so x0,1 = x1, etc.
ldy #0
addloop:
ldx x0,y
lda sum
clc
adc power5byte0,x
sta sum
lda sum+1
adc power5byte1,x
sta sum+1
lda sum+2
adc power5byte2,x
sta sum+2
lda sum+3
adc power5byte3,x
sta sum+3
lda sum+4
adc power5byte4,x
sta sum+4
iny
cpy #4
bcc addloop
; now sum := x₀⁵+x₁⁵+x₂⁵+x₃⁵
; set initial bounds for binary search
ldx x3
inx
stx low
ldx #max_value
dex
stx hi
binsearch:
; compute midpoint
lda low
cmp hi
beq notdone
bcs done_search
notdone:
ldx #0
clc
adc hi
; now a + carry bit = low+hi; rotating right will get the midpoint
ror
; compare square of midpoint to sum
tax
lda sum+4
cmp power5byte4,x
bne notyet
lda sum+3
cmp power5byte3,x
bne notyet
lda sum+2
cmp power5byte2,x
bne notyet
lda sum+1
cmp power5byte1,x
bne notyet
lda sum
cmp power5byte0,x
beq found
notyet:
bcc sum_lt_guess
inx
stx low
bne endbin
beq endbin
sum_lt_guess:
dex
stx hi
endbin:
bne binsearch
beq binsearch
done_search:
inc x3
lda x3
cmp #max_value
bcs end_loop3
jmp loop3
end_loop3:
inc x2
lda x2
cmp #max_value
bcs end_loop2
jmp loop2
end_loop2:
inc x1
lda x1
cmp #max_value
bcs end_loop1
jmp loop1
end_loop1:
inc x0
lda x0
cmp #max_value
bcs end_loop0
jmp loop0
end_loop0:
; should never get here, means we didn't find an example.
brk
found: stx x4
puts success
putdec x0
ldy #1
ploop: puts between
putdec {x0,y}
iny
cpy #4
bcc ploop
puts penult
putdec {x0,y}
puts eqend
putdec5 sum
puts tilabel
rts</syntaxhighlight>
{{Out}}
<pre> **** COMMODORE 64 BASIC V2 ****
64K RAM SYSTEM 38911 BASIC BYTES FREE
READY.
LOAD"ESOP",8,1
SEARCHING FOR ESOP
LOADING
READY.
RUN:
FOUND EXAMPLE:
27^5 + 84^5 + 110^5 + 133^5 = 144^5
(SUM IS 61917364224)
TIME:095617
READY.</pre>
... almost ten hours, but it did find it!
=={{header|Ada}}==
<
procedure Sum_Of_Powers is
Line 254 ⟶ 474:
Ada.Text_IO.New_Line;
end Sum_Of_Powers;</
{{output}}
<pre> 27 84 110 133 144
Line 261 ⟶ 481:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
INT max number = 250;
Line 305 ⟶ 525:
OD
OD
OD</
Output:
<pre>
Line 315 ⟶ 535:
<br>
Algol W integers are 32-bit only, so we simulate the necessary 12 digit arithmetic with pairs of integers.
<
% find a, b, c, d, e such that a^5 + b^5 + c^5 + d^5 = e^5 %
% where 1 <= a <= b <= c <= d <= e <= 250 %
Line 443 ⟶ 663:
found :
end
end.</
{{out}}
<pre>
27^5 + 84^5 + 110^5 + 133^5 = 144^5
</pre>
=={{header|Arturo}}==
{{trans|Nim}}
<syntaxhighlight lang="rebol">eulerSumOfPowers: function [top][
p5: map 0..top => [& ^ 5]
loop 4..top 'a [
loop 3..a-1 'b [
loop 2..b-1 'c [
loop 1..c-1 'd [
s: (get p5 a) + (get p5 b) + (get p5 c) + (get p5 d)
if integer? index p5 s ->
return ~"|a|^5 + |b|^5 + |c|^5 + |d|^5 = |index p5 s|^5"
]
]
]
]
return "not found" ; shouldn't reach here
]
print eulerSumOfPowers 249</syntaxhighlight>
{{out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f EULERS_SUM_OF_POWERS_CONJECTURE.AWK
BEGIN {
Line 474 ⟶ 722:
}
}
</syntaxhighlight>
{{out}}
<pre>
133^5 + 110^5 + 84^5 + 27^5 = 144^5
15 seconds
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic">arraybase 1
max = 250
pow5_max = max * max * max * max * max
limit_x1 = (pow5_max / 4) ^ 0.2
limit_x2 = (pow5_max / 3) ^ 0.2
limit_x3 = (pow5_max / 2) ^ 0.2
dim pow5(max)
for x1 = 1 to max
pow5[x1] = x1 * x1 * x1 * x1 * x1
next x1
for x1 = 1 to limit_x1
for x2 = x1 +1 to limit_x2
m1 = x1 + x2
ans1 = pow5[x1] + pow5[x2]
if ans1 > pow5_max then exit for
for x3 = x2 +1 to limit_x3
ans2 = ans1 + pow5[x3]
if ans2 > pow5_max then exit for
m2 = (m1 + x3) % 30
if m2 = 0 then m2 = 30
for x4 = x3 +1 to max -1
ans3 = ans2 + pow5[x4]
if ans3 > pow5_max then exit for
for x5 = x4 + m2 to max step 30
if ans3 < pow5[x5] then exit for
if ans3 = pow5[x5] then
print x1; "^5 + "; x2; "^5 + "; x3; "^5 + "; x4; "^5 = "; x5; "^5"
end
end if
next x5
next x4
next x3
next x2
next x1</syntaxhighlight>
{{out}}
<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">100 max = 250
110 for w = 1 to max
120 for x = 1 to w
130 for y = 1 to x
140 for z = 1 to y
150 sum = w^5+x^5+y^5+z^5
160 sol = int(sum^0.2)
170 if sum = sol^5 then
180 print w;"^5 + ";x;"^5 + ";y;"^5 + ";z;"^5 = ";sol;"^5"
190 end
200 endif
210 next z
220 next y
230 next x
240 next w</syntaxhighlight>
{{out}}
<pre>133 ^5 + 110 ^5 + 84 ^5 + 27 ^5 = 144 ^5</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' version 14-09-2015
' compile with: fbc -s console
' some constants calculated when the program is compiled
Const As UInteger max = 250
Const As ULongInt pow5_max = CULngInt(max) * max * max * max * max
' limit x1, x2, x3
Const As UInteger limit_x1 = (pow5_max / 4) ^ 0.2
Const As UInteger limit_x2 = (pow5_max / 3) ^ 0.2
Const As UInteger limit_x3 = (pow5_max / 2) ^ 0.2
' ------=< MAIN >=------
Dim As ULongInt pow5(max), ans1, ans2, ans3
Dim As UInteger x1, x2, x3, x4, x5 , m1, m2
Cls : Print
For x1 = 1 To max
pow5(x1) = CULngInt(x1) * x1 * x1 * x1 * x1
Next x1
For x1 = 1 To limit_x1
For x2 = x1 +1 To limit_x2
m1 = x1 + x2
ans1 = pow5(x1) + pow5(x2)
If ans1 > pow5_max Then Exit For
For x3 = x2 +1 To limit_x3
ans2 = ans1 + pow5(x3)
If ans2 > pow5_max Then Exit For
m2 = (m1 + x3) Mod 30
If m2 = 0 Then m2 = 30
For x4 = x3 +1 To max -1
ans3 = ans2 + pow5(x4)
If ans3 > pow5_max Then Exit For
For x5 = x4 + m2 To max Step 30
If ans3 < pow5(x5) Then Exit For
If ans3 = pow5(x5) Then
Print x1; "^5 + "; x2; "^5 + "; x3; "^5 + "; _
x4; "^5 = "; x5; "^5"
Exit For, For
EndIf
Next x5
Next x4
Next x3
Next x2
Next x1
Print
Print "done"
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>
==={{header|Microsoft Small Basic}}===
<syntaxhighlight lang="smallbasic">' Euler sum of powers conjecture - 03/07/2015
'find: x1^5+x2^5+x3^5+x4^5=x5^5
'-> x1=27 x2=84 x3=110 x4=133 x5=144
maxn=250
For i=1 to maxn
p5[i]=Math.Power(i,5)
EndFor
For x1=1 to maxn-4
For x2=x1+1 to maxn-3
'TextWindow.WriteLine("x1="+x1+", x2="+x2)
For x3=x2+1 to maxn-2
'TextWindow.WriteLine("x1="+x1+", x2="+x2+", x3="+x3)
For x4=x3+1 to maxn-1
'TextWindow.WriteLine("x1="+x1+", x2="+x2+", x3="+x3+", x4="+x4)
x5=x4+1
valx=p5[x5]
sumx=p5[x1]+p5[x2]+p5[x3]+p5[x4]
While x5<=maxn and valx<=sumx
If valx=sumx Then
TextWindow.WriteLine("Found!")
TextWindow.WriteLine("-> "+x1+"^5+"+x2+"^5+"+x3+"^5+"+x4+"^5="+x5+"^5")
TextWindow.WriteLine("x5^5="+sumx)
Goto EndPgrm
EndIf
x5=x5+1
valx=p5[x5]
EndWhile 'x5
EndFor 'x4
EndFor 'x3
EndFor 'x2
EndFor 'x1
EndPgrm: </syntaxhighlight>
{{out}}
<pre>Found!
-> 27^5+84^5+110^5+133^5=144^5
x5^5=61917364224 </pre>
==={{header|Minimal BASIC}}===
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">100 LET m = 250
110 FOR w = 1 TO m
120 FOR x = 1 TO w
130 FOR y = 1 TO x
140 FOR z = 1 TO y
150 LET s = w^5+x^5+y^5+z^5
160 LET r = INT(s^0.2)
170 IF s = r^5 THEN 220
180 NEXT z
190 NEXT y
200 NEXT x
210 NEXT w
220 PRINT w;"^5 +";x;"^5 +";y;"^5+ ";z;"^5 =";r;"^5"
230 END</syntaxhighlight>
{{out}}
<pre>133 ^5 + 110 ^5 + 84 ^5 + 27 ^5 = 144 ^5</pre>
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">EnableExplicit
; assumes an array of non-decreasing positive integers
Procedure.q BinarySearch(Array a.q(1), Target.q)
Protected l = 0, r = ArraySize(a()), m
Repeat
If l > r : ProcedureReturn 0 : EndIf; no match found
m = (l + r) / 2
If a(m) < target
l = m + 1
ElseIf a(m) > target
r = m - 1
Else
ProcedureReturn m ; match found
EndIf
ForEver
EndProcedure
Define i, x0, x1, x2, x3, y
Define.q sum
Define Dim p5.q(249)
For i = 1 To 249
p5(i) = i * i * i * i * i
Next
If OpenConsole()
For x0 = 1 To 249
For x1 = 1 To x0 - 1
For x2 = 1 To x1 - 1
For x3 = 1 To x2 - 1
sum = p5(x0) + p5(x1) + p5(x2) + p5(x3)
y = BinarySearch(p5(), sum)
If y > 0
PrintN(Str(x0) + "^5 + " + Str(x1) + "^5 + " + Str(x2) + "^5 + " + Str(x3) + "^5 = " + Str(y) + "^5")
Goto finish
EndIf
Next x3
Next x2
Next x1
Next x0
PrintN("No solution was found")
finish:
PrintN("")
PrintN("Press any key to close the console")
Repeat: Delay(10) : Until Inkey() <> ""
CloseConsole()
EndIf</syntaxhighlight>
{{out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
==={{header|QL SuperBASIC}}===
This program enhances a modular brute-force search, posted on fidonet in the 1980s, via number theoretic enhancements as used by the
program for ZX Spectrum Basic, but without the early decrement of the RHS in the control framework due to being backward compatible
with the lack of floating point in Sinclair ZX80 BASIC (whereby the latter is truly 'zeroeth' generation). To emulate running on a
ZX80 (needing a 16K RAM pack & MODifications, some given below) that completes the task sooner than the program for the OEM Spectrum,
it relies entirely on integer functions, their upper limit being 2^15- 1 in ZX80 BASIC as well. Thus, the "slide rule" calculation
of each percentage on the Spectrum is replaced by that of ones' digits across "abaci" of relatively prime bases Pi. Given that each
Pi is to be <= 2^7 for said limit's sake, it takes six prime numbers or powers thereof to serve as bases of such a mixed-base number
system, since it is necessary that ΠPi > 249^5 for unambiguous representation (as character strings). On ZX80s there are at most 64
consecutive printable characters (in the inverse video block: t%=48 thus becomes T=128). Just seven bases Pi <= 2^6 will be needed
when the difference between 64 & a base is expressible as a four-bit offset, by which one must 'multiply' (since Z80s lack MUL) in
the reduction step of the optimal assembly algorithm for MOD Pi. Such bases are: 49, 53, 55, 57, 59, 61, 64. In disproving Euler's
conjecture, the program demonstrates that using 60 bits of integer precision in 1966 was 2-fold overkill, or even more so in terms of
overhead cost vis-a-vis contemporaneous computers less sophisticated than a CDC 6600.
<syntaxhighlight lang="qbasic">1 CLS
2 DIM i%(255,6) : DIM a%(6) : DIM c%(6)
3 DIM v%(255,6) : DIM b%(6) : DIM d%(29)
4 RESTORE 137
6 FOR m=0 TO 6
7 READ t%
8 FOR j=1 TO 255
11 LET i%(j,m)=j MOD t%
12 LET v%(j,m)=(i%(j,m) * i%(j,m))MOD t%
14 LET v%(j,m)=(v%(j,m) * v%(j,m))MOD t%
15 LET v%(j,m)=(v%(j,m) * i%(j,m))MOD t%
17 END FOR j : END FOR m
19 PRINT "Abaci ready"
21 FOR j=10 TO 29: d%(j)=210+ j
24 FOR j=0 TO 9: d%(j)=240+ j
25 LET t%=48
30 FOR w=6 TO 246 STEP 3
33 LET o=w
42 FOR x=4 TO 248 STEP 2
44 IF o<x THEN o=x
46 FOR m=1 TO 6: a%(m)=i%((v%(w,m)+v%(x,m)),m)
50 FOR y=10 TO 245 STEP 5
54 IF o<y THEN o=y
56 FOR m=1 TO 6: b%(m)=i%((a%(m)+v%(y,m)),m)
57 FOR z=14 TO 245 STEP 7
59 IF o<z THEN o=z
60 FOR m=1 TO 6: c%(m)=i%((b%(m)+v%(z,m)),m)
65 LET s$="" : FOR m=1 TO 6: s$=s$&CHR$(c%(m)+t%)
70 LET o=o+1 : j=d%(i%((i%(w,0)+i%(x,0)+i%(y,0)+i%(z,0)),0))
75 IF j<o THEN NEXT z
80 FOR k=j TO o STEP -30
85 LET e$="" : FOR m=1 TO 6: e$=e$&CHR$(v%(k,m)+t%)
90 IF s$=e$ THEN PRINT w,x,y,z,k,s$,e$: STOP
95 END FOR k : END FOR z : END FOR y : END FOR x : END FOR w
137 DATA 30,97,113,121,125,127,128</syntaxhighlight>
{{out}}
<pre>Abaci ready
27 84 110 133 144 bT`íα0 bT`íα0</pre>
==={{header|Run BASIC}}===
<syntaxhighlight lang="runbasic">max = 250
FOR w = 1 TO max
FOR x = 1 TO w
FOR y = 1 TO x
FOR z = 1 TO y
sum = w^5 + x^5 + y^5 + z^5
s1 = INT(sum^0.2)
IF sum = s1^5 THEN
PRINT w;"^5 + ";x;"^5 + ";y;"^5 + ";z;"^5 = ";s1;"^5"
end
end if
NEXT z
NEXT y
NEXT x
NEXT w</syntaxhighlight>
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
==={{header|True BASIC}}===
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">LET max = 250
FOR w = 1 TO max
FOR x = 1 TO w
FOR y = 1 TO x
FOR z = 1 TO y
LET sum = w^5 + x^5 + y^5 + z^5
LET s1 = INT(sum^0.2)
IF sum = s1^5 THEN
PRINT w;"^5 + ";x;"^5 + ";y;"^5 + ";z;"^5 = ";s1;"^5"
EXIT FOR
END IF
NEXT z
NEXT y
NEXT x
NEXT w
END</syntaxhighlight>
{{out}}
<pre>Same as Run BASIC entry.</pre>
==={{header|VBA}}===
{{trans|AWK}}<syntaxhighlight lang="vb">Public Declare Function GetTickCount Lib "kernel32.dll" () As Long
Public Sub begin()
start_int = GetTickCount()
main
Debug.Print (GetTickCount() - start_int) / 1000 & " seconds"
End Sub
Private Function pow(x, y) As Variant
pow = CDec(Application.WorksheetFunction.Power(x, y))
End Function
Private Sub main()
For x0 = 1 To 250
For x1 = 1 To x0
For x2 = 1 To x1
For x3 = 1 To x2
sum = CDec(pow(x0, 5) + pow(x1, 5) + pow(x2, 5) + pow(x3, 5))
s1 = Int(pow(sum, 0.2))
If sum = pow(s1, 5) Then
Debug.Print x0 & "^5 + " & x1 & "^5 + " & x2 & "^5 + " & x3 & "^5 = " & s1
Exit Sub
End If
Next x3
Next x2
Next x1
Next x0
End Sub</syntaxhighlight>
{{out}}
<pre>33^5 + 110^5 + 84^5 + 27^5 = 144
160,187 seconds</pre>
==={{header|Visual Basic .NET}}===
====Paired Powers Algorithm====
{{trans|Python}}<syntaxhighlight lang="vbnet">Module Module1
Structure Pair
Dim a, b As Integer
Sub New(x as integer, y as integer)
a = x : b = y
End Sub
End Structure
Dim max As Integer = 250
Dim p5() As Long,
sum2 As SortedDictionary(Of Long, Pair) = New SortedDictionary(Of Long, Pair)
Function Fmt(p As Pair) As String
Return String.Format("{0}^5 + {1}^5", p.a, p.b)
End Function
Sub Init()
p5(0) = 0 : p5(1) = 1 : For i As Integer = 1 To max - 1
For j As Integer = i + 1 To max
p5(j) = CLng(j) * j : p5(j) *= p5(j) * j
sum2.Add(p5(i) + p5(j), New Pair(i, j))
Next
Next
End Sub
Sub Calc(Optional findLowest As Boolean = True)
For i As Integer = 1 To max : Dim p As Long = p5(i)
For Each s In sum2.Keys
Dim t As Long = p - s : If t <= 0 Then Exit For
If sum2.Keys.Contains(t) AndAlso sum2.Item(t).a > sum2.Item(s).b Then
Console.WriteLine(" {1} + {2} = {0}^5", i, Fmt(sum2.Item(s)), Fmt(sum2.Item(t)))
If findLowest Then Exit Sub
End If
Next : Next
End Sub
Sub Main(args As String())
If args.Count > 0 Then
Dim t As Integer = 0 : Integer.TryParse(args(0), t)
If t > 0 AndAlso t < 5405 Then max = t
End If
Console.WriteLine("Checking from 1 to {0}...", max)
For i As Integer = 0 To 1
ReDim p5(max) : sum2.Clear()
Dim st As DateTime = DateTime.Now
Init() : Calc(i = 0)
Console.WriteLine("{0} Computation time to {2} was {1} seconds{0}", vbLf,
(DateTime.Now - st).TotalSeconds, If(i = 0, "find lowest one", "check entire space"))
Next
If Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
End Module</syntaxhighlight>
{{out}}(No command line arguments)
<pre>Checking from 1 to 250...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time to find lowest one was 0.0807819 seconds
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time to check entire space was 0.3830103 seconds</pre>
Command line argument = "1000"<pre>
Checking from 1 to 1000...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time to find lowest one was 0.3112007 seconds
27^5 + 84^5 + 110^5 + 133^5 = 144^5
54^5 + 168^5 + 220^5 + 266^5 = 288^5
81^5 + 252^5 + 330^5 + 399^5 = 432^5
108^5 + 336^5 + 440^5 + 532^5 = 576^5
135^5 + 420^5 + 550^5 + 665^5 = 720^5
162^5 + 504^5 + 660^5 + 798^5 = 864^5
Computation time to check entire space was 28.8847393 seconds</pre>
====Paired Powers w/ Mod 30 Shortcut and Threading====
If one divides the searched array of powers ('''sum2m()''') into 30 pieces, the search time can be reduced by only searching the appropriate one (determined by the Mod 30 value of the value being sought). Once broken down by this, it is now easier to use threading to further reduce the computation time.<br/>The following compares the plain paired powers algorithm to the plain powers plus the mod 30 shortcut algorithm, without and with threading.
<syntaxhighlight lang="vbnet">Module Module1
Structure Pair
Dim a, b As Integer
Sub New(x As Integer, y As Integer)
a = x : b = y
End Sub
End Structure
Dim min As Integer = 1, max As Integer = 250
Dim p5() As Long,
sum2 As SortedDictionary(Of Long, Pair) = New SortedDictionary(Of Long, Pair),
sum2m(29) As SortedDictionary(Of Long, Pair)
Function Fmt(p As Pair) As String
Return String.Format("{0}^5 + {1}^5", p.a, p.b)
End Function
Sub Init()
p5(0) = 0 : p5(min) = CLng(min) * min : p5(min) *= p5(min) * min
For i As Integer = min To max - 1
For j As Integer = i + 1 To max
p5(j) = CLng(j) * j : p5(j) *= p5(j) * j
If j = max Then Continue For
sum2.Add(p5(i) + p5(j), New Pair(i, j))
Next
Next
End Sub
Sub InitM()
For i As Integer = 0 To 29 : sum2m(i) = New SortedDictionary(Of Long, Pair) : Next
p5(0) = 0 : p5(min) = CLng(min) * min : p5(min) *= p5(min) * min
For i As Integer = min To max - 1
For j As Integer = i + 1 To max
p5(j) = CLng(j) * j : p5(j) *= p5(j) * j
If j = max Then Continue For
Dim x As Long = p5(i) + p5(j)
sum2m(x Mod 30).Add(x, New Pair(i, j))
Next
Next
End Sub
Sub Calc(Optional findLowest As Boolean = True)
For i As Integer = min To max : Dim p As Long = p5(i)
For Each s In sum2.Keys
Dim t As Long = p - s : If t <= 0 Then Exit For
If sum2.Keys.Contains(t) AndAlso sum2.Item(t).a > sum2.Item(s).b Then
Console.WriteLine(" {1} + {2} = {0}^5", i,
Fmt(sum2.Item(s)), Fmt(sum2.Item(t)))
If findLowest Then Exit Sub
End If
Next : Next
End Sub
Function CalcM(m As Integer) As List(Of String)
Dim res As New List(Of String)
For i As Integer = min To max
Dim pm As Integer = i Mod 30,
mp As Integer = (pm - m + 30) Mod 30
For Each s In sum2m(m).Keys
Dim t As Long = p5(i) - s : If t <= 0 Then Exit For
If sum2m(mp).Keys.Contains(t) AndAlso
sum2m(mp).Item(t).a > sum2m(m).Item(s).b Then
res.Add(String.Format(" {1} + {2} = {0}^5",
i, Fmt(sum2m(m).Item(s)), Fmt(sum2m(mp).Item(t))))
End If
Next : Next
Return res
End Function
Function Snip(s As String) As Integer
Dim p As Integer = s.IndexOf("=") + 1
Return s.Substring(p, s.IndexOf("^", p) - p)
End Function
Function CompareRes(ByVal x As String, ByVal y As String) As Integer
CompareRes = Snip(x).CompareTo(Snip(y))
If CompareRes = 0 Then CompareRes = x.CompareTo(y)
End Function
Function Validify(def As Integer, s As String) As Integer
Validify = def : Dim t As Integer = 0 : Integer.TryParse(s, t)
If t >= 1 AndAlso Math.Pow(t, 5) < (Long.MaxValue >> 1) Then Validify = t
End Function
Sub Switch(ByRef a As Integer, ByRef b As Integer)
Dim t As Integer = a : a = b : b = t
End Sub
Sub Main(args As String())
Select Case args.Count
Case 1 : max = Validify(max, args(0))
Case > 1
min = Validify(min, args(0))
max = Validify(max, args(1))
If max < min Then Switch(max, min)
End Select
Console.WriteLine("Paired powers, checking from {0} to {1}...", min, max)
For i As Integer = 0 To 1
ReDim p5(max) : sum2.Clear()
Dim st As DateTime = DateTime.Now
Init() : Calc(i = 0)
Console.WriteLine("{0} Computation time to {2} was {1} seconds{0}", vbLf,
(DateTime.Now - st).TotalSeconds, If(i = 0, "find lowest one", "check entire space"))
Next
For i As Integer = 0 To 1
Console.WriteLine("Paired powers with Mod 30 shortcut (entire space) {2}, checking from {0} to {1}...",
min, max, If(i = 0, "sequential", "parallel"))
ReDim p5(max)
Dim res As List(Of String) = New List(Of String)
Dim st As DateTime = DateTime.Now
Dim taskList As New List(Of Task(Of List(Of String)))
InitM()
Select Case i
Case 0
For j As Integer = 0 To 29
res.AddRange(CalcM(j))
Next
Case 1
For j As Integer = 0 To 29 : Dim jj = j
taskList.Add(Task.Run(Function() CalcM(jj)))
Next
Task.WhenAll(taskList)
For Each item In taskList.Select(Function(t) t.Result)
res.AddRange(item) : Next
End Select
res.Sort(AddressOf CompareRes)
For Each item In res
Console.WriteLine(item) : Next
Console.WriteLine("{0} Computation time was {1} seconds{0}", vbLf, (DateTime.Now - st).TotalSeconds)
Next
If Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
End Module</syntaxhighlight>
{{out}}(No command line arguments)<pre>Paired powers, checking from 1 to 250...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time to find lowest one was 0.0781252 seconds
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time to check entire space was 0.3280574 seconds
Paired powers with Mod 30 shortcut (entire space) sequential, checking from 1 to 250...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time was 0.2655529 seconds
Paired powers with Mod 30 shortcut (entire space) parallel, checking from 1 to 250...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time was 0.0624651 seconds</pre>
(command line argument = "1000")<pre>Paired powers, checking from 1 to 1000...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time to find lowest one was 0.2499343 seconds
27^5 + 84^5 + 110^5 + 133^5 = 144^5
54^5 + 168^5 + 220^5 + 266^5 = 288^5
81^5 + 252^5 + 330^5 + 399^5 = 432^5
108^5 + 336^5 + 440^5 + 532^5 = 576^5
135^5 + 420^5 + 550^5 + 665^5 = 720^5
162^5 + 504^5 + 660^5 + 798^5 = 864^5
Computation time to check entire space was 27.805961 seconds
Paired powers with Mod 30 shortcut (entire space) sequential, checking from 1 to 1000...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
54^5 + 168^5 + 220^5 + 266^5 = 288^5
81^5 + 252^5 + 330^5 + 399^5 = 432^5
108^5 + 336^5 + 440^5 + 532^5 = 576^5
135^5 + 420^5 + 550^5 + 665^5 = 720^5
162^5 + 504^5 + 660^5 + 798^5 = 864^5
Computation time was 23.8068928 seconds
Paired powers with Mod 30 shortcut (entire space) parallel, checking from 1 to 1000...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
54^5 + 168^5 + 220^5 + 266^5 = 288^5
81^5 + 252^5 + 330^5 + 399^5 = 432^5
108^5 + 336^5 + 440^5 + 532^5 = 576^5
135^5 + 420^5 + 550^5 + 665^5 = 720^5
162^5 + 504^5 + 660^5 + 798^5 = 864^5
Computation time was 5.4205943 seconds</pre>
(command line arguments = "27 864")<pre>Paired powers, checking from 27 to 864...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Computation time to find lowest one was 0.1562309 seconds
27^5 + 84^5 + 110^5 + 133^5 = 144^5
54^5 + 168^5 + 220^5 + 266^5 = 288^5
81^5 + 252^5 + 330^5 + 399^5 = 432^5
108^5 + 336^5 + 440^5 + 532^5 = 576^5
135^5 + 420^5 + 550^5 + 665^5 = 720^5
162^5 + 504^5 + 660^5 + 798^5 = 864^5
Computation time to check entire space was 15.8243802 seconds
Paired powers with Mod 30 shortcut (entire space) sequential, checking from 27 to 864...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
54^5 + 168^5 + 220^5 + 266^5 = 288^5
81^5 + 252^5 + 330^5 + 399^5 = 432^5
108^5 + 336^5 + 440^5 + 532^5 = 576^5
135^5 + 420^5 + 550^5 + 665^5 = 720^5
162^5 + 504^5 + 660^5 + 798^5 = 864^5
Computation time was 13.0438215 seconds
Paired powers with Mod 30 shortcut (entire space) parallel, checking from 27 to 864...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
54^5 + 168^5 + 220^5 + 266^5 = 288^5
81^5 + 252^5 + 330^5 + 399^5 = 432^5
108^5 + 336^5 + 440^5 + 532^5 = 576^5
135^5 + 420^5 + 550^5 + 665^5 = 720^5
162^5 + 504^5 + 660^5 + 798^5 = 864^5
Computation time was 3.0305365 seconds</pre>
(command line arguments = "189 1008")<pre>Paired powers, checking from 189 to 1008...
189^5 + 588^5 + 770^5 + 931^5 = 1008^5
Computation time to find lowest one was 14.6840411 seconds
189^5 + 588^5 + 770^5 + 931^5 = 1008^5
Computation time to check entire space was 14.7777685 seconds
Paired powers with Mod 30 shortcut (entire space) sequential, checking from 189 to 1008...
189^5 + 588^5 + 770^5 + 931^5 = 1008^5
Computation time was 12.4814705 seconds
Paired powers with Mod 30 shortcut (entire space) parallel, checking from 189 to 1008...
189^5 + 588^5 + 770^5 + 931^5 = 1008^5
Computation time was 2.7180777 seconds</pre>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic">limit = 250
pow5_limit = limit * limit * limit * limit * limit
limit_x1 = (pow5_limit / 4) ^ 0.2
limit_x2 = (pow5_limit / 3) ^ 0.2
limit_x3 = (pow5_limit / 2) ^ 0.2
dim pow5(limit)
for x1 = 1 to limit
pow5(x1) = x1 * x1 * x1 * x1 * x1
next x1
for x1 = 1 to limit_x1
for x2 = x1 +1 to limit_x2
m1 = x1 + x2
ans1 = pow5(x1) + pow5(x2)
if ans1 > pow5_limit break
for x3 = x2 +1 to limit_x3
ans2 = ans1 + pow5(x3)
if ans2 > pow5_limit break
m2 = mod((m1 + x3), 30)
if m2 = 0 m2 = 30
for x4 = x3 +1 to limit -1
ans3 = ans2 + pow5(x4)
if ans3 > pow5_limit break
for x5 = x4 + m2 to limit step 30
if ans3 < pow5(x5) break
if ans3 = pow5(x5) then
print x1, "^5 + ", x2, "^5 + ", x3, "^5 + ", x4, "^5 = ", x5, "^5"
break
fi
next x5
next x4
next x3
next x2
next x1
end</syntaxhighlight>
{{out}}
<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>
==={{header|ZX Spectrum Basic}}===
This "abacus revision" reverts back to an earlier one, i.e. the "slide rule" one
calculating the logarithmic 'percentage' for each of 4 summands. It also calculates their ones' digits as if on a base m abacus, that
complements the other base m digits embedded in their percentages via a check sum of the ones' digits when the percentages add up to 1.
Because any other argument is less than m, there is sufficient additional precision so as to not find false solutions while
seeking the first primitive solution. 1 is excluded a priori for (e.g.) w, since it is well-known that the only integral points on
1=m^5-x^5-y^5-z^5 are the obvious ones (that aren't distinct\all >0). Nonetheless, 1 (as the zeroeth 'prime' Po) can be the first of 3 factors (one of
the others being a power of the first 4 primes) for specifying a LHS argument. Given 4 LHS arguments
each raised to a 5th power as is the RHS for which m<=ΣΠPi<2^(3+5), i=0 to 4, the LHS solution (if one exists) will consist of 4 elements of a factorial domain that are each a triplet
(a prime\Po * a prime^1st\2nd power * a prime^1st\4th power) multiple having a distinct pair of the first 4 primes present &
absent. Such potential solutions are generated by aiming for simplicity rather than
efficiency (e.g. not generating potential solutions where each multiple is even). Two theorems' consequences intended for an even
earlier revision are also applied: Fermat's Little Theorem (as proven later by Euler) whereby Xi^5 mod P = Xi mod P for the first 3
primes; and the Chinese Remainder Theorem in reverse whereby m= k- i*2*3*5, such that k is chosen to be the highest allowed m
congruent mod 30 to the sum of the LHS arguments of a potential solution. Although still slow, this revision performs the given task
on any ZX Spectrum, despite being limited to 32-bit precision.
<syntaxhighlight lang="zxbasic">
1 CLS
2 DIM k(29): DIM q(249)
5 FOR i=4 TO 249: LET q(i)=LN i : NEXT i
6 REM enhancements for the much expanded Spectrum Next: DIM p(248,249)
7 REM FOR j=4TO 248:FOR i=j TO 249:LET p(j,i)=EXP (q(j)-q(i))*5:NEXT i:NEXT j
9 PRINT "slide rule ready"
15 FOR i=0 TO 9: LET k(i)=240+ i : NEXT i
17 FOR i=10 TO 29: LET k(i)=210+ i : NEXT i
20 FOR w=6 TO 246 STEP 3
21 LET o=w
22 FOR x=4 TO 248 STEP 2
23 IF o<x THEN LET o=x
24 FOR y=10 TO 245 STEP 5
25 IF o<y THEN LET o=y
26 FOR z=14 TO 245 STEP 7
27 IF o<z THEN LET o=z
30 LET o=o+1 : LET m=k(FN f((w+x+y+z),30))
34 IF m<o THEN GO TO 90
40 REM LET s=p(w,m)+p(x,m)+p(y,m)+p(z,m) instead of:
42 LET s=EXP((q(w)-q(m))*5)
43 LET s=EXP((q(x)-q(m))*5)+ s
45 LET s=EXP((q(y)-q(m))*5)+ s
47 LET s=EXP((q(z)-q(m))*5)+ s
50 IF s<>1 THEN GO TO 80
52 LET a=FN f(w*w,m) : LET a=FN f(a*a*w,m)
53 LET b=FN f(x*x,m) : LET b=FN f(b*b*x,m)
55 LET c=FN f(y*y,m) : LET c=FN f(c*c*y,m)
57 LET d=FN f(z*z,m) : LET d=FN f(d*d*z,m)
60 LET u=FN f((a+b+c+d),m)
65 IF u THEN GO TO 80
73 PRINT w;"^5+";x;"^5+";y;"^5+";z;"^5=";m;"^5": STOP
80 IF s<1 THEN m=m-30 : GO TO 34
90 NEXT z: NEXT y: NEXT x: NEXT w
100 DEF FN f(e,n)=e- INT(e/n)*n
</syntaxhighlight>
{{out}}
<pre>slide rule ready
27^5+84^5+110^5+133^5=144^5</pre>
=={{header|BCPL}}==
{{trans|Go}}
<syntaxhighlight lang="bcpl">
GET "libhdr"
LET solve() BE {
LET pow5 = VEC 249
LET sum = ?
FOR i = 1 TO 249
pow5!i := i * i * i * i * i
FOR w = 4 TO 249
FOR x = 3 TO w - 1
FOR y = 2 TO x - 1
FOR z = 1 TO y - 1 {
sum := pow5!w + pow5!x + pow5!y + pow5!z
FOR a = w + 1 TO 249
IF pow5!a = sum {
writef("solution found: %d %d %d %d %d *n", w, x, y, z, a)
RETURN
}
}
writef("Sorry, no solution found.*n")
}
LET start() = VALOF {
solve()
RESULTIS 0
}
</syntaxhighlight>
{{Out}}
<pre>
solution found: 133 110 84 27 144
</pre>
=={{header|Bracmat}}==
<
& whl
' ( 1+!x0:<250:?x0
Line 505 ⟶ 1,561:
)
)
)</
'''Output'''
<pre>x0 133 x1 110 x2 84 x3 27 y 144</pre>
Line 511 ⟶ 1,567:
=={{header|C}}==
The trick to speed up was the observation that for any x we have x^5=x modulo 2, 3, and 5, according to the Fermat's little theorem. Thus, based on the Chinese Remainder Theorem we have x^5==x modulo 30 for any x. Therefore, when we have computed the left sum s=a^5+b^5+c^5+d^5, then we know that the right side e^5 must be such that s==e modulo 30. Thus, we do not have to consider all values of e, but only values in the form e=e0+30k, for some starting value e0, and any k. Also, we follow the constraints 1<=a<b<c<d<e<N in the main loop.
<
#include <stdio.h>
#include <time.h>
Line 545 ⟶ 1,601:
printf("time=%d milliseconds\r\n", (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC));
return 0;
}</
{{output}}
The fair way to measure the speed of the code above is to measure it's run time to find all possible solutions to the problem, given N (and not just a single solution, since then the time may depend on the way and the order we organize for-loops).
Line 569 ⟶ 1,625:
===Loops===
{{trans|Java}}
<
namespace EulerSumOfPowers {
Line 600 ⟶ 1,656:
}
}
}</
===Paired Powers, Mod 30, etc...===
{{trans|vbnet}}
<
using System.Collections.Generic;
using System.Linq;
Line 727 ⟶ 1,783:
}
}
}</
{{out}}(no command line arguments)<pre>Mod 30 shortcut with threading, checking from 1 to 250...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Line 743 ⟶ 1,799:
===First version===
The simplest brute-force find is already reasonably quick:
<
#include <iostream>
#include <cmath>
Line 782 ⟶ 1,838:
cout << "time=" << (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC) << " milliseconds\r\n";
return 0;
}</
{{out}}
<pre>
Line 789 ⟶ 1,845:
</pre>
We can accelerate this further by creating a parallel std::set<double> p5s containing the elements of the std::vector pow5, and using it to replace the call to std::binary_search:
<
for (auto i = 1; i < MAX; i++)
{
Line 796 ⟶ 1,852:
}
//...
if (pow5s.find(sum) != pow5s.end())</
This reduces the timing to 125 ms on the same hardware.
A different, more effective optimization is to note that each successive sum is close to the previous one, and use a bidirectional linear search with memory. We also note that inside the innermost loop, we only need to search upward, so we hoist the downward linear search to the loop over x2.
<
{
const auto MAX = 250;
Line 826 ⟶ 1,882:
// not found
return false;
}</
This reduces the timing to around 25 ms. We could equally well replace rs with an iterator inside pow5; the timing is unaffected.
Line 832 ⟶ 1,888:
Fortunately, we can incorporate the same trick into the above code, by inserting a forward jump to a feasible solution mod 30 into the loop over x3:
<
{
// go straight to the first appropriate x3, mod 30
Line 839 ⟶ 1,895:
if (x3 >= x2)
break;
auto sum = s2 + pow5[x3];</
With this refinement, the exhaustive search up to MAX=1000 takes 16.9 seconds.
Line 851 ⟶ 1,907:
<
{
C_ retval(src);
Line 924 ⟶ 1,980:
}
return false;
}</
Thanks, EchoLisp guys!
===Third version===
We expand on the second version with two main improvements. First, we use a hash table instead of binary search to improve the runtime from O(n^3 log n) to O(n^3). Second, we adapt the fast inverse square root algorithm to quickly compute the fifth root. Combined this gives a 7.3x speedup over the Second Version.
<syntaxhighlight lang="cpp">#include <array>
#include <cstdint>
#include <iostream>
#include <memory>
#include <numeric>
template <size_t n, typename T> static constexpr T power(T base) {
if constexpr (n == 0)
return 1;
else if constexpr (n == 1)
return base;
else if constexpr (n & 1)
return power<n / 2, T>(base * base) * base;
else
return power<n / 2, T>(base * base);
}
static constexpr int count = 1024;
static constexpr uint64_t count_diff = []() {
// finds something that looks kinda sorta prime.
const uint64_t coprime_to_this = 2llu * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 59;
// we make this oversized to reduce collisions and just hope it fits in cache.
uint64_t guess = 7 * count * count;
for (; std::gcd(guess, coprime_to_this) > 1; ++guess)
;
return guess;
}();
static constexpr int fast_integer_root5(const double x) {
constexpr uint64_t magic = 3685583637919522816llu;
uint64_t x_i = std::bit_cast<uint64_t>(x);
x_i /= 5;
x_i += magic;
const double x_f = std::bit_cast<double>(x_i);
const double x5 = power<5>(x_f);
return x_f * ((x - x5) / (3 * x5 + 2 * x)) + (x_f + .5);
}
static constexpr uint64_t hash(uint64_t h) { return h % count_diff; }
void euler() {
std::array<int64_t, count> pow5;
for (int64_t i = 0; i < count; i++)
pow5[i] = power<5>(i);
// build hash table
constexpr int oversize_fudge = 8;
std::unique_ptr<int16_t[]> differences = std::make_unique<int16_t[]>(count_diff + oversize_fudge);
std::fill(differences.get(), differences.get() + count_diff + oversize_fudge, 0);
for (int64_t n = 4; n < count; n++)
for (int64_t d = 3; d < n; d++) {
uint64_t h = hash(pow5[n] - pow5[d]);
for (; differences[h]; ++h)
if (h >= count_diff + oversize_fudge - 2) {
std::cerr << "too many collisions; increase fudge factor or hash table size\n";
return;
}
differences[h] = d;
if (h >= count_diff)
differences[h - count_diff] = d;
}
// brute force a,b,c
const int a_max = fast_integer_root5(.25 * pow5.back());
for (int a = 0; a <= a_max; a++) {
const int b_max = fast_integer_root5((1.0 / 3.0) * (pow5.back() - pow5[a]));
for (int b = a; b <= b_max; b++) {
const int64_t a5_p_b5 = pow5[a] + pow5[b];
const int c_max = fast_integer_root5(.5 * (pow5.back() - a5_p_b5));
for (int c = b; c <= c_max; c++) {
// lookup d in hash table
const int64_t n5_minus_d5 = a5_p_b5 + pow5[c];
//this loop is O(1)
for (uint64_t h = hash(n5_minus_d5); differences[h]; ++h) {
if (const int d = differences[h]; d >= c)
// calculate n from d
if (const int n = fast_integer_root5(n5_minus_d5 + pow5[d]);
// check whether this is a solution
n < count && n5_minus_d5 == pow5[n] - pow5[d] && d != n)
std::cout << a << "^5 + " << b << "^5 + " << c << "^5 + " << d << "^5 = " << n << "^5\t"
<< pow5[a] + pow5[b] + pow5[c] + pow5[d] << " = " << pow5[n] << '\n';
}
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
euler();
return 0;
}</syntaxhighlight>
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">
(ns test-p.core
(:require [clojure.math.numeric-tower :as math])
Line 958 ⟶ 2,111:
(println (into #{} (map sort (solve-power-sum 250 1)))) ; MAX = 250, find only 1 value: Duration was 0.26 seconds
(println (into #{} (map sort (solve-power-sum 1000 1000))));MAX = 1000, high max-value so all solutions found: Time = 4.8 seconds
</syntaxhighlight>
Output
<pre>
Line 975 ⟶ 2,128:
=={{header|COBOL}}==
<
IDENTIFICATION DIVISION.
PROGRAM-ID. EULER.
Line 1,073 ⟶ 2,226:
END PROGRAM EULER.
</syntaxhighlight>
Output
<pre>
Line 1,080 ⟶ 2,233:
=={{header|Common Lisp}}==
<
(ql:quickload :alexandria)
(let ((fifth-powers (mapcar #'(lambda (x) (expt x 5))
Line 1,094 ⟶ 2,247:
(if (member x-sum fifth-powers)
(return-from outer (list x0 x1 x2 x3 (round (expt x-sum 0.2)))))))))))
</syntaxhighlight>
{{out}}
<pre>(133 110 84 27 144)</pre>
Line 1,101 ⟶ 2,254:
===First version===
{{trans|Rust}}
<
auto eulersSumOfPowers() {
Line 1,120 ⟶ 2,273:
void main() {
writefln("%d^5 + %d^5 + %d^5 + %d^5 == %d^5", eulersSumOfPowers[]);
}</
{{out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre>
Line 1,128 ⟶ 2,281:
===Second version===
{{trans|Python}}
<
import std.stdio, std.range, std.algorithm, std.typecons;
Line 1,151 ⟶ 2,304:
}
}
}</
{{out}}
<pre>144 Tuple!(uint, uint, uint, uint)(27, 84, 110, 133)</pre>
Line 1,159 ⟶ 2,312:
{{trans|C++}}
This solution is a brutal translation of the iterator-based C++ version, and it should be improved to use more idiomatic D Ranges.
<
alias Pair = Tuple!(double, int);
Line 1,236 ⟶ 2,389:
if (!dPFind(100))
printf("Search finished.\n");
}</
{{out}}
<pre>133 110 27 84 : 144
Line 1,252 ⟶ 2,405:
Search finished.</pre>
Run-time about 7.1 seconds.
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#Pascal Pascal].
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
n = 250
len p5[] n
len h5[] 65537
for i
p5[i + 1] = i * i * i * i * i
h5[p5[i + 1] mod 65537 + 1] = 1
.
func search a s
y = -1
b = n
while a + 1 < b
i = (a + b) div 2
if p5[i + 1] > s
b = i
elif p5[i + 1] < s
a = i
else
a = b
y = i
.
.
return y
.
for x0
for x1
sum1 = p5[x0 + 1] + p5[x1 + 1]
for x2
sum2 = p5[x2 + 1] + sum1
for x3
sum = p5[x3 + 1] + sum2
if h5[sum mod 65537 + 1] = 1
if y >= 0
print x0 & " " & x1 & " " & x2 & " " & x3 & " " & y
break 4
.
.
.
.
</syntaxhighlight>
=={{header|EchoLisp}}==
To speed up things, we search for x0, x1, x2 such as x0^5 + x1^5 + x2^5 = a difference of 5-th powers.
<
(define dim 250)
Line 1,333 ⟶ 2,491:
→ (27 84 110 133 144) ;; time 2.8 sec
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def sum_of_power(max \\ 250) do
{p5, sum2} = setup(max)
Line 1,365 ⟶ 2,523:
Enum.each(Euler.sum_of_power, fn {k,v} ->
IO.puts Enum.map_join(k, " + ", fn i -> "#{i}**5" end) <> " = #{v}**5"
end)</
{{out}}
Line 1,373 ⟶ 2,531:
=={{header|ERRE}}==
<
CONST MAX=250
Line 1,399 ⟶ 2,557:
END FOR
END FOR
END PROGRAM</
{{output}}
<pre>
Line 1,406 ⟶ 2,564:
=={{header|F_Sharp|F#}}==
<
//Find 4 integers whose 5th powers sum to the fifth power of an integer (Quickly!) - Nigel Galloway: April 23rd., 2015
let G =
Line 1,422 ⟶ 2,580:
| _ -> gng(n,i,g,e+1)
gng (1, 1, 1, 1)
</syntaxhighlight>
{{out}}
<pre>
Line 1,430 ⟶ 2,588:
=={{header|Factor}}==
This solution uses Factor's <code>backtrack</code> vocabulary (based on continuations) to simplify the reduction of the search space. Each time <code>xn</code> is called, a new summand is introduced which can only take on a value as high as the previous summand - 1. This also creates a checkpoint for the backtracker. <code>fail</code> causes the backtracking to occur.
<
math.ranges prettyprint sequences ;
Line 1,438 ⟶ 2,596:
250 xn xn xn xn drop 4array dup pow5 nths sum dup pow5
member? [ pow5 index suffix . ] [ 2drop fail ] if</
{{out}}
<pre>
Line 1,446 ⟶ 2,604:
=={{header|Forth}}==
{{trans|Go}}
<
: sq dup * ;
: 5^ dup sq sq * ;
Line 1,483 ⟶ 2,641:
euler
bye
</syntaxhighlight>
{{out}}
<pre>
Line 1,495 ⟶ 2,653:
In 1966 all Fortrans were not equal. On IBM360, INTEGER was a 32-bit integer; on CDC6600, INTEGER was a 60-bit integer.
And Leon J. Lander and Thomas R. Parkin used the CDC6600.
<
C FIND I1,I2,I3,I4,I5 : I1**5+I2**5+I3**5+I4**5=I5**5
INTEGER I,P5(250),SUMX
Line 1,515 ⟶ 2,673:
6 CONTINUE
300 FORMAT(5(1X,I3))
END </
{{out}}
<pre>
Line 1,523 ⟶ 2,681:
===Fortran 95===
{{works with|Fortran|95 and later}}
<
implicit none
Line 1,551 ⟶ 2,709:
end do outer
end program</
{{out}}
<pre> 27 84 110 133 144</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
void local fn EulersSumOfPower( max as int )
long w, x, y, z, sum, s1
for w = 1 to max
for x = 1 to w
for y = 1 to x
for z = 1 to y
sum = w^5 + x^5 + y^5 + z^5
s1 = int(sum^0.2)
if ( sum == s1 ^ 5 )
print w;"^5 + ";x;"^5 + ";y;"^5 + ";z;"^5 = ";s1;"^5"
exit fn
end if
next
next
next
next
end fn
fn EulersSumOfPower( 250 )
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
133^5 + 110^5 + 84^5 + 27^5 = 144^5
</pre>
=={{header|Go}}==
{{trans|Python}}
<
import (
Line 1,653 ⟶ 2,782:
log.Fatal("no solution")
return
}</
{{output}}
<pre>
Line 1,661 ⟶ 2,790:
=={{header|Groovy}}==
{{trans|Java}}
<
static final int MAX_NUMBER = 250
Line 1,688 ⟶ 2,817:
}
}
}</
{{out}}
<pre>27^5 + 84^5 + 110^5 + 133^5 + 144^5</pre>
=={{header|Haskell}}==
<
import Data.List.Ordered
Line 1,714 ⟶ 2,843:
-- which power of 5 is sum ?
let Just x4 = elemIndex p5Sum p5List ]</
{{output}}
<pre>
Line 1,722 ⟶ 2,851:
Or, using dictionaries of powers and sums, and thus rather faster:
{{Trans|Python}}
<
import Data.List (find, intercalate)
import Data.Maybe (maybe)
Line 1,774 ⟶ 2,903:
rangeString :: [Int] -> String
rangeString [] = "[]"
rangeString (x:xs) = '[' : show x <> " .. " <> show (last xs) <> "]"</
{{Out}}
<pre>Euler's sum of powers conjecture – a counter-example in range [1 .. 249]:
Line 1,782 ⟶ 2,911:
=={{header|J}}==
<
(#~ (= <.)@((+/"1)&.:(^&5)))1+4 comb 248
27 84 110 133</
Explanation:
<syntaxhighlight lang
Then, <
Only one possibility remains.
Line 1,796 ⟶ 2,925:
Here's a significantly faster approach (about 100 times faster), based on the echolisp implementation:
<
y=. 250
n=. i.y
Line 1,807 ⟶ 2,936:
x=. (t e. s)#t
|.,&<&~./|:(y,y)#:l#~a e. x
)</
Use:
<
┌─────────────┬───┐
│27 84 110 133│144│
└─────────────┴───┘</
Note that this particular implementation is a bit hackish, since it relies on the solution being unique for the range of numbers being considered. If there were more solutions it would take a little extra code (though not much time) to untangle them.
Line 1,821 ⟶ 2,950:
{{trans|ALGOL 68}}
Tested with Java 6.
<
{
Line 1,864 ⟶ 2,993:
} // main
} // eulerSopConjecture</
Output:
<pre>
Line 1,872 ⟶ 3,001:
=={{header|JavaScript}}==
===ES5===
<
var aPow5 = [];
Line 1,907 ⟶ 3,036:
console.log(oResult.i0 + '^5 + ' + oResult.i1 + '^5 + ' + oResult.i2 +
'^5 + ' + oResult.i3 + '^5 = ' + oResult.iSum + '^5');</
{{Out}}
133^5 + 110^5 + 84^5 + 27^5 = 144^5
'''This'''{{trans|D}} that verify: a^5 + b^5 + c^5 + d^5 = x^5
<
var ns={}, npv=[]
for (var n=0; n<=N; n++) {
Line 1,930 ⟶ 3,059:
var e='<sup>5</sup>', ep=e+' + '
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')
}</
'''Or this'''{{trans|C}} that verify: a^5 + b^5 + c^5 + d^5 = x^5
<
var npv=[], M=30 // x^5 == x modulo M (=2*3*5)
for (var n=0; n<=N; n+=1) npv[n]=Math.pow(n, 5)
Line 1,950 ⟶ 3,079:
var e='<sup>5</sup>', ep=e+' + '
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')
}</
'''Or this'''{{trans|EchoLisp}} that verify: a^5 + b^5 + c^5 = x^5 - d^5
<
var dxs={}, pow=Math.pow
for (var d=1; d<=N; d+=1)
Line 1,969 ⟶ 3,098:
var e='<sup>5</sup>', ep=e+' + '
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')
}</
'''Or this'''{{trans|Python}} that verify: a^5 + b^5 = x^5 - (c^5 + d^5)
<
var is={}, ipv=[], ijs={}, ijpv=[], pow=Math.pow
for (var i=1; i<=N; i+=1) {
Line 1,995 ⟶ 3,124:
var e='<sup>5</sup>', ep=e+' + '
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')
}</
{{output}}
Line 2,007 ⟶ 3,136:
===ES6===
====Procedural====
<
'use strict';
Line 2,047 ⟶ 3,176:
.join(' + ') + ` = ${soln[4]}^5` : 'No solution found.'
})();</
{{Out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
Line 2,055 ⟶ 3,184:
{{Trans|Python}}
{{Trans|Haskell}}
<
'use strict';
Line 2,300 ⟶ 3,429:
// MAIN ---
return main();
})();</
{{Out}}
<pre>Counter-example found:
Line 2,309 ⟶ 3,438:
This version finds all non-decreasing solutions within the specified bounds,
using a brute-force but not entirely blind approach.
<
# and for each solution with x0<=x1<=...<x3, print [x0, x1, x3, x3, y]
#
Line 2,335 ⟶ 3,464:
end
else empty
end ;</
'''The task:'''
<syntaxhighlight lang
{{out}}
<
[27,84,110,133,144]</
=={{header|Julia}}==
<syntaxhighlight lang="julia">
const lim = 250
const pwr = 5
Line 2,366 ⟶ 3,495:
println("A solution is ", s, " = ", @sprintf("%d^%d", y, pwr), ".")
end
</syntaxhighlight>
{{out}}
Line 2,374 ⟶ 3,503:
=={{header|Kotlin}}==
<
val p5 = LongArray(250){ it.toLong() * it * it * it * it }
var sum: Long
Line 2,392 ⟶ 3,521:
}
if (!found) println("No solution was found")
}</
{{out}}
Line 2,401 ⟶ 3,530:
=={{header|Lua}}==
Brute force but still takes under two seconds with LuaJIT.
<
function binarySearch (t, n)
local start, stop, mid = 1, #t
Line 2,442 ⟶ 3,571:
else
print("Looks like he was right after all...")
end</
{{out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5
Time taken: 1.247 seconds</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
x0^5 + x1^5 + x2^5 + x3^5 == y^5 && x0 > 0 && x1 > 0 && x2 > 0 &&
x3 > 0, {x0, x1, x2, x3, y}, Integers][[1, All, -1]]]</
{{out}}
<pre>{27,84,110,133,144}</pre>
=={{header|Modula-2}}==
{{output?|Modula-2}}
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 2,534 ⟶ 3,624:
WriteLn;
ReadChar
END EulerConjecture.</
===Alternative===
{{works with|XDS Modula-2}}
Uses the same idea as the QL SuperBASIC solution, i.e. if the desired equation holds modulo several positive integers M0, M1, ..., and if the LCM of M0, M1, ... is greater than 4*(249^5), then the equation holds absolutely. This makes it unnecessary to have variables with enough bits to store the fifth powers up to 249^5. It isn't clear why the fifth powers in a counterexample must be all different, as the task description seems to assume, so the demo program doesn't enforce this.
<syntaxhighlight lang="modula2">
MODULE EulerFifthPowers;
FROM InOut IMPORT WriteString, WriteLn, WriteCard;
TYPE
(* CARDINAL in XDS Modula-2 is 32-bit unsigned integer *)
TModArray = ARRAY [0..4] OF CARDINAL;
CONST
Modulus = TModArray {327, 329, 334, 335, 337};
MaxTerm = 249;
VAR
res : ARRAY [0..4] OF ARRAY [0..Modulus[4]-1] OF CARDINAL;
inv : ARRAY [0..Modulus[0]-1] OF CARDINAL;
m, s0, s1, s2, s3, x, x0, x1, x2, x3, y : CARDINAL;
BEGIN
(* Set up arrays of 5th powers w.r.t. each modulus *)
FOR m := 0 TO 4 DO
FOR x := 0 TO Modulus[m] - 1 DO
y := (x*x) MOD Modulus[m];
y := (y*y) MOD Modulus[m];
res[m][x] := (x*y) MOD Modulus[m];
END;
END;
(* For Modulus[0] only, set up an inverse array (having checked
elsewhere that 5th powers MOD Modulus[0] are all different) *)
FOR x := 0 TO Modulus[0] - 1 DO
y := res[0][x];
inv[y] := x;
END;
(* Test sums of four 5th powers *)
FOR x0 := 1 TO MaxTerm DO
s0 := res[0][x0];
FOR x1 := x0 TO MaxTerm DO
s1 := (s0 + res[0][x1]) MOD Modulus[0];
FOR x2 := x1 TO MaxTerm DO
s2 := (s1 + res[0][x2]) MOD Modulus[0];
FOR x3 := x2 TO MaxTerm DO
s3 := (s2 + res[0][x3]) MOD Modulus[0];
y := inv[s3];
IF y <= MaxTerm THEN
(* Here, by definition of y, we have
x0^5 + x1^5 + x2^5 + x3^5 = y^5 MOD Modulus[0].
Now test the congruence for the other moduli. *)
m := 1;
WHILE (m <= 4) AND
((res[m][x0] + res[m][x1] + res[m][x2] + res[m][x3])
MOD Modulus[m] = res[m][y])
DO INC(m); END;
IF (m = 5) THEN
WriteString('Counterexample: ');
WriteCard( x0, 1); WriteString('^5 + ');
WriteCard( x1, 1); WriteString('^5 + ');
WriteCard( x2, 1); WriteString('^5 + ');
WriteCard( x3, 1); WriteString('^5 = ');
WriteCard( y, 1); WriteString('^5');
WriteLn;
END; (* IF m... *)
END; (* IF y... *)
END; (* FOR x3 *)
END; (* FOR x2 *)
END; (* FOR x1 *)
END; (* FOR x0 *)
END EulerFifthPowers.
</syntaxhighlight>
{{out}}
<pre>
Counterexample: 27^5 + 84^5 + 110^5 + 133^5 = 144^5
</pre>
=={{header|Nim}}==
{{trans|PureBasic}}
<syntaxhighlight lang="nim">
# Brute force approach
Line 2,582 ⟶ 3,747:
if y == 0 :
echo "No solution was found"
</syntaxhighlight>
{{out}}
Line 2,592 ⟶ 3,757:
=={{header|Oforth}}==
<
| i j k l ip jp kp |
250 loop: i [
Line 2,605 ⟶ 3,770:
]
]
] ;</
{{out}}
Line 2,615 ⟶ 3,780:
=={{header|PARI/GP}}==
Naive script:
<
{{out}}
<pre>144 [27, 84, 110, 133]</pre>
Naive + caching (<code>setbinop</code>):
<
v2=setbinop((x,y)->[min(x,y),max(x,y),x^5+y^5],[0..250]); \\ sums of two fifth powers
for(i=2,#v2,
Line 2,629 ⟶ 3,794:
)
)
}</
{{out}}
<pre>144 [27, 84, 110, 133]</pre>
Line 2,636 ⟶ 3,801:
{{works with|Free Pascal}}
slightly improved.Reducing calculation time by temporary sum and early break.
<
{$IFDEF FPC} {$MODE DELPHI}{$ELSE]{$APPTYPE CONSOLE}{$ENDIF}
type
Line 2,668 ⟶ 3,833:
end;
END.
</syntaxhighlight>
;output:
<pre>
Line 2,677 ⟶ 3,842:
=={{header|Perl}}==
Brute Force:
<
my @p5 = (0,map { $_**5 } 1 .. MAX-1);
my $s = 0;
Line 2,690 ⟶ 3,855:
}
}
}</
{{out}}
<pre>27 84 110 133 144</pre>
Adding some optimizations makes it 5x faster with similar output, but obfuscates things.
{{trans|C++}}<
my @p5 = (0,map { $_**5 } 1 .. MAX-1);
my $rs = 5;
Line 2,713 ⟶ 3,878:
}
}
}</
=={{header|Phix}}==
Line 2,720 ⟶ 3,885:
Quitting when the first is found drops the main loop to 0.7s, so 1.1s in all, vs 4.3s for the full search.<br>
Without the return 0, you just get six permutes (of ordered pairs) for 144.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAX</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">250</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">p5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">sum2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">MAX</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">i5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">j5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j5</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i5</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">},</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">forsum2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">s</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">data</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (show one solution per p)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">forp5</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*data*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*user_data*/</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">forsum2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">forp5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,764 ⟶ 3,932:
=={{header|PHP}}==
{{trans|Python}}
<
function eulers_sum_of_powers () {
Line 2,796 ⟶ 3,964:
echo "$n_0^5 + $n_1^5 + $n_2^5 + $n_3^5 = $y^5";
?></
{{out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">
import sat.
main =>
X = new_list(5), X :: 1..150, decreasing_strict(X),
X[1]**5 #= sum([X[I]**5 : I in 2..5]),
solve(X), printf("%d**5 = %d**5 + %d**5 + %d**5 + %d**5", X[1], X[2], X[3], X[4], X[5]).
</syntaxhighlight>
{{out}}
<pre>144**5 = 133**5 + 110**5 + 84**5 + 27**5</pre>
<pre>CPU time 6.626 seconds</pre>
=={{header|PicoLisp}}==
<
(off S)
Line 2,826 ⟶ 4,005:
(cadr (lup S (car B)))
(cadr (lup S (- (car A) (car B))))
(cdr (lup P (car A))) ) ) ) ) ) ) )</
{{out}}
<pre>(27 84 110 133 144)</pre>
Line 2,833 ⟶ 4,012:
'''Brute Force Search'''<br>
This is a slow algorithm, so attempts have been made to speed it up, including pre-computing the powers, using an ArrayList for them, and using [int] to cast the 5th root rather than use truncate.
<
$max = 250
Line 2,855 ⟶ 4,034:
}
}
}</
{{Out}}
<pre>PS > measure-command { .\euler.ps1 | out-default }
Line 2,870 ⟶ 4,049:
=={{header|Prolog}}==
<
makepowers :-
retractall(pow5(_, _)),
Line 2,891 ⟶ 4,070:
Y_5th is X0_5th + X1_5th + X2_5th + X3_5th,
pow5(Y, Y_5th).
</syntaxhighlight>
{{out}}
<pre>
Line 2,900 ⟶ 4,079:
X3 = 27,
Y = 144 .
</pre>
=={{header|Python}}==
===Procedural===
<
max_n = 250
pow_5 = [n**5 for n in range(max_n)]
Line 2,975 ⟶ 4,096:
return (x0, x1, x2, x3, y)
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</
{{out}}
Line 2,982 ⟶ 4,103:
The above can be written as:
{{works with|Python|2.6+}}
<
def eulers_sum_of_powers():
Line 2,994 ⟶ 4,115:
return (x0, x1, x2, x3, y)
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</
{{out}}
Line 3,000 ⟶ 4,121:
It's much faster to cache and look up sums of two fifth powers, due to the small allowed range:
<
p5, sum2 = {}, {}
Line 3,014 ⟶ 4,135:
if p - s in sum2:
print(p5[p], sum2[s] + sum2[p-s])
exit()</
{{out}}
<pre>144 (27, 84, 110, 133)</pre>
Line 3,020 ⟶ 4,141:
===Composition of pure functions===
{{Works with|Python|3.7}}
<
from itertools import (chain, takewhile)
Line 3,131 ⟶ 4,252:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Euler's sum of powers conjecture – counter-example:
133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
=={{header|Racket}}==
{{trans|C++}}
<
(define MAX 250)
(define pow5 (make-vector MAX))
Line 3,200 ⟶ 4,277:
(when (set-member? pow5s sum)
(displayln (list x0 x1 x2 x3 (inexact->exact (round (expt sum 1/5)))))
(break))))</
{{output}}
<pre>
Line 3,208 ⟶ 4,285:
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Python}}<syntaxhighlight lang="raku" line>constant MAX = 250;
my %po5{Int};
my %sum2{Int};
%po5{
for 1..MAX ->
%sum2{
}
}
for %
say ((sort |%sum2{s},|%sum2{p - s}) X~ '⁵').join(' + '), " = %po5{p}", "⁵" and exit
}
}
}</
{{out}}
<pre>27⁵ + 84⁵ + 110⁵ + 133⁵ =
=={{header|REXX}}==
=== fast computation ===
Line 3,260 ⟶ 4,332:
:* [the left side of the above equation] sum any applicable three integer powers of five
:* [the <big><big>==</big></big> part of the above equation] see if any of the above left─side sums match any of the ≈30k right─side differences
<
parse arg L H N . /*get optional LOW, HIGH, #solutions.*/
if L=='' | L=="," then L= 0 + 1 /*Not specified? Then use the default.*/
Line 3,296 ⟶ 4,368:
if #<N then return /*return, keep searching for more sols.*/
exit # /*stick a fork in it, we're all done. */
</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre>
Line 3,362 ⟶ 4,434:
Execution time for computing/displaying/writing '''200''' numbers on a slow PC is about '''<sup>1</sup>/<sub>16</sub>''' second.
Execution time on a slow PC for computing (alone) for '''6,000''' numbers is less than '''one''' second.
Execution time on a fast PC for computing (alone) for '''23,686''' numbers is exactly '''1.<sup>00</sup>''' seconds.
<
numeric digits 1000 /*ensure enough decimal digs for powers*/
parse arg N oFID . /*obtain optional arguments from the CL*/
Line 3,412 ⟶ 4,484:
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _
show: if tell then say $; call lineout oFID, $; $=; return /*show and/or write it*/</
{{out|output|text= when using the default input of: <tt> 200 </tt>}}
(Shown at three-quarter size.)
Line 3,623 ⟶ 4,695:
=={{header|Ring}}==
<
# Project : Euler's sum of powers conjecture
Line 3,640 ⟶ 4,712:
next
next
</syntaxhighlight>
Output:
<pre>
Line 3,648 ⟶ 4,720:
=={{header|Ruby}}==
Brute force:
<
result = power5.keys.repeated_combination(4).select{|a| power5[a.inject(:+)]}
puts result.map{|a| a.map{|i| "#{power5[i]}**5"}.join(' + ') + " = #{power5[a.inject(:+)]}**5"}</
{{out}}
<pre>
Line 3,658 ⟶ 4,730:
Faster version:
{{trans|Python}}
<
(1..max).each do |i|
p5[i**5] = i
Line 3,672 ⟶ 4,744:
end
end
result.each{|k,v| puts k.map{|i| "#{i}**5"}.join(' + ') + " = #{v}**5"}</
The output is the same above.
=={{header|Rust}}==
<
fn eulers_sum_of_powers() -> (usize, usize, usize, usize, usize) {
Line 3,722 ⟶ 4,773:
let (x0, x1, x2, x3, y) = eulers_sum_of_powers();
println!("{}^5 + {}^5 + {}^5 + {}^5 == {}^5", x0, x1, x2, x3, y)
}</
{{out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre>
Line 3,728 ⟶ 4,779:
=={{header|Scala}}==
===Functional programming===
<
object EulerSopConjecture extends App {
Line 3,747 ⟶ 4,798:
println(sop)
}</
{{Out}}Vector(27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵)
=={{header|Seed7}}==
<
const func integer: binarySearch (in array integer: arr, in integer: aKey) is func
Line 3,806 ⟶ 4,857:
writeln("No solution was found");
end if;
end func;</
{{out}}
Line 3,814 ⟶ 4,865:
=={{header|SenseTalk}}==
<
to findEulerSumOfPowers
set MAX_NUMBER to 250
Line 3,835 ⟶ 4,886:
end repeat
end repeat
end findEulerSumOfPowers</
=={{header|Sidef}}==
{{trans|Raku}}
<
var p5 = Hash()
Line 3,862 ⟶ 4,913:
say "#{t} = #{p5{p}}⁵"
break
}</
{{out}}
<pre>
84⁵ + 27⁵ + 133⁵ + 110⁵ = 144⁵
</pre>
=={{header|Swift}}==
Line 3,905 ⟶ 4,923:
{{trans|Rust}}
<
@inlinable
public func power(_ n: Self) -> Self {
Line 3,935 ⟶ 4,953:
let (x0, x1, x2, x3, y) = sumOfPowers()
print("\(x0)^5 + \(x1)^5 + \(x2)^5 \(x3)^5 = \(y)^5")</
{{out}}
Line 3,941 ⟶ 4,959:
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
=={{header|
<syntaxhighlight lang="tcl">proc doit {{badx 250} {complete 0}} {
## NB: $badx is exclusive upper limit, and also limits y!
for {set y 1} {$y < $badx} {incr y} {
set s [expr {$y ** 5}]
set r5($s) $y ;# fifth roots of valid sums
}
for {set a 1} {$a < $badx} {incr a} {
set suma [expr {$a ** 5}]
for {set b 1} {$b <= $a} {incr b} {
set sumb [expr {$suma + ($b ** 5)}]
for {set c 1} {$c <= $b} {incr c} {
}
puts "search complete (x < $badx)"
}
doit</syntaxhighlight>
{{out}}
144^5 = 133^5 + 110^5 + 84^5 + 27^5
real 0m2.387s
=={{header|UNIX Shell}}==
{{works with|Bourne Again SHell}}
{{works with|Korn Shell}}
{{works with|Zsh}}
Shell is not the go-to language for number-crunching, but if you're going to use a shell, it looks like ksh is the fastest option, at about 8x faster than bash and 2x faster than zsh.
<syntaxhighlight lang="bash">MAX=250
pow5=()
for (( i=1; i<MAX; ++i )); do
pow5[i]=$(( i*i*i*i*i ))
done
for (( a=1; a<MAX; ++a )); do
for (( b=a+1; b<MAX; ++b )); do
for (( c=b+1; c<MAX; ++c )); do
for (( d=c+1; d<MAX; ++d )); do
(( sum=pow5[a]+pow5[b]+pow5[c]+pow5[d] ))
(( low=d+3 ))
(( high=MAX ))
while (( low <= high )); do
(( guess=(low+high)/2 ))
if (( pow5[guess] == sum )); then
printf 'Found example: %d⁵+%d⁵+%d⁵+%d⁵=%d⁵\n' "$a" "$b" "$c" "$d" "$guess"
exit 0
elif (( pow5[guess] < sum )); then
(( low=guess+1 ))
else
(( high=guess-1 ))
fi
done
done
done
done
done
printf 'No examples found.\n'
exit 1</syntaxhighlight>
{{Out}}
<pre>$ time bash esop.sh
Found example: 27⁵+84⁵+110⁵+133⁵=144⁵
bash esop.sh 6953.75s user 37.53s system 99% cpu 1:57:02.41 total
$ time ksh esop.sh
Found example: 27⁵+84⁵+110⁵+133⁵=144⁵
ksh esop.sh 855.66s user 5.30s system 99% cpu 14:26.78 total
$ time zsh esop.sh
Found example: 27⁵+84⁵+110⁵+133⁵=144⁵
zsh esop.sh 1969.48s user 250.82s system 99% cpu 37:11.62 total</pre>
=={{header|VBScript}}==
{{trans|ERRE}}
<
For X0=1 To Max
Line 3,991 ⟶ 5,061:
Function fnP5(n)
fnP5 = n ^ 5
End Function</
{{out}}
Line 3,997 ⟶ 5,067:
=={{header|Visual Basic .NET}}==
{{works with|Visual Basic .NET|2011}}
<syntaxhighlight lang="vbnet">' Euler's sum of powers of 4 conjecture - Patrice Grandin - 17/05/2020
' x1^4 + x2^4 + x3^4 + x4^4 = x5^4
' Project\Add reference\Assembly\Framework System.Numerics
Imports System.Numerics 'BigInteger
Public Class EulerPower4Sum
Private Sub MyForm_Load(sender As Object, e As EventArgs) Handles MyBase.Load
t2 =
Console.WriteLine((t2 - t1).TotalSeconds & " sec")
End Sub 'Load
Private Sub EulerPower45Sum()
Const MaxN =
Dim i, j, i1, i2, i3, i4,
Dim p4(MaxN), n, sumx As Int64
Debug.Print(">EulerPower45Sum")
For i = 1 To
n =
n *= i
Next j
p4(i) = n
Next i
For i1 = 1 To MaxN
If i1 Mod 5 = 0 Then Debug.Print(">i1=" & i1)
For i2 = i1 To MaxN
For i3 = i2 To MaxN
For i4 = i3 To MaxN
sumx = p4(i1) + p4(i2) + p4(i3) + p4(i4)
i5 = i4 + 1
While i5 <= MaxN AndAlso p4(i5) <= sumx
If p4(i5) = sumx Then
Debug.Print(i1 & " " & i2 & " " & i3 & " " & i4 & " " & i5)
Exit Sub
End If
i5 += 1
End While
Next i4
Next i3
Next i2
Next i1
Debug.Print("Not found!")
End Sub 'EulerPower45Sum
Private Sub
Const MaxN = 500000
Dim i, j, i1,
Dim t0 As DateTime
For i = 1
Next j
Next i
For i1 = 1 To MaxN
Debug.Print(">i1=" & i1)
For i2 = i1 To MaxN
If i2 Mod 100 = 0 Then Debug.Print(">i1=" & i1 & " i2=" & i2 & " " & Int((Now - t0).TotalSeconds) & " sec")
For i3 = i2 To MaxN
sumx = p4(i1) + p4(i2) + p4(i3)
i4 = i3 + 1
While i4 <= MaxN AndAlso p4(i4) <= sumx
If p4(i4) = sumx Then
Debug.Print(i1 & " " & i2 & " " & i3 & " " & i4)
Exit Sub
End If
i4 += 1
End While
Next i3
Next i2
Next i1
Debug.Print("Not found!")
End Sub 'EulerPower44Sum
End Class</syntaxhighlight>
{{out}}
<pre>
133 110 84 27 144
</pre>
=={{header|Wren}}==
{{trans|C}}
<
var n = 250
var m = 30
Line 4,352 ⟶ 5,200:
}
}
}</
{{out}}
Timing is for an Intel Core i7-8565U machine running Wren 0.
<pre>
27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵
Took
</pre>
=={{header|XPL0}}==
Runs in 50.3 seconds on Pi4.
<syntaxhighlight lang="xpl0">func real Pow5(N);
int N;
real X, P;
[X:= float(N);
P:= X*X;
P:= P*P;
return P*X;
];
int X0, X1, X2, X3, Y;
real SP;
[for X0:= 1 to 250 do
for X1:= 1 to X0-1 do
for X2:= 1 to X1-1 do
for X3:= 1 to X2-1 do
[SP:= Pow5(X0) + Pow5(X1) + Pow5(X2) + Pow5(X3);
for Y:= X0+1 to 250 do
if Pow5(Y) = SP then
[IntOut(0, X0); Text(0, "^^5 + ");
IntOut(0, X1); Text(0, "^^5 + ");
IntOut(0, X2); Text(0, "^^5 + ");
IntOut(0, X3); Text(0, "^^5 = ");
IntOut(0, Y); Text(0, "^^5^m^j");
exit;
];
];
]</syntaxhighlight>
{{out}}
<pre>
133^5 + 110^5 + 84^5 + 27^5 = 144^5
</pre>
=={{header|Zig}}==
{{trans|Go}}
<syntaxhighlight lang="zig">
const std = @import("std");
const stdout = std.io.getStdOut().outStream();
Line 4,394 ⟶ 5,277:
try stdout.print("Sorry, no solution found.\n", .{});
}
</syntaxhighlight>
{{Out}}
<pre>
Line 4,401 ⟶ 5,284:
=={{header|zkl}}==
Uses two look up tables for efficiency. Counts from 0 for ease of coding.
<
pow5r:=pow5s.enumerate().apply("reverse").toDictionary(); // [144^5:144, ...]
foreach x0,x1,x2,x3 in (249,x0,x1,x2){
Line 4,409 ⟶ 5,292:
.fmt(x3+1,x2+1,x1+1,x0+1,pow5r[sum]+1));
break(4); // the foreach is actually four loops
}</
{{out}}<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>
Using the Python technique of caching double sums results in a 5x speed up [to the first/only solution]; actually the speed up is close to 25x but creating the caches dominates the runtime to the first solution.
{{trans|Python}}
<
foreach i in ([1..249]){
p5[i.pow(5)]=i;
Line 4,427 ⟶ 5,310:
break(2); // or get permutations
}
}</
Note: dictionary keys are always strings and copying a read only list creates a read write list.
{{out}}<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>
|