I never did get working tests for this problem. I got caught up in whether or not to include numbers like 11111 in the sum. Until the very end I excluded them. But after getting the wrong answer so many times, I attempted including them to see what happened. Yup, right answer. I would have preferred to have an example sum to work off of.
Reading through the threads after completing the problem, it looks like I approached this in a very very different way from most people. This problem seems incredibly similar to Problem 358 in that they both give the number 142857 as an example of a cyclic number. Therefore, I attempted to go about this problem in a similar way.
I knew that full cyclic numbers, like 142857, are the results of taking the inverse of full reptend primes. Since I was looking for kinda cyclic numbers, I figured I could start by looking at inverses of numbers and their decimal expansions.
I spent a long time trying to figure out the most efficient way to get the repeating part of these repeating decimals. I settled on using the multiplicative order which gave me the benefit of providing both the period and the repeating part all in one algorithm.
The last step was to take multiples of these numbers and then check if their right rotations fit the requirement. Runs in about 13 seconds with Pypy3.
def solve(digits):
def periodof(k):
r, n, p = 1, 0, 0
while True:
p += 1
d, r = divmod(10 * r, k)
n = n * 10 + d
if r == 1:
break
if p >= digits:
return 0, 0
return p, n
found = {}
for n in range(7, 100000, 2):
period, perdigits = periodof(n)
if period < 6:
continue
tenminus = 10 ** (period - 1)
tenperiod = tenminus * 10
for k in range(1, n):
num = k * perdigits
if num > tenperiod:
break
div, mod = divmod(num, 10)
rot = div + mod * tenminus
if num == rot:
break
if num > tenminus and rot % num == 0:
found[num] = True
for d in range(1, 10):
num = d
for _ in range(digits - 1):
num = 10 * num + d
found[num] = True
return sum(found) % 10**5
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))