Euler's sum of powers conjecture: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
|||
Line 29:
=={{header|11l}}==
{{trans|Python}}
<
V max_n = 250
V pow_5 = (0 .< max_n).map(n -> Int64(n) ^ 5)
Line 44:
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:
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:
BUF DS CL80
YREGS
END </
{{out}}
<pre>
Line 180:
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.
<
; positive a,b,c,d,e such that a⁵+b⁵+c⁵+d⁵=e⁵.
Line 379:
putdec5 sum
puts tilabel
rts</
{{Out}}
Line 409:
=={{header|Ada}}==
<
procedure Sum_Of_Powers is
Line 484:
Ada.Text_IO.New_Line;
end Sum_Of_Powers;</
{{output}}
<pre> 27 84 110 133 144
Line 491:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
INT max number = 250;
Line 535:
OD
OD
OD</
Output:
<pre>
Line 545:
<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 673:
found :
end
end.</
{{out}}
<pre>
Line 683:
{{trans|Nim}}
<
p5: map 0..top => [& ^ 5]
Line 701:
]
print eulerSumOfPowers 249</
{{out}}
Line 708:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f EULERS_SUM_OF_POWERS_CONJECTURE.AWK
BEGIN {
Line 732:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 741:
=={{header|BCPL}}==
{{trans|Go}}
<syntaxhighlight lang="bcpl">
GET "libhdr"
Line 769:
RESULTIS 0
}
</syntaxhighlight>
{{Out}}
<pre>
Line 776:
=={{header|Bracmat}}==
<
& whl
' ( 1+!x0:<250:?x0
Line 799:
)
)
)</
'''Output'''
<pre>x0 133 x1 110 x2 84 x3 27 y 144</pre>
Line 805:
=={{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 839:
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 863:
===Loops===
{{trans|Java}}
<
namespace EulerSumOfPowers {
Line 894:
}
}
}</
===Paired Powers, Mod 30, etc...===
{{trans|vbnet}}
<
using System.Collections.Generic;
using System.Linq;
Line 1,021:
}
}
}</
{{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 1,037:
===First version===
The simplest brute-force find is already reasonably quick:
<
#include <iostream>
#include <cmath>
Line 1,076:
cout << "time=" << (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC) << " milliseconds\r\n";
return 0;
}</
{{out}}
<pre>
Line 1,083:
</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 1,090:
}
//...
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 1,120:
// 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 1,126:
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 1,133:
if (x3 >= x2)
break;
auto sum = s2 + pow5[x3];</
With this refinement, the exhaustive search up to MAX=1000 takes 16.9 seconds.
Line 1,145:
<
{
C_ retval(src);
Line 1,218:
}
return false;
}</
Thanks, EchoLisp guys!
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">
(ns test-p.core
(:require [clojure.math.numeric-tower :as math])
Line 1,252:
(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 1,269:
=={{header|COBOL}}==
<
IDENTIFICATION DIVISION.
PROGRAM-ID. EULER.
Line 1,367:
END PROGRAM EULER.
</syntaxhighlight>
Output
<pre>
Line 1,374:
=={{header|Common Lisp}}==
<
(ql:quickload :alexandria)
(let ((fifth-powers (mapcar #'(lambda (x) (expt x 5))
Line 1,388:
(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,395:
===First version===
{{trans|Rust}}
<
auto eulersSumOfPowers() {
Line 1,414:
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,422:
===Second version===
{{trans|Python}}
<
import std.stdio, std.range, std.algorithm, std.typecons;
Line 1,445:
}
}
}</
{{out}}
<pre>144 Tuple!(uint, uint, uint, uint)(27, 84, 110, 133)</pre>
Line 1,453:
{{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,530:
if (!dPFind(100))
printf("Search finished.\n");
}</
{{out}}
<pre>133 110 27 84 : 144
Line 1,550:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">n = 250
len p5[] n
len h5[] 65537
Line 1,589:
.
.
.</
=={{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,629:
→ (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,661:
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,669:
=={{header|ERRE}}==
<
CONST MAX=250
Line 1,695:
END FOR
END FOR
END PROGRAM</
{{output}}
<pre>
Line 1,702:
=={{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,718:
| _ -> gng(n,i,g,e+1)
gng (1, 1, 1, 1)
</syntaxhighlight>
{{out}}
<pre>
Line 1,726:
=={{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,734:
250 xn xn xn xn drop 4array dup pow5 nths sum dup pow5
member? [ pow5 index suffix . ] [ 2drop fail ] if</
{{out}}
<pre>
Line 1,742:
=={{header|Forth}}==
{{trans|Go}}
<
: sq dup * ;
: 5^ dup sq sq * ;
Line 1,779:
euler
bye
</syntaxhighlight>
{{out}}
<pre>
Line 1,791:
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,811:
6 CONTINUE
300 FORMAT(5(1X,I3))
END </
{{out}}
<pre>
Line 1,819:
===Fortran 95===
{{works with|Fortran|95 and later}}
<
implicit none
Line 1,847:
end do outer
end program</
{{out}}
<pre> 27 84 110 133 144</pre>
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 1,908:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>
Line 1,914:
=={{header|Go}}==
{{trans|Python}}
<
import (
Line 1,949:
log.Fatal("no solution")
return
}</
{{output}}
<pre>
Line 1,957:
=={{header|Groovy}}==
{{trans|Java}}
<
static final int MAX_NUMBER = 250
Line 1,984:
}
}
}</
{{out}}
<pre>27^5 + 84^5 + 110^5 + 133^5 + 144^5</pre>
=={{header|Haskell}}==
<
import Data.List.Ordered
Line 2,010:
-- which power of 5 is sum ?
let Just x4 = elemIndex p5Sum p5List ]</
{{output}}
<pre>
Line 2,018:
Or, using dictionaries of powers and sums, and thus rather faster:
{{Trans|Python}}
<
import Data.List (find, intercalate)
import Data.Maybe (maybe)
Line 2,070:
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 2,078:
=={{header|J}}==
<
(#~ (= <.)@((+/"1)&.:(^&5)))1+4 comb 248
27 84 110 133</
Explanation:
<syntaxhighlight lang
Then, <
Only one possibility remains.
Line 2,092:
Here's a significantly faster approach (about 100 times faster), based on the echolisp implementation:
<
y=. 250
n=. i.y
Line 2,103:
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 2,117:
{{trans|ALGOL 68}}
Tested with Java 6.
<
{
Line 2,160:
} // main
} // eulerSopConjecture</
Output:
<pre>
Line 2,168:
=={{header|JavaScript}}==
===ES5===
<
var aPow5 = [];
Line 2,203:
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 2,226:
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 2,246:
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 2,265:
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 2,291:
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,303:
===ES6===
====Procedural====
<
'use strict';
Line 2,343:
.join(' + ') + ` = ${soln[4]}^5` : 'No solution found.'
})();</
{{Out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>
Line 2,351:
{{Trans|Python}}
{{Trans|Haskell}}
<
'use strict';
Line 2,596:
// MAIN ---
return main();
})();</
{{Out}}
<pre>Counter-example found:
Line 2,605:
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,631:
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,662:
println("A solution is ", s, " = ", @sprintf("%d^%d", y, pwr), ".")
end
</syntaxhighlight>
{{out}}
Line 2,670:
=={{header|Kotlin}}==
<
val p5 = LongArray(250){ it.toLong() * it * it * it * it }
var sum: Long
Line 2,688:
}
if (!found) println("No solution was found")
}</
{{out}}
Line 2,697:
=={{header|Lua}}==
Brute force but still takes under two seconds with LuaJIT.
<
function binarySearch (t, n)
local start, stop, mid = 1, #t
Line 2,738:
else
print("Looks like he was right after all...")
end</
{{out}}
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5
Line 2,744:
=={{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|Microsoft Small Basic}}==
<
'find: x1^5+x2^5+x3^5+x4^5=x5^5
'-> x1=27 x2=84 x3=110 x4=133 x5=144
Line 2,782:
EndFor 'x2
EndFor 'x1
EndPgrm: </
{{out}}
<pre>Found!
Line 2,790:
=={{header|Modula-2}}==
{{output?|Modula-2}}
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 2,829:
WriteLn;
ReadChar
END EulerConjecture.</
=={{header|Nim}}==
{{trans|PureBasic}}
<syntaxhighlight lang="nim">
# Brute force approach
Line 2,877:
if y == 0 :
echo "No solution was found"
</syntaxhighlight>
{{out}}
Line 2,887:
=={{header|Oforth}}==
<
| i j k l ip jp kp |
250 loop: i [
Line 2,900:
]
]
] ;</
{{out}}
Line 2,910:
=={{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,924:
)
)
}</
{{out}}
<pre>144 [27, 84, 110, 133]</pre>
Line 2,931:
{{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,963:
end;
END.
</syntaxhighlight>
;output:
<pre>
Line 2,972:
=={{header|Perl}}==
Brute Force:
<
my @p5 = (0,map { $_**5 } 1 .. MAX-1);
my $s = 0;
Line 2,985:
}
}
}</
{{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 3,008:
}
}
}</
=={{header|Phix}}==
Line 3,015:
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.
<!--<
<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>
Line 3,052:
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
<!--</
{{out}}
<pre>
Line 3,062:
=={{header|PHP}}==
{{trans|Python}}
<
function eulers_sum_of_powers () {
Line 3,094:
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 =>
Line 3,105:
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>
Line 3,111:
=={{header|PicoLisp}}==
<
(off S)
Line 3,135:
(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 3,142:
'''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 3,164:
}
}
}</
{{Out}}
<pre>PS > measure-command { .\euler.ps1 | out-default }
Line 3,179:
=={{header|Prolog}}==
<
makepowers :-
retractall(pow5(_, _)),
Line 3,200:
Y_5th is X0_5th + X1_5th + X2_5th + X3_5th,
pow5(Y, Y_5th).
</syntaxhighlight>
{{out}}
<pre>
Line 3,212:
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">
EnableExplicit
Line 3,262:
CloseConsole()
EndIf
</syntaxhighlight>
{{out}}
Line 3,271:
=={{header|Python}}==
===Procedural===
<
max_n = 250
pow_5 = [n**5 for n in range(max_n)]
Line 3,284:
return (x0, x1, x2, x3, y)
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</
{{out}}
Line 3,291:
The above can be written as:
{{works with|Python|2.6+}}
<
def eulers_sum_of_powers():
Line 3,303:
return (x0, x1, x2, x3, y)
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</
{{out}}
Line 3,309:
It's much faster to cache and look up sums of two fifth powers, due to the small allowed range:
<
p5, sum2 = {}, {}
Line 3,323:
if p - s in sum2:
print(p5[p], sum2[s] + sum2[p-s])
exit()</
{{out}}
<pre>144 (27, 84, 110, 133)</pre>
Line 3,329:
===Composition of pure functions===
{{Works with|Python|3.7}}
<
from itertools import (chain, takewhile)
Line 3,440:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Euler's sum of powers conjecture – counter-example:
Line 3,460:
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.
<
1 CLS
2 DIM i%(255,6) : DIM a%(6) : DIM c%(6)
Line 3,496:
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
Line 3,504:
=={{header|Racket}}==
{{trans|C++}}
<
(define MAX 250)
(define pow5 (make-vector MAX))
Line 3,521:
(when (set-member? pow5s sum)
(displayln (list x0 x1 x2 x3 (inexact->exact (round (expt sum 1/5)))))
(break))))</
{{output}}
<pre>
Line 3,530:
(formerly Perl 6)
{{Works with|rakudo|2018.10}}
{{trans|Python}}<syntaxhighlight lang="raku"
my %po5{Int};
Line 3,551:
}
}
}</
{{out}}
<pre>27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵</pre>
Line 3,581:
:* [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,617:
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,688:
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,733:
/*──────────────────────────────────────────────────────────────────────────────────────*/
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,944:
=={{header|Ring}}==
<
# Project : Euler's sum of powers conjecture
Line 3,961:
next
next
</syntaxhighlight>
Output:
<pre>
Line 3,969:
=={{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,979:
Faster version:
{{trans|Python}}
<
(1..max).each do |i|
p5[i**5] = i
Line 3,993:
end
end
result.each{|k,v| puts k.map{|i| "#{i}**5"}.join(' + ') + " = #{v}**5"}</
The output is the same above.
=={{header|Run BASIC}}==
<
max=250
FOR w = 1 TO max
Line 4,012:
NEXT y
NEXT x
NEXT w</
<pre>
133^5 + 110^5 + 84^5 + 27^5 = 144^5
Line 4,018:
=={{header|Rust}}==
<
fn eulers_sum_of_powers() -> (usize, usize, usize, usize, usize) {
Line 4,043:
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 4,049:
=={{header|Scala}}==
===Functional programming===
<
object EulerSopConjecture extends App {
Line 4,068:
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 4,127:
writeln("No solution was found");
end if;
end func;</
{{out}}
Line 4,135:
=={{header|SenseTalk}}==
<
to findEulerSumOfPowers
set MAX_NUMBER to 250
Line 4,156:
end repeat
end repeat
end findEulerSumOfPowers</
=={{header|Sidef}}==
{{trans|Raku}}
<
var p5 = Hash()
Line 4,183:
say "#{t} = #{p5{p}}⁵"
break
}</
{{out}}
<pre>
Line 4,193:
{{trans|Rust}}
<
@inlinable
public func power(_ n: Self) -> Self {
Line 4,223:
let (x0, x1, x2, x3, y) = sumOfPowers()
print("\(x0)^5 + \(x1)^5 + \(x2)^5 \(x3)^5 = \(y)^5")</
{{out}}
Line 4,230:
=={{header|Tcl}}==
<
## NB: $badx is exclusive upper limit, and also limits y!
for {set y 1} {$y < $badx} {incr y} {
Line 4,257:
puts "search complete (x < $badx)"
}
doit</
{{out}}
144^5 = 133^5 + 110^5 + 84^5 + 27^5
Line 4,269:
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.
<
pow5=()
for (( i=1; i<MAX; ++i )); do
Line 4,297:
done
printf 'No examples found.\n'
exit 1</
{{Out}}
Line 4,311:
=={{header|VBA}}==
{{trans|AWK}}<
Public Sub begin()
start_int = GetTickCount()
Line 4,335:
Next x1
Next x0
End Sub</
<pre>33^5 + 110^5 + 84^5 + 27^5 = 144
160,187 seconds</pre>
Line 4,341:
=={{header|VBScript}}==
{{trans|ERRE}}
<
For X0=1 To Max
Line 4,360:
Function fnP5(n)
fnP5 = n ^ 5
End Function</
{{out}}
Line 4,367:
=={{header|Visual Basic .NET}}==
===Paired Powers Algorithm===
{{trans|Python}}<
Structure Pair
Line 4,419:
If Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
End Module</
{{out}}(No command line arguments)
<pre>Checking from 1 to 250...
Line 4,445:
===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.
<
Structure Pair
Line 4,578:
If Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
End Module</
{{out}}(No command line arguments)<pre>Paired powers, checking from 1 to 250...
27^5 + 84^5 + 110^5 + 133^5 = 144^5
Line 4,684:
=={{header|Wren}}==
{{trans|C}}
<
var n = 250
var m = 30
Line 4,721:
}
}
}</
{{out}}
Line 4,732:
=={{header|XPL0}}==
Runs in 50.3 seconds on Pi4.
<
int N;
real X, P;
Line 4,758:
];
];
]</
{{out}}
Line 4,767:
=={{header|Zig}}==
{{trans|Go}}
<syntaxhighlight lang="zig">
const std = @import("std");
const stdout = std.io.getStdOut().outStream();
Line 4,798:
try stdout.print("Sorry, no solution found.\n", .{});
}
</syntaxhighlight>
{{Out}}
<pre>
Line 4,805:
=={{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,813:
.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,831:
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>
Line 4,852:
on any ZX Spectrum, despite being limited to 32-bit precision.
<
1 CLS
2 DIM k(29): DIM q(249)
Line 4,887:
90 NEXT z: NEXT y: NEXT x: NEXT w
100 DEF FN f(e,n)=e- INT(e/n)*n
</syntaxhighlight>
{{out}}
<pre>
|