Euler's sum of powers conjecture: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 29: | Line 29: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F eulers_sum_of_powers() |
||
V max_n = 250 |
V max_n = 250 |
||
V pow_5 = (0 .< max_n).map(n -> Int64(n) ^ 5) |
V pow_5 = (0 .< max_n).map(n -> Int64(n) ^ 5) |
||
Line 44: | Line 44: | ||
V r = eulers_sum_of_powers() |
V r = eulers_sum_of_powers() |
||
print(‘#.^5 + #.^5 + #.^5 + #.^5 = #.^5’.format(r[0], r[1], r[2], r[3], r[4]))</ |
print(‘#.^5 + #.^5 + #.^5 + #.^5 = #.^5’.format(r[0], r[1], r[2], r[3], r[4]))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 52: | 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> |
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. |
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. |
||
< |
<syntaxhighlight lang="360asm"> EULERCO CSECT |
||
USING EULERCO,R13 |
USING EULERCO,R13 |
||
B 80(R15) |
B 80(R15) |
||
Line 171: | Line 171: | ||
BUF DS CL80 |
BUF DS CL80 |
||
YREGS |
YREGS |
||
END </ |
END </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 180: | 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. |
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⁵. |
; positive a,b,c,d,e such that a⁵+b⁵+c⁵+d⁵=e⁵. |
||
Line 379: | Line 379: | ||
putdec5 sum |
putdec5 sum |
||
puts tilabel |
puts tilabel |
||
rts</ |
rts</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 409: | Line 409: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
procedure Sum_Of_Powers is |
procedure Sum_Of_Powers is |
||
Line 484: | Line 484: | ||
Ada.Text_IO.New_Line; |
Ada.Text_IO.New_Line; |
||
end Sum_Of_Powers;</ |
end Sum_Of_Powers;</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre> 27 84 110 133 144 |
<pre> 27 84 110 133 144 |
||
Line 491: | Line 491: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}} |
||
< |
<syntaxhighlight lang="algol68"># max number will be the highest integer we will consider # |
||
INT max number = 250; |
INT max number = 250; |
||
Line 535: | Line 535: | ||
OD |
OD |
||
OD |
OD |
||
OD</ |
OD</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 545: | Line 545: | ||
<br> |
<br> |
||
Algol W integers are 32-bit only, so we simulate the necessary 12 digit arithmetic with pairs of integers. |
Algol W integers are 32-bit only, so we simulate the necessary 12 digit arithmetic with pairs of integers. |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% find a, b, c, d, e such that a^5 + b^5 + c^5 + d^5 = e^5 % |
% 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 % |
% where 1 <= a <= b <= c <= d <= e <= 250 % |
||
Line 673: | Line 673: | ||
found : |
found : |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 683: | Line 683: | ||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang="rebol">eulerSumOfPowers: function [top][ |
||
p5: map 0..top => [& ^ 5] |
p5: map 0..top => [& ^ 5] |
||
Line 701: | Line 701: | ||
] |
] |
||
print eulerSumOfPowers 249</ |
print eulerSumOfPowers 249</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 708: | Line 708: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f EULERS_SUM_OF_POWERS_CONJECTURE.AWK |
# syntax: GAWK -f EULERS_SUM_OF_POWERS_CONJECTURE.AWK |
||
BEGIN { |
BEGIN { |
||
Line 732: | Line 732: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 741: | Line 741: | ||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<syntaxhighlight lang="bcpl"> |
|||
<lang BCPL> |
|||
GET "libhdr" |
GET "libhdr" |
||
Line 769: | Line 769: | ||
RESULTIS 0 |
RESULTIS 0 |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 776: | Line 776: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang="bracmat"> 0:?x0 |
||
& whl |
& whl |
||
' ( 1+!x0:<250:?x0 |
' ( 1+!x0:<250:?x0 |
||
Line 799: | Line 799: | ||
) |
) |
||
) |
) |
||
)</ |
)</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
<pre>x0 133 x1 110 x2 84 x3 27 y 144</pre> |
<pre>x0 133 x1 110 x2 84 x3 27 y 144</pre> |
||
Line 805: | Line 805: | ||
=={{header|C}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="c">// Alexander Maximov, July 2nd, 2015 |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <time.h> |
#include <time.h> |
||
Line 839: | Line 839: | ||
printf("time=%d milliseconds\r\n", (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC)); |
printf("time=%d milliseconds\r\n", (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC)); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{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). |
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: | Line 863: | ||
===Loops=== |
===Loops=== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
namespace EulerSumOfPowers { |
namespace EulerSumOfPowers { |
||
Line 894: | Line 894: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
===Paired Powers, Mod 30, etc...=== |
===Paired Powers, Mod 30, etc...=== |
||
{{trans|vbnet}} |
{{trans|vbnet}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
Line 1,021: | Line 1,021: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}}(no command line arguments)<pre>Mod 30 shortcut with threading, checking from 1 to 250... |
{{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 |
27^5 + 84^5 + 110^5 + 133^5 = 144^5 |
||
Line 1,037: | Line 1,037: | ||
===First version=== |
===First version=== |
||
The simplest brute-force find is already reasonably quick: |
The simplest brute-force find is already reasonably quick: |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iostream> |
#include <iostream> |
||
#include <cmath> |
#include <cmath> |
||
Line 1,076: | Line 1,076: | ||
cout << "time=" << (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC) << " milliseconds\r\n"; |
cout << "time=" << (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC) << " milliseconds\r\n"; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,083: | Line 1,083: | ||
</pre> |
</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: |
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: |
||
< |
<syntaxhighlight lang="cpp"> set<double> pow5s; |
||
for (auto i = 1; i < MAX; i++) |
for (auto i = 1; i < MAX; i++) |
||
{ |
{ |
||
Line 1,090: | Line 1,090: | ||
} |
} |
||
//... |
//... |
||
if (pow5s.find(sum) != pow5s.end())</ |
if (pow5s.find(sum) != pow5s.end())</syntaxhighlight> |
||
This reduces the timing to 125 ms on the same hardware. |
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. |
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. |
||
< |
<syntaxhighlight lang="cpp">bool find() |
||
{ |
{ |
||
const auto MAX = 250; |
const auto MAX = 250; |
||
Line 1,120: | Line 1,120: | ||
// not found |
// not found |
||
return false; |
return false; |
||
}</ |
}</syntaxhighlight> |
||
This reduces the timing to around 25 ms. We could equally well replace rs with an iterator inside pow5; the timing is unaffected. |
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: | 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: |
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: |
||
< |
<syntaxhighlight lang="cpp"> for (auto x3 = 1; x3 < x2; x3++) |
||
{ |
{ |
||
// go straight to the first appropriate x3, mod 30 |
// go straight to the first appropriate x3, mod 30 |
||
Line 1,133: | Line 1,133: | ||
if (x3 >= x2) |
if (x3 >= x2) |
||
break; |
break; |
||
auto sum = s2 + pow5[x3];</ |
auto sum = s2 + pow5[x3];</syntaxhighlight> |
||
With this refinement, the exhaustive search up to MAX=1000 takes 16.9 seconds. |
With this refinement, the exhaustive search up to MAX=1000 takes 16.9 seconds. |
||
Line 1,145: | Line 1,145: | ||
< |
<syntaxhighlight lang="cpp">template<class C_, class LT_> C_ Unique(const C_& src, const LT_& less) |
||
{ |
{ |
||
C_ retval(src); |
C_ retval(src); |
||
Line 1,218: | Line 1,218: | ||
} |
} |
||
return false; |
return false; |
||
}</ |
}</syntaxhighlight> |
||
Thanks, EchoLisp guys! |
Thanks, EchoLisp guys! |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
<syntaxhighlight lang="clojure"> |
|||
<lang Clojure> |
|||
(ns test-p.core |
(ns test-p.core |
||
(:require [clojure.math.numeric-tower :as math]) |
(:require [clojure.math.numeric-tower :as math]) |
||
Line 1,252: | 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 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 |
(println (into #{} (map sort (solve-power-sum 1000 1000))));MAX = 1000, high max-value so all solutions found: Time = 4.8 seconds |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output |
Output |
||
<pre> |
<pre> |
||
Line 1,269: | Line 1,269: | ||
=={{header|COBOL}}== |
=={{header|COBOL}}== |
||
< |
<syntaxhighlight lang="cobol"> |
||
IDENTIFICATION DIVISION. |
IDENTIFICATION DIVISION. |
||
PROGRAM-ID. EULER. |
PROGRAM-ID. EULER. |
||
Line 1,367: | Line 1,367: | ||
END PROGRAM EULER. |
END PROGRAM EULER. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output |
Output |
||
<pre> |
<pre> |
||
Line 1,374: | Line 1,374: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp"> |
||
(ql:quickload :alexandria) |
(ql:quickload :alexandria) |
||
(let ((fifth-powers (mapcar #'(lambda (x) (expt x 5)) |
(let ((fifth-powers (mapcar #'(lambda (x) (expt x 5)) |
||
Line 1,388: | Line 1,388: | ||
(if (member x-sum fifth-powers) |
(if (member x-sum fifth-powers) |
||
(return-from outer (list x0 x1 x2 x3 (round (expt x-sum 0.2))))))))))) |
(return-from outer (list x0 x1 x2 x3 (round (expt x-sum 0.2))))))))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>(133 110 84 27 144)</pre> |
<pre>(133 110 84 27 144)</pre> |
||
Line 1,395: | Line 1,395: | ||
===First version=== |
===First version=== |
||
{{trans|Rust}} |
{{trans|Rust}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.range, std.algorithm, std.typecons; |
||
auto eulersSumOfPowers() { |
auto eulersSumOfPowers() { |
||
Line 1,414: | Line 1,414: | ||
void main() { |
void main() { |
||
writefln("%d^5 + %d^5 + %d^5 + %d^5 == %d^5", eulersSumOfPowers[]); |
writefln("%d^5 + %d^5 + %d^5 + %d^5 == %d^5", eulersSumOfPowers[]); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre> |
<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre> |
||
Line 1,422: | Line 1,422: | ||
===Second version=== |
===Second version=== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="d">void main() { |
||
import std.stdio, std.range, std.algorithm, std.typecons; |
import std.stdio, std.range, std.algorithm, std.typecons; |
||
Line 1,445: | Line 1,445: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>144 Tuple!(uint, uint, uint, uint)(27, 84, 110, 133)</pre> |
<pre>144 Tuple!(uint, uint, uint, uint)(27, 84, 110, 133)</pre> |
||
Line 1,453: | Line 1,453: | ||
{{trans|C++}} |
{{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. |
This solution is a brutal translation of the iterator-based C++ version, and it should be improved to use more idiomatic D Ranges. |
||
< |
<syntaxhighlight lang="d">import core.stdc.stdio, std.typecons, std.math, std.algorithm, std.range; |
||
alias Pair = Tuple!(double, int); |
alias Pair = Tuple!(double, int); |
||
Line 1,530: | Line 1,530: | ||
if (!dPFind(100)) |
if (!dPFind(100)) |
||
printf("Search finished.\n"); |
printf("Search finished.\n"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>133 110 27 84 : 144 |
<pre>133 110 27 84 : 144 |
||
Line 1,550: | Line 1,550: | ||
=={{header|EasyLang}}== |
=={{header|EasyLang}}== |
||
<lang>n = 250 |
<syntaxhighlight lang="text">n = 250 |
||
len p5[] n |
len p5[] n |
||
len h5[] 65537 |
len h5[] 65537 |
||
Line 1,589: | Line 1,589: | ||
. |
. |
||
. |
. |
||
.</ |
.</syntaxhighlight> |
||
=={{header|EchoLisp}}== |
=={{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. |
To speed up things, we search for x0, x1, x2 such as x0^5 + x1^5 + x2^5 = a difference of 5-th powers. |
||
< |
<syntaxhighlight lang="lisp"> |
||
(define dim 250) |
(define dim 250) |
||
Line 1,629: | Line 1,629: | ||
→ (27 84 110 133 144) ;; time 2.8 sec |
→ (27 84 110 133 144) ;; time 2.8 sec |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Euler do |
||
def sum_of_power(max \\ 250) do |
def sum_of_power(max \\ 250) do |
||
{p5, sum2} = setup(max) |
{p5, sum2} = setup(max) |
||
Line 1,661: | Line 1,661: | ||
Enum.each(Euler.sum_of_power, fn {k,v} -> |
Enum.each(Euler.sum_of_power, fn {k,v} -> |
||
IO.puts Enum.map_join(k, " + ", fn i -> "#{i}**5" end) <> " = #{v}**5" |
IO.puts Enum.map_join(k, " + ", fn i -> "#{i}**5" end) <> " = #{v}**5" |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,669: | Line 1,669: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
< |
<syntaxhighlight lang="erre">PROGRAM EULERO |
||
CONST MAX=250 |
CONST MAX=250 |
||
Line 1,695: | Line 1,695: | ||
END FOR |
END FOR |
||
END FOR |
END FOR |
||
END PROGRAM</ |
END PROGRAM</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 1,702: | Line 1,702: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
//Find 4 integers whose 5th powers sum to the fifth power of an integer (Quickly!) - Nigel Galloway: April 23rd., 2015 |
//Find 4 integers whose 5th powers sum to the fifth power of an integer (Quickly!) - Nigel Galloway: April 23rd., 2015 |
||
let G = |
let G = |
||
Line 1,718: | Line 1,718: | ||
| _ -> gng(n,i,g,e+1) |
| _ -> gng(n,i,g,e+1) |
||
gng (1, 1, 1, 1) |
gng (1, 1, 1, 1) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,726: | Line 1,726: | ||
=={{header|Factor}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="factor">USING: arrays backtrack kernel literals math.functions |
||
math.ranges prettyprint sequences ; |
math.ranges prettyprint sequences ; |
||
Line 1,734: | Line 1,734: | ||
250 xn xn xn xn drop 4array dup pow5 nths sum dup pow5 |
250 xn xn xn xn drop 4array dup pow5 nths sum dup pow5 |
||
member? [ pow5 index suffix . ] [ 2drop fail ] if</ |
member? [ pow5 index suffix . ] [ 2drop fail ] if</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,742: | Line 1,742: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="forth"> |
||
: sq dup * ; |
: sq dup * ; |
||
: 5^ dup sq sq * ; |
: 5^ dup sq sq * ; |
||
Line 1,779: | Line 1,779: | ||
euler |
euler |
||
bye |
bye |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,791: | 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. |
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. |
And Leon J. Lander and Thomas R. Parkin used the CDC6600. |
||
< |
<syntaxhighlight lang="fortran">C EULER SUM OF POWERS CONJECTURE - FORTRAN IV |
||
C FIND I1,I2,I3,I4,I5 : I1**5+I2**5+I3**5+I4**5=I5**5 |
C FIND I1,I2,I3,I4,I5 : I1**5+I2**5+I3**5+I4**5=I5**5 |
||
INTEGER I,P5(250),SUMX |
INTEGER I,P5(250),SUMX |
||
Line 1,811: | Line 1,811: | ||
6 CONTINUE |
6 CONTINUE |
||
300 FORMAT(5(1X,I3)) |
300 FORMAT(5(1X,I3)) |
||
END </ |
END </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,819: | Line 1,819: | ||
===Fortran 95=== |
===Fortran 95=== |
||
{{works with|Fortran|95 and later}} |
{{works with|Fortran|95 and later}} |
||
< |
<syntaxhighlight lang="fortran">program sum_of_powers |
||
implicit none |
implicit none |
||
Line 1,847: | Line 1,847: | ||
end do outer |
end do outer |
||
end program</ |
end program</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 27 84 110 133 144</pre> |
<pre> 27 84 110 133 144</pre> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' version 14-09-2015 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,908: | Line 1,908: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre> |
<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre> |
||
Line 1,914: | Line 1,914: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,949: | Line 1,949: | ||
log.Fatal("no solution") |
log.Fatal("no solution") |
||
return |
return |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 1,957: | Line 1,957: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="groovy">class EulerSumOfPowers { |
||
static final int MAX_NUMBER = 250 |
static final int MAX_NUMBER = 250 |
||
Line 1,984: | Line 1,984: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>27^5 + 84^5 + 110^5 + 133^5 + 144^5</pre> |
<pre>27^5 + 84^5 + 110^5 + 133^5 + 144^5</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List |
||
import Data.List.Ordered |
import Data.List.Ordered |
||
Line 2,010: | Line 2,010: | ||
-- which power of 5 is sum ? |
-- which power of 5 is sum ? |
||
let Just x4 = elemIndex p5Sum p5List ]</ |
let Just x4 = elemIndex p5Sum p5List ]</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 2,018: | Line 2,018: | ||
Or, using dictionaries of powers and sums, and thus rather faster: |
Or, using dictionaries of powers and sums, and thus rather faster: |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
< |
<syntaxhighlight lang="haskell">import qualified Data.Map.Strict as M |
||
import Data.List (find, intercalate) |
import Data.List (find, intercalate) |
||
import Data.Maybe (maybe) |
import Data.Maybe (maybe) |
||
Line 2,070: | Line 2,070: | ||
rangeString :: [Int] -> String |
rangeString :: [Int] -> String |
||
rangeString [] = "[]" |
rangeString [] = "[]" |
||
rangeString (x:xs) = '[' : show x <> " .. " <> show (last xs) <> "]"</ |
rangeString (x:xs) = '[' : show x <> " .. " <> show (last xs) <> "]"</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Euler's sum of powers conjecture – a counter-example in range [1 .. 249]: |
<pre>Euler's sum of powers conjecture – a counter-example in range [1 .. 249]: |
||
Line 2,078: | Line 2,078: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j"> require 'stats' |
||
(#~ (= <.)@((+/"1)&.:(^&5)))1+4 comb 248 |
(#~ (= <.)@((+/"1)&.:(^&5)))1+4 comb 248 |
||
27 84 110 133</ |
27 84 110 133</syntaxhighlight> |
||
Explanation: |
Explanation: |
||
<lang |
<syntaxhighlight lang="j">1+4 comb 248</syntaxhighlight> finds all the possibilities for our four arguments. |
||
Then, < |
Then, <syntaxhighlight lang="j">(#~ (= <.)@((+/"1)&.:(^&5)))</syntaxhighlight> discards the cases we are not interested in. (It only keeps the case(s) where the fifth root of the sum of the fifth powers is an integer.) |
||
Only one possibility remains. |
Only one possibility remains. |
||
Line 2,092: | Line 2,092: | ||
Here's a significantly faster approach (about 100 times faster), based on the echolisp implementation: |
Here's a significantly faster approach (about 100 times faster), based on the echolisp implementation: |
||
< |
<syntaxhighlight lang="j">find5=:3 :0 |
||
y=. 250 |
y=. 250 |
||
n=. i.y |
n=. i.y |
||
Line 2,103: | Line 2,103: | ||
x=. (t e. s)#t |
x=. (t e. s)#t |
||
|.,&<&~./|:(y,y)#:l#~a e. x |
|.,&<&~./|:(y,y)#:l#~a e. x |
||
)</ |
)</syntaxhighlight> |
||
Use: |
Use: |
||
< |
<syntaxhighlight lang="j"> find5'' |
||
┌─────────────┬───┐ |
┌─────────────┬───┐ |
||
│27 84 110 133│144│ |
│27 84 110 133│144│ |
||
└─────────────┴───┘</ |
└─────────────┴───┘</syntaxhighlight> |
||
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. |
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: | Line 2,117: | ||
{{trans|ALGOL 68}} |
{{trans|ALGOL 68}} |
||
Tested with Java 6. |
Tested with Java 6. |
||
< |
<syntaxhighlight lang="java">public class eulerSopConjecture |
||
{ |
{ |
||
Line 2,160: | Line 2,160: | ||
} // main |
} // main |
||
} // eulerSopConjecture</ |
} // eulerSopConjecture</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,168: | Line 2,168: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
===ES5=== |
===ES5=== |
||
< |
<syntaxhighlight lang="javascript">var eulers_sum_of_powers = function (iMaxN) { |
||
var aPow5 = []; |
var aPow5 = []; |
||
Line 2,203: | Line 2,203: | ||
console.log(oResult.i0 + '^5 + ' + oResult.i1 + '^5 + ' + oResult.i2 + |
console.log(oResult.i0 + '^5 + ' + oResult.i1 + '^5 + ' + oResult.i2 + |
||
'^5 + ' + oResult.i3 + '^5 = ' + oResult.iSum + '^5');</ |
'^5 + ' + oResult.i3 + '^5 = ' + oResult.iSum + '^5');</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
133^5 + 110^5 + 84^5 + 27^5 = 144^5 |
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 |
'''This'''{{trans|D}} that verify: a^5 + b^5 + c^5 + d^5 = x^5 |
||
< |
<syntaxhighlight lang="javascript">var N=1000, first=false |
||
var ns={}, npv=[] |
var ns={}, npv=[] |
||
for (var n=0; n<=N; n++) { |
for (var n=0; n<=N; n++) { |
||
Line 2,226: | Line 2,226: | ||
var e='<sup>5</sup>', ep=e+' + ' |
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>') |
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>') |
||
}</ |
}</syntaxhighlight> |
||
'''Or this'''{{trans|C}} that verify: a^5 + b^5 + c^5 + d^5 = x^5 |
'''Or this'''{{trans|C}} that verify: a^5 + b^5 + c^5 + d^5 = x^5 |
||
< |
<syntaxhighlight lang="javascript">var N=1000, first=false |
||
var npv=[], M=30 // x^5 == x modulo M (=2*3*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) |
for (var n=0; n<=N; n+=1) npv[n]=Math.pow(n, 5) |
||
Line 2,246: | Line 2,246: | ||
var e='<sup>5</sup>', ep=e+' + ' |
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>') |
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>') |
||
}</ |
}</syntaxhighlight> |
||
'''Or this'''{{trans|EchoLisp}} that verify: a^5 + b^5 + c^5 = x^5 - d^5 |
'''Or this'''{{trans|EchoLisp}} that verify: a^5 + b^5 + c^5 = x^5 - d^5 |
||
< |
<syntaxhighlight lang="javascript">var N=1000, first=false |
||
var dxs={}, pow=Math.pow |
var dxs={}, pow=Math.pow |
||
for (var d=1; d<=N; d+=1) |
for (var d=1; d<=N; d+=1) |
||
Line 2,265: | Line 2,265: | ||
var e='<sup>5</sup>', ep=e+' + ' |
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>') |
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>') |
||
}</ |
}</syntaxhighlight> |
||
'''Or this'''{{trans|Python}} that verify: a^5 + b^5 = x^5 - (c^5 + d^5) |
'''Or this'''{{trans|Python}} that verify: a^5 + b^5 = x^5 - (c^5 + d^5) |
||
< |
<syntaxhighlight lang="javascript">var N=1000, first=false |
||
var is={}, ipv=[], ijs={}, ijpv=[], pow=Math.pow |
var is={}, ipv=[], ijs={}, ijpv=[], pow=Math.pow |
||
for (var i=1; i<=N; i+=1) { |
for (var i=1; i<=N; i+=1) { |
||
Line 2,291: | Line 2,291: | ||
var e='<sup>5</sup>', ep=e+' + ' |
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>') |
document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>') |
||
}</ |
}</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
Line 2,303: | Line 2,303: | ||
===ES6=== |
===ES6=== |
||
====Procedural==== |
====Procedural==== |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 2,343: | Line 2,343: | ||
.join(' + ') + ` = ${soln[4]}^5` : 'No solution found.' |
.join(' + ') + ` = ${soln[4]}^5` : 'No solution found.' |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre> |
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre> |
||
Line 2,351: | Line 2,351: | ||
{{Trans|Python}} |
{{Trans|Python}} |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 2,596: | Line 2,596: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Counter-example found: |
<pre>Counter-example found: |
||
Line 2,605: | Line 2,605: | ||
This version finds all non-decreasing solutions within the specified bounds, |
This version finds all non-decreasing solutions within the specified bounds, |
||
using a brute-force but not entirely blind approach. |
using a brute-force but not entirely blind approach. |
||
< |
<syntaxhighlight lang="jq"># Search for y in 1 .. maxn (inclusive) for a solution to SIGMA (xi ^ 5) = y^5 |
||
# and for each solution with x0<=x1<=...<x3, print [x0, x1, x3, x3, y] |
# and for each solution with x0<=x1<=...<x3, print [x0, x1, x3, x3, y] |
||
# |
# |
||
Line 2,631: | Line 2,631: | ||
end |
end |
||
else empty |
else empty |
||
end ;</ |
end ;</syntaxhighlight> |
||
'''The task:''' |
'''The task:''' |
||
<lang |
<syntaxhighlight lang="jq">sum_of_powers_conjecture(249)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="sh">$ jq -c -n -f Euler_sum_of_powers_conjecture_fifth_root.jq |
||
[27,84,110,133,144]</ |
[27,84,110,133,144]</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<syntaxhighlight lang="julia"> |
|||
<lang Julia> |
|||
const lim = 250 |
const lim = 250 |
||
const pwr = 5 |
const pwr = 5 |
||
Line 2,662: | Line 2,662: | ||
println("A solution is ", s, " = ", @sprintf("%d^%d", y, pwr), ".") |
println("A solution is ", s, " = ", @sprintf("%d^%d", y, pwr), ".") |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,670: | Line 2,670: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">fun main(args: Array<String>) { |
||
val p5 = LongArray(250){ it.toLong() * it * it * it * it } |
val p5 = LongArray(250){ it.toLong() * it * it * it * it } |
||
var sum: Long |
var sum: Long |
||
Line 2,688: | Line 2,688: | ||
} |
} |
||
if (!found) println("No solution was found") |
if (!found) println("No solution was found") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,697: | Line 2,697: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Brute force but still takes under two seconds with LuaJIT. |
Brute force but still takes under two seconds with LuaJIT. |
||
< |
<syntaxhighlight lang="lua">-- Fast table search (only works if table values are in order) |
||
function binarySearch (t, n) |
function binarySearch (t, n) |
||
local start, stop, mid = 1, #t |
local start, stop, mid = 1, #t |
||
Line 2,738: | Line 2,738: | ||
else |
else |
||
print("Looks like he was right after all...") |
print("Looks like he was right after all...") |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5 |
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5 |
||
Line 2,744: | Line 2,744: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">Sort[FindInstance[ |
||
x0^5 + x1^5 + x2^5 + x3^5 == y^5 && x0 > 0 && x1 > 0 && x2 > 0 && |
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]]]</ |
x3 > 0, {x0, x1, x2, x3, y}, Integers][[1, All, -1]]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{27,84,110,133,144}</pre> |
<pre>{27,84,110,133,144}</pre> |
||
=={{header|Microsoft Small Basic}}== |
=={{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 |
'find: x1^5+x2^5+x3^5+x4^5=x5^5 |
||
'-> x1=27 x2=84 x3=110 x4=133 x5=144 |
'-> x1=27 x2=84 x3=110 x4=133 x5=144 |
||
Line 2,782: | Line 2,782: | ||
EndFor 'x2 |
EndFor 'x2 |
||
EndFor 'x1 |
EndFor 'x1 |
||
EndPgrm: </ |
EndPgrm: </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Found! |
<pre>Found! |
||
Line 2,790: | Line 2,790: | ||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
{{output?|Modula-2}} |
{{output?|Modula-2}} |
||
< |
<syntaxhighlight lang="modula2">MODULE EulerConjecture; |
||
FROM FormatString IMPORT FormatString; |
FROM FormatString IMPORT FormatString; |
||
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
||
Line 2,829: | Line 2,829: | ||
WriteLn; |
WriteLn; |
||
ReadChar |
ReadChar |
||
END EulerConjecture.</ |
END EulerConjecture.</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|PureBasic}} |
{{trans|PureBasic}} |
||
<syntaxhighlight lang="nim"> |
|||
<lang Nim> |
|||
# Brute force approach |
# Brute force approach |
||
Line 2,877: | Line 2,877: | ||
if y == 0 : |
if y == 0 : |
||
echo "No solution was found" |
echo "No solution was found" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,887: | Line 2,887: | ||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang="oforth">: eulerSum |
||
| i j k l ip jp kp | |
| i j k l ip jp kp | |
||
250 loop: i [ |
250 loop: i [ |
||
Line 2,900: | Line 2,900: | ||
] |
] |
||
] |
] |
||
] ;</ |
] ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,910: | Line 2,910: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
Naive script: |
Naive script: |
||
< |
<syntaxhighlight lang="parigp">forvec(v=vector(4,i,[0,250]), if(ispower(v[1]^5+v[2]^5+v[3]^5+v[4]^5,5,&n), print(n" "v)), 2)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>144 [27, 84, 110, 133]</pre> |
<pre>144 [27, 84, 110, 133]</pre> |
||
Naive + caching (<code>setbinop</code>): |
Naive + caching (<code>setbinop</code>): |
||
< |
<syntaxhighlight lang="parigp">{ |
||
v2=setbinop((x,y)->[min(x,y),max(x,y),x^5+y^5],[0..250]); \\ sums of two fifth powers |
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, |
for(i=2,#v2, |
||
Line 2,924: | Line 2,924: | ||
) |
) |
||
) |
) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>144 [27, 84, 110, 133]</pre> |
<pre>144 [27, 84, 110, 133]</pre> |
||
Line 2,931: | Line 2,931: | ||
{{works with|Free Pascal}} |
{{works with|Free Pascal}} |
||
slightly improved.Reducing calculation time by temporary sum and early break. |
slightly improved.Reducing calculation time by temporary sum and early break. |
||
< |
<syntaxhighlight lang="pascal">program Pot5Test; |
||
{$IFDEF FPC} {$MODE DELPHI}{$ELSE]{$APPTYPE CONSOLE}{$ENDIF} |
{$IFDEF FPC} {$MODE DELPHI}{$ELSE]{$APPTYPE CONSOLE}{$ENDIF} |
||
type |
type |
||
Line 2,963: | Line 2,963: | ||
end; |
end; |
||
END. |
END. |
||
</syntaxhighlight> |
|||
</lang> |
|||
;output: |
;output: |
||
<pre> |
<pre> |
||
Line 2,972: | Line 2,972: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Brute Force: |
Brute Force: |
||
< |
<syntaxhighlight lang="perl">use constant MAX => 250; |
||
my @p5 = (0,map { $_**5 } 1 .. MAX-1); |
my @p5 = (0,map { $_**5 } 1 .. MAX-1); |
||
my $s = 0; |
my $s = 0; |
||
Line 2,985: | Line 2,985: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>27 84 110 133 144</pre> |
<pre>27 84 110 133 144</pre> |
||
Adding some optimizations makes it 5x faster with similar output, but obfuscates things. |
Adding some optimizations makes it 5x faster with similar output, but obfuscates things. |
||
{{trans|C++}}< |
{{trans|C++}}<syntaxhighlight lang="perl">use constant MAX => 250; |
||
my @p5 = (0,map { $_**5 } 1 .. MAX-1); |
my @p5 = (0,map { $_**5 } 1 .. MAX-1); |
||
my $rs = 5; |
my $rs = 5; |
||
Line 3,008: | Line 3,008: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 3,015: | 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> |
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. |
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;">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;">MAX</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">250</span> |
||
Line 3,052: | 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> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,062: | Line 3,062: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="php"><?php |
||
function eulers_sum_of_powers () { |
function eulers_sum_of_powers () { |
||
Line 3,094: | Line 3,094: | ||
echo "$n_0^5 + $n_1^5 + $n_2^5 + $n_3^5 = $y^5"; |
echo "$n_0^5 + $n_1^5 + $n_2^5 + $n_3^5 = $y^5"; |
||
?></ |
?></syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre> |
<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre> |
||
=={{header|Picat}}== |
=={{header|Picat}}== |
||
<syntaxhighlight lang="picat"> |
|||
<lang Picat> |
|||
import sat. |
import sat. |
||
main => |
main => |
||
Line 3,105: | Line 3,105: | ||
X[1]**5 #= sum([X[I]**5 : I in 2..5]), |
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]). |
solve(X), printf("%d**5 = %d**5 + %d**5 + %d**5 + %d**5", X[1], X[2], X[3], X[4], X[5]). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>144**5 = 133**5 + 110**5 + 84**5 + 27**5</pre> |
<pre>144**5 = 133**5 + 110**5 + 84**5 + 27**5</pre> |
||
Line 3,111: | Line 3,111: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(off P) |
||
(off S) |
(off S) |
||
Line 3,135: | Line 3,135: | ||
(cadr (lup S (car B))) |
(cadr (lup S (car B))) |
||
(cadr (lup S (- (car A) (car B)))) |
(cadr (lup S (- (car A) (car B)))) |
||
(cdr (lup P (car A))) ) ) ) ) ) ) )</ |
(cdr (lup P (car A))) ) ) ) ) ) ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(27 84 110 133 144)</pre> |
<pre>(27 84 110 133 144)</pre> |
||
Line 3,142: | Line 3,142: | ||
'''Brute Force Search'''<br> |
'''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. |
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. |
||
< |
<syntaxhighlight lang="powershell"># EULER.PS1 |
||
$max = 250 |
$max = 250 |
||
Line 3,164: | Line 3,164: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>PS > measure-command { .\euler.ps1 | out-default } |
<pre>PS > measure-command { .\euler.ps1 | out-default } |
||
Line 3,179: | Line 3,179: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
< |
<syntaxhighlight lang="prolog"> |
||
makepowers :- |
makepowers :- |
||
retractall(pow5(_, _)), |
retractall(pow5(_, _)), |
||
Line 3,200: | Line 3,200: | ||
Y_5th is X0_5th + X1_5th + X2_5th + X3_5th, |
Y_5th is X0_5th + X1_5th + X2_5th + X3_5th, |
||
pow5(Y, Y_5th). |
pow5(Y, Y_5th). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,212: | Line 3,212: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
<syntaxhighlight lang="purebasic"> |
|||
<lang PureBasic> |
|||
EnableExplicit |
EnableExplicit |
||
Line 3,262: | Line 3,262: | ||
CloseConsole() |
CloseConsole() |
||
EndIf |
EndIf |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,271: | Line 3,271: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Procedural=== |
===Procedural=== |
||
< |
<syntaxhighlight lang="python">def eulers_sum_of_powers(): |
||
max_n = 250 |
max_n = 250 |
||
pow_5 = [n**5 for n in range(max_n)] |
pow_5 = [n**5 for n in range(max_n)] |
||
Line 3,284: | Line 3,284: | ||
return (x0, x1, x2, x3, y) |
return (x0, x1, x2, x3, y) |
||
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</ |
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,291: | Line 3,291: | ||
The above can be written as: |
The above can be written as: |
||
{{works with|Python|2.6+}} |
{{works with|Python|2.6+}} |
||
< |
<syntaxhighlight lang="python">from itertools import combinations |
||
def eulers_sum_of_powers(): |
def eulers_sum_of_powers(): |
||
Line 3,303: | Line 3,303: | ||
return (x0, x1, x2, x3, y) |
return (x0, x1, x2, x3, y) |
||
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</ |
print("%i**5 + %i**5 + %i**5 + %i**5 == %i**5" % eulers_sum_of_powers())</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,309: | Line 3,309: | ||
It's much faster to cache and look up sums of two fifth powers, due to the small allowed range: |
It's much faster to cache and look up sums of two fifth powers, due to the small allowed range: |
||
< |
<syntaxhighlight lang="python">MAX = 250 |
||
p5, sum2 = {}, {} |
p5, sum2 = {}, {} |
||
Line 3,323: | Line 3,323: | ||
if p - s in sum2: |
if p - s in sum2: |
||
print(p5[p], sum2[s] + sum2[p-s]) |
print(p5[p], sum2[s] + sum2[p-s]) |
||
exit()</ |
exit()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>144 (27, 84, 110, 133)</pre> |
<pre>144 (27, 84, 110, 133)</pre> |
||
Line 3,329: | Line 3,329: | ||
===Composition of pure functions=== |
===Composition of pure functions=== |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Euler's sum of powers conjecture''' |
||
from itertools import (chain, takewhile) |
from itertools import (chain, takewhile) |
||
Line 3,440: | Line 3,440: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Euler's sum of powers conjecture – counter-example: |
<pre>Euler's sum of powers conjecture – counter-example: |
||
Line 3,460: | 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 |
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. |
overhead cost vis-a-vis contemporaneous computers less sophisticated than a CDC 6600. |
||
< |
<syntaxhighlight lang="qbasic"> |
||
1 CLS |
1 CLS |
||
2 DIM i%(255,6) : DIM a%(6) : DIM c%(6) |
2 DIM i%(255,6) : DIM a%(6) : DIM c%(6) |
||
Line 3,496: | Line 3,496: | ||
95 END FOR k : END FOR z : END FOR y : END FOR x : END FOR w |
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 |
137 DATA 30,97,113,121,125,127,128 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre> |
{{out}}<pre> |
||
Abaci ready |
Abaci ready |
||
Line 3,504: | Line 3,504: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="scheme">#lang racket |
||
(define MAX 250) |
(define MAX 250) |
||
(define pow5 (make-vector MAX)) |
(define pow5 (make-vector MAX)) |
||
Line 3,521: | Line 3,521: | ||
(when (set-member? pow5s sum) |
(when (set-member? pow5s sum) |
||
(displayln (list x0 x1 x2 x3 (inexact->exact (round (expt sum 1/5))))) |
(displayln (list x0 x1 x2 x3 (inexact->exact (round (expt sum 1/5))))) |
||
(break))))</ |
(break))))</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 3,530: | Line 3,530: | ||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{Works with|rakudo|2018.10}} |
{{Works with|rakudo|2018.10}} |
||
{{trans|Python}}<lang |
{{trans|Python}}<syntaxhighlight lang="raku" line>constant MAX = 250; |
||
my %po5{Int}; |
my %po5{Int}; |
||
Line 3,551: | Line 3,551: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵</pre> |
<pre>27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵</pre> |
||
Line 3,581: | Line 3,581: | ||
:* [the left side of the above equation] sum any applicable three integer powers of five |
:* [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 |
:* [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 |
||
< |
<syntaxhighlight lang="rexx">/*REXX program finds unique positive integers for ────────── aⁿ+bⁿ+cⁿ+dⁿ==xⁿ where n=5 */ |
||
parse arg L H N . /*get optional LOW, HIGH, #solutions.*/ |
parse arg L H N . /*get optional LOW, HIGH, #solutions.*/ |
||
if L=='' | L=="," then L= 0 + 1 /*Not specified? Then use the default.*/ |
if L=='' | L=="," then L= 0 + 1 /*Not specified? Then use the default.*/ |
||
Line 3,617: | Line 3,617: | ||
if #<N then return /*return, keep searching for more sols.*/ |
if #<N then return /*return, keep searching for more sols.*/ |
||
exit # /*stick a fork in it, we're all done. */ |
exit # /*stick a fork in it, we're all done. */ |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 3,688: | Line 3,688: | ||
Execution time on a fast PC for computing (alone) for '''23,686''' numbers is exactly '''1.<sup>00</sup>''' seconds. |
Execution time on a fast PC for computing (alone) for '''23,686''' numbers is exactly '''1.<sup>00</sup>''' seconds. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program shows unique positive integers for ────────── aⁿ+bⁿ+cⁿ+dⁿ==xⁿ where n=5 */ |
||
numeric digits 1000 /*ensure enough decimal digs for powers*/ |
numeric digits 1000 /*ensure enough decimal digs for powers*/ |
||
parse arg N oFID . /*obtain optional arguments from the CL*/ |
parse arg N oFID . /*obtain optional arguments from the CL*/ |
||
Line 3,733: | Line 3,733: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ |
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*/</ |
show: if tell then say $; call lineout oFID, $; $=; return /*show and/or write it*/</syntaxhighlight> |
||
{{out|output|text= when using the default input of: <tt> 200 </tt>}} |
{{out|output|text= when using the default input of: <tt> 200 </tt>}} |
||
(Shown at three-quarter size.) |
(Shown at three-quarter size.) |
||
Line 3,944: | Line 3,944: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Euler's sum of powers conjecture |
# Project : Euler's sum of powers conjecture |
||
Line 3,961: | Line 3,961: | ||
next |
next |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 3,969: | Line 3,969: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Brute force: |
Brute force: |
||
< |
<syntaxhighlight lang="ruby">power5 = (1..250).each_with_object({}){|i,h| h[i**5]=i} |
||
result = power5.keys.repeated_combination(4).select{|a| power5[a.inject(:+)]} |
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"}</ |
puts result.map{|a| a.map{|i| "#{power5[i]}**5"}.join(' + ') + " = #{power5[a.inject(:+)]}**5"}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,979: | Line 3,979: | ||
Faster version: |
Faster version: |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="ruby">p5, sum2, max = {}, {}, 250 |
||
(1..max).each do |i| |
(1..max).each do |i| |
||
p5[i**5] = i |
p5[i**5] = i |
||
Line 3,993: | Line 3,993: | ||
end |
end |
||
end |
end |
||
result.each{|k,v| puts k.map{|i| "#{i}**5"}.join(' + ') + " = #{v}**5"}</ |
result.each{|k,v| puts k.map{|i| "#{i}**5"}.join(' + ') + " = #{v}**5"}</syntaxhighlight> |
||
The output is the same above. |
The output is the same above. |
||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang="runbasic"> |
||
max=250 |
max=250 |
||
FOR w = 1 TO max |
FOR w = 1 TO max |
||
Line 4,012: | Line 4,012: | ||
NEXT y |
NEXT y |
||
NEXT x |
NEXT x |
||
NEXT w</ |
NEXT w</syntaxhighlight> |
||
<pre> |
<pre> |
||
133^5 + 110^5 + 84^5 + 27^5 = 144^5 |
133^5 + 110^5 + 84^5 + 27^5 = 144^5 |
||
Line 4,018: | Line 4,018: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">const MAX_N : u64 = 250; |
||
fn eulers_sum_of_powers() -> (usize, usize, usize, usize, usize) { |
fn eulers_sum_of_powers() -> (usize, usize, usize, usize, usize) { |
||
Line 4,043: | Line 4,043: | ||
let (x0, x1, x2, x3, y) = eulers_sum_of_powers(); |
let (x0, x1, x2, x3, y) = eulers_sum_of_powers(); |
||
println!("{}^5 + {}^5 + {}^5 + {}^5 == {}^5", x0, x1, x2, x3, y) |
println!("{}^5 + {}^5 + {}^5 + {}^5 == {}^5", x0, x1, x2, x3, y) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre> |
<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre> |
||
Line 4,049: | Line 4,049: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
===Functional programming=== |
===Functional programming=== |
||
< |
<syntaxhighlight lang="scala">import scala.collection.Searching.{Found, search} |
||
object EulerSopConjecture extends App { |
object EulerSopConjecture extends App { |
||
Line 4,068: | Line 4,068: | ||
println(sop) |
println(sop) |
||
}</ |
}</syntaxhighlight> |
||
{{Out}}Vector(27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵) |
{{Out}}Vector(27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵) |
||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func integer: binarySearch (in array integer: arr, in integer: aKey) is func |
const func integer: binarySearch (in array integer: arr, in integer: aKey) is func |
||
Line 4,127: | Line 4,127: | ||
writeln("No solution was found"); |
writeln("No solution was found"); |
||
end if; |
end if; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,135: | Line 4,135: | ||
=={{header|SenseTalk}}== |
=={{header|SenseTalk}}== |
||
< |
<syntaxhighlight lang="sensetalk">findEulerSumOfPowers |
||
to findEulerSumOfPowers |
to findEulerSumOfPowers |
||
set MAX_NUMBER to 250 |
set MAX_NUMBER to 250 |
||
Line 4,156: | Line 4,156: | ||
end repeat |
end repeat |
||
end repeat |
end repeat |
||
end findEulerSumOfPowers</ |
end findEulerSumOfPowers</syntaxhighlight> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">define range = (1 ..^ 250) |
||
var p5 = Hash() |
var p5 = Hash() |
||
Line 4,183: | Line 4,183: | ||
say "#{t} = #{p5{p}}⁵" |
say "#{t} = #{p5{p}}⁵" |
||
break |
break |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,193: | Line 4,193: | ||
{{trans|Rust}} |
{{trans|Rust}} |
||
< |
<syntaxhighlight lang="swift">extension BinaryInteger { |
||
@inlinable |
@inlinable |
||
public func power(_ n: Self) -> Self { |
public func power(_ n: Self) -> Self { |
||
Line 4,223: | Line 4,223: | ||
let (x0, x1, x2, x3, y) = sumOfPowers() |
let (x0, x1, x2, x3, y) = sumOfPowers() |
||
print("\(x0)^5 + \(x1)^5 + \(x2)^5 \(x3)^5 = \(y)^5")</ |
print("\(x0)^5 + \(x1)^5 + \(x2)^5 \(x3)^5 = \(y)^5")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,230: | Line 4,230: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">proc doit {{badx 250} {complete 0}} { |
||
## NB: $badx is exclusive upper limit, and also limits y! |
## NB: $badx is exclusive upper limit, and also limits y! |
||
for {set y 1} {$y < $badx} {incr y} { |
for {set y 1} {$y < $badx} {incr y} { |
||
Line 4,257: | Line 4,257: | ||
puts "search complete (x < $badx)" |
puts "search complete (x < $badx)" |
||
} |
} |
||
doit</ |
doit</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
144^5 = 133^5 + 110^5 + 84^5 + 27^5 |
144^5 = 133^5 + 110^5 + 84^5 + 27^5 |
||
Line 4,269: | 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. |
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=() |
pow5=() |
||
for (( i=1; i<MAX; ++i )); do |
for (( i=1; i<MAX; ++i )); do |
||
Line 4,297: | Line 4,297: | ||
done |
done |
||
printf 'No examples found.\n' |
printf 'No examples found.\n' |
||
exit 1</ |
exit 1</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 4,311: | Line 4,311: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
{{trans|AWK}}< |
{{trans|AWK}}<syntaxhighlight lang="vb">Public Declare Function GetTickCount Lib "kernel32.dll" () As Long |
||
Public Sub begin() |
Public Sub begin() |
||
start_int = GetTickCount() |
start_int = GetTickCount() |
||
Line 4,335: | Line 4,335: | ||
Next x1 |
Next x1 |
||
Next x0 |
Next x0 |
||
End Sub</ |
End Sub</syntaxhighlight>{{out}} |
||
<pre>33^5 + 110^5 + 84^5 + 27^5 = 144 |
<pre>33^5 + 110^5 + 84^5 + 27^5 = 144 |
||
160,187 seconds</pre> |
160,187 seconds</pre> |
||
Line 4,341: | Line 4,341: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
{{trans|ERRE}} |
{{trans|ERRE}} |
||
< |
<syntaxhighlight lang="vb">Max=250 |
||
For X0=1 To Max |
For X0=1 To Max |
||
Line 4,360: | Line 4,360: | ||
Function fnP5(n) |
Function fnP5(n) |
||
fnP5 = n ^ 5 |
fnP5 = n ^ 5 |
||
End Function</ |
End Function</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,367: | Line 4,367: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
===Paired Powers Algorithm=== |
===Paired Powers Algorithm=== |
||
{{trans|Python}}< |
{{trans|Python}}<syntaxhighlight lang="vbnet">Module Module1 |
||
Structure Pair |
Structure Pair |
||
Line 4,419: | Line 4,419: | ||
If Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
If Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}}(No command line arguments) |
{{out}}(No command line arguments) |
||
<pre>Checking from 1 to 250... |
<pre>Checking from 1 to 250... |
||
Line 4,445: | Line 4,445: | ||
===Paired Powers w/ Mod 30 Shortcut and Threading=== |
===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. |
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 |
Structure Pair |
||
Line 4,578: | Line 4,578: | ||
If Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
If Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}}(No command line arguments)<pre>Paired powers, checking from 1 to 250... |
{{out}}(No command line arguments)<pre>Paired powers, checking from 1 to 250... |
||
27^5 + 84^5 + 110^5 + 133^5 = 144^5 |
27^5 + 84^5 + 110^5 + 133^5 = 144^5 |
||
Line 4,684: | Line 4,684: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="ecmascript">var start = System.clock |
||
var n = 250 |
var n = 250 |
||
var m = 30 |
var m = 30 |
||
Line 4,721: | Line 4,721: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,732: | Line 4,732: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
Runs in 50.3 seconds on Pi4. |
Runs in 50.3 seconds on Pi4. |
||
< |
<syntaxhighlight lang="xpl0">func real Pow5(N); |
||
int N; |
int N; |
||
real X, P; |
real X, P; |
||
Line 4,758: | Line 4,758: | ||
]; |
]; |
||
]; |
]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,767: | Line 4,767: | ||
=={{header|Zig}}== |
=={{header|Zig}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<syntaxhighlight lang="zig"> |
|||
<lang Zig> |
|||
const std = @import("std"); |
const std = @import("std"); |
||
const stdout = std.io.getStdOut().outStream(); |
const stdout = std.io.getStdOut().outStream(); |
||
Line 4,798: | Line 4,798: | ||
try stdout.print("Sorry, no solution found.\n", .{}); |
try stdout.print("Sorry, no solution found.\n", .{}); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 4,805: | Line 4,805: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Uses two look up tables for efficiency. Counts from 0 for ease of coding. |
Uses two look up tables for efficiency. Counts from 0 for ease of coding. |
||
< |
<syntaxhighlight lang="zkl">pow5s:=[1..249].apply("pow",5); // (1^5, 2^5, 3^5 .. 249^5) |
||
pow5r:=pow5s.enumerate().apply("reverse").toDictionary(); // [144^5:144, ...] |
pow5r:=pow5s.enumerate().apply("reverse").toDictionary(); // [144^5:144, ...] |
||
foreach x0,x1,x2,x3 in (249,x0,x1,x2){ |
foreach x0,x1,x2,x3 in (249,x0,x1,x2){ |
||
Line 4,813: | Line 4,813: | ||
.fmt(x3+1,x2+1,x1+1,x0+1,pow5r[sum]+1)); |
.fmt(x3+1,x2+1,x1+1,x0+1,pow5r[sum]+1)); |
||
break(4); // the foreach is actually four loops |
break(4); // the foreach is actually four loops |
||
}</ |
}</syntaxhighlight> |
||
{{out}}<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre> |
{{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. |
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}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="zkl">p5,sum2:=Dictionary(),Dictionary(); |
||
foreach i in ([1..249]){ |
foreach i in ([1..249]){ |
||
p5[i.pow(5)]=i; |
p5[i.pow(5)]=i; |
||
Line 4,831: | Line 4,831: | ||
break(2); // or get permutations |
break(2); // or get permutations |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Note: dictionary keys are always strings and copying a read only list creates a read write list. |
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> |
{{out}}<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre> |
||
Line 4,852: | Line 4,852: | ||
on any ZX Spectrum, despite being limited to 32-bit precision. |
on any ZX Spectrum, despite being limited to 32-bit precision. |
||
< |
<syntaxhighlight lang="zxbasic"> |
||
1 CLS |
1 CLS |
||
2 DIM k(29): DIM q(249) |
2 DIM k(29): DIM q(249) |
||
Line 4,887: | Line 4,887: | ||
90 NEXT z: NEXT y: NEXT x: NEXT w |
90 NEXT z: NEXT y: NEXT x: NEXT w |
||
100 DEF FN f(e,n)=e- INT(e/n)*n |
100 DEF FN f(e,n)=e- INT(e/n)*n |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |