For a while I was choosing problems based on their difficulty percentage. The last few days I’ve been doing them based on the number of people who have completed them. Seems like that is a better predictor of the difficulty of a problem for me.
I started with a basic, slow brute force implementation. This allowed me to print out values of A(n) that were the largest yet seen. I noticed pretty quickly that all these values of n were either divisible by 3 or prime.
From there it was just a matter of creating and testing the repunits. The most time consuming things for this were creating the repunits and doing the division. To speed things up, I applied the modulo as I went. Runs in under a second.
def isprime(n):
for p in range(7, int(n**0.5) + 1, 2):
if n % p == 0:
return False
return True
def solve(m):
n = m - 1
while True:
n += 2
if n % 5 == 0:
n += 2
if n % 3 == 0 or isprime(n):
k = r = 1
while r != 0:
r = (r * 10 + 1) % n
k += 1
if k > m:
return n
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(10, 17),
(20, 23),
(30, 47),
(40, 47),
(50, 59),
(60, 69),
(70, 81),
(80, 81),
(90, 97),
(10**2, 109),
(10**3, 1017),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)