Project Euler in R: Problem 26

February 27, 2012

(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:
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.

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.

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
}

The above code demonstrates the use of the less common but simple repeat loop. R doesn't have a do-while, so repeat with a break is a perfect way to imitate such a construct. You can read more about R control-flows here.

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
}

The search is efficient and takes only 0.15s on my Intel Core 2 Duo 1.6Ghz laptop running Linux. Discussion threads suggest limiting the search to prime numbers, but I'm not sure if this would be much more efficient. The gains in the reduced number of candidates would probably be offset by primality tests. It is amazing how small this code is. R handles most of the array handling and searching through a vector.

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.