Anonymous user
Euler's sum of powers conjecture: Difference between revisions
Euler's sum of powers conjecture (view source)
Revision as of 14:13, 17 February 2024
, 3 months ago→Second version
Thundergnat (talk | contribs) m (→{{header|Raku}}: whitespace sensitive) |
imported>Pigeon768 |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 728:
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}}==
Line 1,211 ⟶ 1,983:
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}}==
Line 1,545 ⟶ 2,414:
len h5[] 65537
for i = 0 to n - 1
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 = 0 to n - 1
for x1 = 0 to x0
sum1 = p5[x0 + 1] + p5[x1 + 1]
for x2 = 0 to x1
sum2 = p5[x2 + 1] + sum1
for x3 = 0 to x2
sum = p5[x3 + 1] + sum2
if h5[sum mod 65537 + 1] = 1
if y >= 0
print x0 & " " & x1 & " " & x2 & " " & x3 & " " & y
break 4
.
.
.
.
.
</syntaxhighlight>
Line 1,843 ⟶ 2,713:
<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}}==
Line 2,741 ⟶ 3,582:
{{out}}
<pre>{27,84,110,133,144}</pre>
=={{header|Modula-2}}==
Line 2,822 ⟶ 3,625:
ReadChar
END EulerConjecture.</syntaxhighlight>
===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}}==
Line 3,201 ⟶ 4,079:
X3 = 27,
Y = 144 .
</pre>
Line 3,437 ⟶ 4,257:
133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
=={{header|Racket}}==
Line 3,982 ⟶ 4,746:
result.each{|k,v| puts k.map{|i| "#{i}**5"}.join(' + ') + " = #{v}**5"}</syntaxhighlight>
The output is the same above.
=={{header|Rust}}==
Line 4,296 ⟶ 5,039:
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}}==
Line 4,353 ⟶ 5,067:
=={{header|Visual Basic .NET}}==
{{works with|Visual Basic .NET|2011}}
' 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}}
<syntaxhighlight lang="
var n = 250
var m = 30
Line 4,711 ⟶ 5,203:
{{out}}
Timing is for an Intel Core i7-8565U machine running Wren 0.
<pre>
27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵
Took
</pre>
Line 4,821 ⟶ 5,313:
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>
| |||