# Project Euler 26: Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

^{1}/_{2} | = | 0.5 |

^{1}/_{3} | = | 0.(3) |

^{1}/_{4} | = | 0.25 |

^{1}/_{5} | = | 0.2 |

^{1}/_{6} | = | 0.1(6) |

^{1}/_{7} | = | 0.(142857) |

^{1}/_{8} | = | 0.125 |

^{1}/_{9} | = | 0.(1) |

^{1}/_{10} | = | 0.1 |

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ^{1}/_{7} has a 6-digit recurring cycle.

Find the value of *d* < 1000 for which ^{1}/_{d} contains the longest recurring cycle in its decimal fraction part.

## Solution

I studied recurring decimal numbers for quite a while when I worked on my rational numbers library, so it's nice to see this as a problem here again. When working out the decimal expansion of a rational number \(\frac{a}{b}\in\mathbb{Q}\), we can follow a simple algorithm, we learn quite early in school. For example, the decimal expansion of \(\frac{1}{7}\) can be generated like this:

1 / 7 = 0 10 / 7 = 1 30 / 7 = 4 20 / 7 = 2 60 / 7 = 8 40 / 7 = 5 50 / 7 = 7 10 / 7 = 1

Which starts cycling with the last line. The algorithm to generate this pattern is quite simple:

var a = 1; var b = 7; var digits = 8; for (var i = 0; i < digits; i++) { var n = a / b | 0; console.log(a + " / "+ b + " = "+ n); a = a % b * 10; }

We could use this principle already to calculate the length of the cycle, all we have to do is to remember all remainders and check if the cycle starts over again:

function cycleLength(b) { var hash = {}; var a = 1; var t = 0; do { hash[a] = t; a = a % b * 10; t++; } while (hash[a] === undefined); return t - hash[a]; }

It can be shown that recurrence will always end with 1, which allows us to remove the hash-map for cycle detection:

function cycleLength(b) { var a = 1; var t = 0; do { a = a * 10 % b; t++; } while(a !== 1); return t; }

That's actually the function I've written for the rational numbers implementation, but how can it be derived? Let's start with the example \(\frac{1}{7}\), which is \(0.(142857)\) in decimal. In order to bring the repeating part in front of the decimal point, we need to multiply the fraction by \(10^6\). When we calculate \(\left\lfloor \frac{10^6}{7}\right\rfloor\) we get \(142857\), multiplying it by 7 yields \(999999\). That's interesting, that only one is missing to \(10^6\), or \(10^6-7\left\lfloor \frac{10^6}{7}\right\rfloor=1\). Re-formulating this finding gives

\[10^d\equiv 1\pmod{b}\]

Or differently, we are looking for the smallest \(d\) such that \(b\) divides \(10^d-1\). Since \((x\cdot y)\mod z = (x\mod z \cdot y\mod z)\mod z\), the recursive definition of the algorithm stated before follows. A naive implementation for the solution is then:

function solution() { var max = 0; var max_p = 0; for (var d = 1; d < 1000; d++) { var tmp = cycleLength(d); if (max < tmp) { max_p = d; max = tmp; } } return max_p; }

When we execute this snippet however, we get an endless loop. The reason is that \(b\) must be co-prime to 10, meaning that it is not allowed to be divisible by 2 or 5, as it will never go down to 1. It's possible however to remove the primes two and five from \(b\) - which doesn't change the length of the repeating part. Have a look at any \(\frac{1}{7\cdot 2^i\cdot 5^j}\) for example. Instead of changing the cycle length function, we reduce the set of numbers we take into account, however. When we take a look at \(\frac{1}{7}\) with \(d=6\), we could come to the idea that for any prime the length is \(d=b-1\). When we look at the prime 11 with \(d=2\), this idea isn't valid anymore. However, if we knew what primes would have exactly a periodic length of the denominator minus one, we could choose just the largest of such primes. Those primes are called **Full reptend primes** (A001913). Generating these primes is costlier however than simply looping over all primes and maximize \(d\):

function solution() { var primes = [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]; var max = 0; var max_p = 0; for (var i = 0; i < primes.length; i++) { var tmp = cycleLength(primes[i]); if (max < tmp) { max_p = primes[i]; max = tmp; } } return max_p; }