Problem 141
completed February 9, 2021Comments
This is officially the “hardest” problem I’ve completed! The site claims that
it is difficultly level 60%. Previously, the most difficult problems I was
able to complete were level 55%. This really makes me feel like I can do
anything if I just put my mind to it. I am so loving these problems.
This problem just required a little bit of algebra and poking around. A few things stood out. First, it is required that 0 < r < q < d < n. It is also possible that 0 < r < d < q < n, but I found that choosing either leads to the same result. From there it was just a matter of doing some algebra and realizing that r must be a divisor of n**2.
Code
def memoize(fn):
_cache = {}
def wrap(n):
if n in _cache:
return _cache[n]
ret = fn(n)
_cache[n] = ret
return ret
return wrap
def divisors_factory(n):
top = int(n ** 0.5)
sieve = [False, False] + [True] * (top - 1)
primes = []
for p, isprime in enumerate(sieve):
if not isprime:
continue
primes.append(p)
num = p + p
while num <= top:
sieve[num] = True
num += p
@memoize
def _divisors(n):
if n == 1:
return []
orig = n
stop = n ** 0.5
for p in primes:
if p > stop:
return [1]
if n % p == 0:
n //= p
e = 1
while n % p == 0:
n //= p
e += 1
divs = _divisors(n)
return [
d*p**exp
for exp in range(4*e+1)
for d in divs
if d*p**exp < orig
]
return [1]
return _divisors
def solve(n):
third = 1 / 3
total, m, num = 0, 1, 1
divs = divisors_factory(n ** 0.5)
while num < n:
for r in divs(m):
d3 = (num ** 2 // r) - 2 * num + r
c = int(d3**third)
if c**3 == d3 or (c + 1)**3 == d3:
total += num
break
m += 1
num = m ** 2
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
Tests
import pytest
from problem import solve
_test_solve = (
(10**1, 9),
(10**2, 9),
(10**3, 9),
(10**4, 9),
(10**5, 124657),
(10**6, 700738),
(10**7, 14253190),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)