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.