Last active
August 13, 2022 09:23
-
-
Save jorpic/5c4b9ff7248c44a957c388555ffe4ffa to your computer and use it in GitHub Desktop.
Calculate funny sums of cubes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 166**3 + 500**3 + 333**3 = 166 500 333 | |
# 296**3 + 584**3 + 415**3 = 296 584 415 | |
# 710**3 + 656**3 + 413**3 = 710 656 413 | |
# 828**3 + 538**3 + 472**3 = 828 538 472 | |
# Executed in 18.47 mins | |
def f1(): | |
for i in range(100, 1000): | |
for j in range(100, 1000): | |
for k in range(100, 1000): | |
s = i ** 3 + j ** 3 + k ** 3 | |
if f'{s}' == f'{i}{j}{k}': | |
print(i, j, k) | |
# Executed in 823.58 secs (13.72 mins) | |
def f2(): | |
for i in range(100, 1000): | |
for j in range(100, 1000): | |
for k in range(100, 1000): | |
s = i ** 3 + j ** 3 + k ** 3 | |
if s % 1000 == k and f'{s}' == f'{i}{j}{k}': | |
print(i, j, k) | |
# Executed in 748.55 secs | |
def f3(): | |
for i in range(100, 1000): | |
for j in range(100, 1000): | |
for k in range(100, 1000): | |
s = i ** 3 + j ** 3 + k ** 3 | |
x = s % 1000 | |
if x == k: | |
y = (s // 1000) % 1000 | |
if y == j: | |
z = s // 1000000 | |
if z == i: | |
print(i, j, k) | |
# Executed in 201.55 secs | |
def f4(): | |
for i in range(100, 1000): | |
for j in range(i, 1000): | |
for k in range(j, 1000): | |
s = i ** 3 + j ** 3 + k ** 3 | |
x = s % 1000 | |
y = (s // 1000) % 1000 | |
z = s // 1000000 | |
if x ^ y ^ z ^ i ^ j ^ k == 0 and x + y + z == i + j + k: | |
p = min(x, y, z) | |
r = max(x, y, z) | |
q = x ^ y ^ z ^ p ^ r | |
if p == i and q == j and r == k: | |
print(z, y, x) | |
# Executed in 94.12 secs | |
def f5(): | |
from array import array | |
qb = array('L', [i**3 for i in range(0, 1000)]) | |
for i in range(100, 1000): | |
si = qb[i] | |
for j in range(i, 1000): | |
sj = si + qb[j] | |
for k in range(j, 1000): | |
s = sj + qb[k] | |
x = s % 1000 | |
y = (s // 1000) % 1000 | |
z = s // 1000000 | |
if x ^ y ^ z ^ i ^ j ^ k == 0 and x + y + z == i + j + k: | |
p = min(x, y, z) | |
r = max(x, y, z) | |
q = x ^ y ^ z ^ p ^ r | |
if p == i and q == j and r == k: | |
print(z, y, x) | |
# Executed in 51.85 secs | |
def f6(): | |
from array import array | |
qb = array('L', [i**3 for i in range(0, 1000)]) | |
for i in range(100, 1000): | |
si = qb[i] | |
for j in range(i, 1000): | |
sj = si + qb[j] | |
for k in range(j, 1000): | |
s = sj + qb[k] | |
x = s % 1000 | |
y = (s // 1000) % 1000 | |
z = s // 1000000 | |
if z < 1000 and x ^ y ^ z ^ i ^ j ^ k == 0 and x + y + z == i + j + k: | |
if qb[x] + qb[y] + qb[z] == s: | |
print(z, y, x) | |
# Executed in 31.06 secs | |
def f7(): | |
from math import floor | |
from array import array | |
qb = array('L', [i**3 for i in range(0, 1000)]) | |
# We iterate over ordered triples i >= j >= k. | |
# But i can't be too small or we will get a result with less than 9 digits. | |
min_i = floor((10**8 / 3) ** (1/3)) | |
# i can't be too big either. | |
# E.g. i = 999 => 999**3 + j**2 + k**3 > 997_002_999 | |
# We will get overflow (10 digits in a result) if the first triple is too large: | |
# i = 999, j >= 997, s > 999**3 + 997**3 > 10**9 | |
max_i = next( | |
i for i in range(999, min_i, -1) if qb[qb[i] // 10**6] + qb[i] < 10**9) | |
# (min_i, max_i) = (321, 880) | |
for i in range(min_i, max_i+1): | |
si = qb[i] | |
# The same reasoning as above: | |
# when i is small, we need j and k be large enough to fill 9 digits. | |
min_j = floor(((10**8 - si) / 2) ** (1/3)) if si < 10**8 else 100 | |
for j in range(min_j, i+1): | |
sj = si + qb[j] | |
for k in range(100, j+1): | |
s = sj + qb[k] | |
x = s % 1000 | |
y = (s // 1000) % 1000 | |
z = s // 1000000 | |
if z < 1000 and x ^ y ^ z ^ i ^ j ^ k == 0 and x + y + z == i + j + k: | |
if qb[x] + qb[y] + qb[z] == s: | |
print(z, y, x) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment