This problem was actually pretty simple and I was able to get it in just a couple hours of work. I was able to create all the repunits below 10**8 pretty easily. It would have worked fine but probably needed to run for about an hour or more. From looking at the output of this slower version, I noticed that all the strong repunits were found very very early on, and all the last ones searched were numbers that had only a single repunit representation. I figured if I exited early I’d be able to save a lot of time. I implemented that quickly, the tests passed, then I ran the program. Runs in about a half second on pypy3 and a second and a half on python3.
def solve(top):
repunits = {}
for base in range(2, top):
num = base + 1
exp = 1
while num < top:
repunits[num] = repunits.get(num, 0) + 1
exp += 1
num += base ** exp
if exp == 2:
break
return sum(k for k, v in repunits.items() if v > 1 or k > base+1) + 1
if __name__ == '__main__':
import sys
n = int(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(10 ** 1, 8),
(10 ** 2, 540),
(10 ** 3, 15864),
(10 ** 4, 450740),
(10 ** 5, 12755696),
(10 ** 6, 372810163),
(10 ** 7, 11302817869),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)