Anonymous user
Euler's sum of powers conjecture: Difference between revisions
Euler's sum of powers conjecture (view source)
Revision as of 14:13, 17 February 2024
, 3 months ago→Second version
imported>Pigeon768 |
|||
| (3 intermediate revisions by 3 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
.
y = -1
b = n
while a + 1 < b
i = (a + b) div 2
if p5[i + 1] > s
b = i
elif p5[i + 1] < s
a = i
else
a = b
y = i
.
.
return y
.
for x0 = 0 to n - 1
for x1 = 0 to x0
sum1 = p5[x0 + 1] + p5[x1 + 1]
for x2 = 0 to x1
sum2 = p5[x2 + 1] + sum1
for x3 = 0 to x2
sum = p5[x3 + 1] + sum2
if h5[sum mod 65537 + 1] = 1
if y >= 0
print x0 & " " & x1 & " " & x2 & " " & x3 & " " & y
break 4
.
.
.
.
.
</syntaxhighlight>
Line 5,025 ⟶ 5,163:
=={{header|Wren}}==
{{trans|C}}
<syntaxhighlight lang="
var n = 250
var m = 30
Line 5,065 ⟶ 5,203:
{{out}}
Timing is for an Intel Core i7-8565U machine running Wren 0.
<pre>
27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵
Took
</pre>
| |||