Prob 0026 ‐ Reciprocal Cycles - maccergit/Euler GitHub Wiki

01

One approach is to implement a traditional long-division algorithm in code, and then look to see if any of the steps repeats a previous step. This has the advantage of only using integers, with floor division and modulo being used for the division steps. We basically use the floor division to determine if any extra 0 values need to be added, and then use the modulo to get the remainder for each step. By storing the remainders in a list, we can then look to see if that remainder was previously generated. If so, we can also determine how long the pattern is by noting how many steps were needed to generate the repeat remainder. If any step generates a 0 remainder, then we know the fraction is not a repeating decimal.

Since we are looking for the max repetend length, we can simplify the algorithm by not looking for a terminating fraction, but instead extending the definition of the repeated fraction by stating that all fractions repeat - even those that end in trailing zeroes. These then result in a repetend length of 1, which is slightly incorrect - but it simplifies the approach.

Also note that we do not need the result of the division - by not storing the result, but only looking for the repeat of the reminder, we shave about 10% off the execution time.

The info provided in the problem description did not allow for many test cases - but looking up repeating decimal in Wikipedia provides a chart of many more repeated decimal entries that can be used to verify the algorithm is correct. We get the answer in well under a second :

Another obvious approach is to allow Python to expand the fraction into decimal form, and then look for the repetend in the decimal expansion. However, this has a few issues :

  • Floating point numbers have limited precision, and we rapidly encounter this limit when looking for long repetends. It's possible to get past this issue with a library like "decimal" or "gmpy2".
  • The arbitrary precision libraries are fast - but their performance decreases in proportion to the increase in precision.
  • The search for a repeating value of unknown length, and with an unknown prefix before it repeats, is slow.