Problem 129

completed January 18, 2021

Comments

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.

Code

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))

Tests

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)