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;
}
```