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

Permalink: https://projecteuler.net/problem=26

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

As you see for `d`

from `2`

to `10`

, the longest cycle length is `6`

, for `d=7`

.

Let’s start with a function, which finds the cycle length for given `d`

```
(defn unit-fraction [denom]
(loop [numer 1 i 1 known {}]
(let [r (rem (* 10 numer) denom)]
(cond (zero? r) 0
(get known r) (- i (get known r))
:else (recur r (inc i) (assoc known r i))))))
```

Optimal algorithm is a little bit tricky.

In simplest case, we need to find a cycle for `1/4`

. Calculate next decimal digit (we index digits number with `i`

variable), by finding quotient. `1/4`

does not produce integer number, so advance decimal index (result becomes `0.`

something) and multiply 1 by 10. Quotient `10/4=2`

and remainder is `2`

(result becomes `0.2`

something). Again `2/4`

does not produce integer number, so advance index and multiply by 10. Quotient of `20/4=5`

, *without* remainder, so whole result is equal to `0.25`

, no cycle detected.

For `d`

, which contain cycles we introduce `known`

map to store all previous numbers. Assume `d`

is `11`

, starting with remainder `1`

we don’t have integer result (result so far `0.`

) and we store the fact, for `remainder=1`

, `index=1`

. Proceeding, we multiple remainder by 10, but `10/11`

does not produce integer result as well (result so far `0.0`

) and store `remainder=10, index=2`

. Proceeding, For third index `100/11=9`

, with remainder `1`

. But remainder `1`

has been seen before, at index `1`

, so all subsequent calculation will produce the cycle. And cycle length is difference between current index and index seen before, `3-1=2`

, and as result we have `0.(09)`

with cycle length `2`

.

Finally, just map this function to all denominators and find the one which will produce max result.

```
(->> (range 1 1000)
(map #(vec [% (unit-fraction %)]))
(apply max-key second)
(first))
```

Easy.

mishadoff 09 May 2017