Another repunits problem! I chose it because I’ve already done I think two other repunit related problems in the last couple of days so I figured I would have some good context on it.
When prime p is not 2 or 5, there will always be a value \(i\) that divides \(R(10^n)\). In fact, if \(i\) divides \(R(10^n)\) then so does \(2i\) and \(3i\), etc. It is possible to find the period by finding the first value of i that divides any length repunit. From there, if the value of this period is only divisible by 2 or 5, then we know that multiplying it enough times by a constant, we will eventually reach a power of 10.
def solve(n):
total = 0
sieve = [True] * (n + 1)
for p, isprime in enumerate(sieve):
if not isprime or p < 2:
continue
num = p + p
while num <= n:
sieve[num] = False
num += p
if p == 2 or p == 5:
total += p
continue
i = r = 1
while r != 0:
i += 1
r = (r * 10 + 1) % p
while i % 2 == 0:
i //= 2
while i % 5 == 0:
i //= 5
if i != 1:
total += p
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(100, 1060 - (11 + 17 + 41 + 73)),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)