(This article was first published on

**Vikram and Neha**, and kindly contributed to R-bloggers)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*

To

**leave a comment**for the author, please follow the link and comment on his blog:**Vikram and Neha**.R-bloggers.com offers

**daily e-mail updates**about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...