A very interestng problem! It was cool that there were almost two problems in one here. The first was how to determine if a fraction is terminating or non-terminating. It ends up that as long as the denominator is coprime to all primes except for 2 and 5, then the fraction is terminating. Second, it ends up that finding large powers of large numbers is hard. Who knew. Eventually for Pypy3 when we get to n=1930 calculating P overflows. The solution for that was to take the logorithm of P. This is allowed because we do not need the actual value of P, we just need to be able to compare it to other P’s. Therefore, as long as the function we apply to P is continuously increasing, the values for P will maintain their size comparison.
Code runs in about 300 milliseconds.
import math
def gcd(a, b):
while b:
a, b = b, a % b
return a
def solve(n):
total = 0
for k in range(5, n + 1):
top_p = top_j = 0
for j in range(1, k + 1):
split = j * math.log10(k / j)
if split > top_p:
top_p = split
top_j = j
else:
break
top_j //= gcd(k, top_j)
while top_j % 2 == 0:
top_j //= 2
while top_j % 5 == 0:
top_j //= 5
if top_j == 1:
total -= k
else:
total += k
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(100, 2438),
(1000, 452936),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)
_test_not_solve = (
(2000, 1839106),
(3000, 4135506),
(4000, 7461508),
(5000, 11219942),
(6000, 16393680),
(7000, 21999104),
(8000, 28138658),
(9000, 36265688),
(10000, 48506996),
(10000, 45176320),
(10000, 49417322),
(10000, 45410190),
(10000, 45609938),
)
@pytest.mark.parametrize('n,expect', _test_not_solve)
def test_not_solve(n, expect):
assert expect != solve(n)