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