Project Euler 26: Reciprocal Cycles

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.

Sequence A051626 in the On-Line Encyclopaedia of Integer Sequences describes the length of the recurring numbers in 1/n. To solve Euler Problem 26, we need to generate the first 1000 numbers of this sequence and find out which number has the longest recurring cycle.

R can only display up to 22 decimals by using options(digits=22). The base R capability is unsuitable for solving this problem, so I wrote some code to perform long division the old-fashioned way.

The recur() function divides 1 by any arbitrary integer. The code continues until the decimal terminates, for example 1/4 = 0.25, or when a recurring pattern emerges, e.g. 1/7 = 0.(142857).

The function has two arguments: n is the input number. The output argument determines the outcome of the function: “=len=” for the length of the recurring decimals. Any other value shows the result of the calculation. The output of the function is a string. Using the European notation, the recurring part of the decimals is shown between brackets, e.g. 1/14 = 0.0(714285).

ProjectEuler

  ## Project Euler 26: Reciprocal Cycles
  recur <- function(x, output = "") {
      # Prepare variable
      if (x == 0) return(NaN)
      if (x == 1) return(0)
      x <- floor(abs(x))
      # Initiate vectors to store decimals and remainders
      dec <- vector()
      rem <- vector()
      # Initiate values
      i <- 1
      r <- 10
      rem <- r
      # Long division
      repeat {
          dec[i] <- floor(r / x)
          r <- 10 * (r %% x)
          # Test wether the number is terminating or repeating
          if (r == 0 | r %in% rem) break
          rem[i + 1] <- r
          i <- i + 1 
      }
      # Determine number of recurring digits
      rep <- ifelse(r != 0, length(rem) - which(r == rem) + 1, 0)
      # Output
      if (output == "len")
          return(rep)
      else {
          if (rep != 0) {
              if (rep == length(dec)) 
                  l <- "("
              else
                  l <- c(dec[1:(length(dec) - rep)], "(")
              dec <- c(l, dec[(length(dec) - rep + 1):length(dec)], ")")
          }
          return(paste0("0.", paste0(dec, collapse = "", sep = "")))
          }
  }

  A051626 <- sapply(1:1000, recur, "len")
  answer <- which.max(A051626)
  print(answer)

  recur(998001, "len")
  recur(998001)