This problem is quite simple to solve if you actually try to prove the claim given to you.
Notably, if we want to find an n such that k > 1,000,000 then n itself must be greater than 1,000,000.
The algorithm itself is very simple, I start from a million and I just generate repunits until I find the first one that is divisible by n, if it's greater than 1,000,000 then I stop. Either use the pow function in python (See Problem 132 for more detailed explanation), or remember that R(k+1) = 10*R(k) + 1, and notably R(k+1) mod n = 10*(R(k) mod n) + 1 to keep it smaller.
Enter a number (yourinput)
Code will output the least value of n for which A(n) first exceeds yourinput