Rosetta Code

Euler's sum of powers conjecture: Difference between revisions

Page Discussion

Euler's sum of powers conjecture (view source)

Revision as of 14:13, 17 February 2024

8,570 bytes added ,  3 months ago
→‎Second version
(Initial FutureBasic task solution added)
imported>Pigeon768
 
(6 intermediate revisions by 4 users not shown)
Line 770:
{{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}}===
Line 869 ⟶ 890:
-> 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}}===
Line 1,943 ⟶ 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 2,277 ⟶ 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 .
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
call y = search x0 sum y
if y >= 0
print x0 & " " & x1 & " " & x2 & " " & x3 & " " & y
break 4
.
.
.
.
.
.
.
</syntaxhighlight>
Line 4,927 ⟶ 5,065:
{{out}}
<pre>133 110 84 27 144</pre>
 
=={{header|Visual Basic .NET}}==
{{works with|Visual Basic .NET|2011}}
<syntaxhighlight lang="vbnet">' Euler's sum of powers of 4 conjecture - Patrice Grandin - 17/05/2020
 
' x1^4 + x2^4 + x3^4 + x4^4 = x5^4
 
' Project\Add reference\Assembly\Framework System.Numerics
Imports System.Numerics 'BigInteger
 
Public Class EulerPower4Sum
 
Private Sub MyForm_Load(sender As Object, e As EventArgs) Handles MyBase.Load
Dim t1, t2 As DateTime
t1 = Now
EulerPower45Sum() '16.7 sec
'EulerPower44Sum() '633 years !!
t2 = Now
Console.WriteLine((t2 - t1).TotalSeconds & " sec")
End Sub 'Load
 
Private Sub EulerPower45Sum()
'30^4 + 120^4 + 272^4 + 315^4 = 353^4
Const MaxN = 360
Dim i, j, i1, i2, i3, i4, i5 As Int32
Dim p4(MaxN), n, sumx As Int64
Debug.Print(">EulerPower45Sum")
For i = 1 To MaxN
n = 1
For j = 1 To 4
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 EulerPower44Sum()
'95800^4 + 217519^4 + 414560^4 = 422481^4
Const MaxN = 500000 '500000^4 => decimal(23) => binary(76) !!
Dim i, j, i1, i2, i3, i4 As Int32
Dim p4(MaxN), n, sumx As BigInteger
Dim t0 As DateTime
Debug.Print(">EulerPower44Sum")
For i = 1 To MaxN
n = 1
For j = 1 To 4
n *= i
Next j
p4(i) = n
Next i
t0 = Now
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="ecmascriptwren">var start = System.clock
var n = 250
var m = 30
Line 4,970 ⟶ 5,203:
 
{{out}}
Timing is for an Intel Core i7-8565U machine running Wren 0.24.0 on Ubuntu 1822.04.
<pre>
27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵
Took 67.836934168733 seconds
</pre>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340622...352675"