Project Euler 358 - Cyclic numbers

Official link: https://projecteuler.net/problem=358

Thought Process

I already knew that cyclic numbers are essentially created from the repeating decimals of 1/p where p is a prime, but if you didn't a quick google search of Cyclic Numbers you find it easily, now using our 2 constraints we can narrow down the search greatly.

1. starts with 00,000,000,137

   • This means that for the prime we are looking for, 0.000,000,001,37 ≤ 1/p ≤ 0.000,000,001,38

   • From this you can easily get a range of around (10**11/138) ≤ p ≤ (10**11/137)

   • You can go through this range and find the primes. I used Fermat's Little Theorem to narrow down which numbers I want to check are actually prime as the is_prime function is very costly.

2. end with 56,789

   • This means that 56,789 * p = 99,999 (mod 100,000) and 56,789 * p + 1 = 0 (mod 100,000)

After combining 1) and 2) I end up with 3 candidate primes and I simply brute force checked if the repeating portion is p-1 digits long, if not it is not cyclic by definition.

There is only one and I found its digit sum, alternatively there is a very elegant way to compute the digit sum of a cyclic number which I show below

Interactive Code

No interactive code for this problem, my code is given below