I have been posting R solutions to Project Euler problems as a way of polishing my R skills. Here is the next problem in the series, problem 26. The problem is stated as follows:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:The first task is to define a function that returns the cycle length of 1/n for any input n. The function logic is pretty simple. We compute all the remainders in the long division of 1 by n. The moment we encounter a remainder that has been seen before, we know that the fraction has a recurring cycle and can compute its length.

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.

recur.length <- function (n) { x = 1 # Starting with the numerator 1 remainders = c(x) repeat { x = (x*10) %% n # Find the remainder if (x == 0) { return (0) } # Fraction terminates, so cycle length is 0. if ((x %in% remainders)) {break} # Repeating remainder is found. Break from loop. remainders <- c(remainders, x) # Else add remainder to list. } return (length(remainders) - which(remainders == x) + 1) # Exclude non-repeating part of the decimal }

Using the recur.length function we find d < 1000 with the largest recurring cycle. The following insights that make our search pretty efficient

- A number d can have a recurring cycle of at most d - 1. This is because modulo division by d can have only d unique remainders (0, 1, ..., d-1), after which we will necessarily find a remainder that repeats. One of these remainders is zero, and if we get this, no recurrence is possible.
- Due to the first observation, larger values of d will possibly have larger cycle lengths. So it is faster to searching from 1000 down to 2, rather than from 2 up to 1000.
- Searching down from 1000, say we find a recurring cycle of length k. Now we know that the smallest number that we need to check is k + 1. This is because the numbers smaller than k + 1 (that is 2 to k) can only have cycle lengths of k - 1 or less.

Based on the above, here's a function to find the d with the largest recurring cycle.

longest <- function (n) { maxlength = 0 # Maximum recurring cycle maxd = 0 # d with the maximum recurring cycle # Check all numbers between low and i for a longer cycle length low = 2 i = n while (i > low) { ilength = recur.length(i) if (ilength > maxlength) { maxlength = ilength maxd = i low = maxlength + 1 # The candidate must be > = low } i = i - 1 } maxd }

*Code formatted by Pretty R at inside-R.org*