Project Euler 4: Largest Palindromic Product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

The formal definition for Palindromic numbers in base-\(b\), with \(k\) digits \(a_i\) is:

$$\sum_{i=0}^ka_ib^i = \sum_{i=k}^0a_ib^i$$

The solution code uses a helper-function to reverse numbers. The reverse() function takes the modulus of 10 to extract the last digit until all digits have been processed. The solution code searches for palindromic numbers, starting at the highest product of three-digit numbers.

ProjectEuler

  ## Project Euler 4: Largest Palindromic Product

  ## Reverse a number
  reverse <- function(n) {
      reverse <- 0
      while (n > 0) {
          reverse <- 10 * reverse + (n %% 10)
          n <- floor(n / 10)
      }
      return(reverse)
  }

  ## Euler problem 4
  for (i in 999:900) {
      for (j in 990:900) {
          p <- i * j
          if (p == reverse(p)) 
              break
      }
      if (p == reverse(p)) {
          break
      }
  }
  answer <- i * j
  print(answer)

The Lychrell process can convert almost all non-palindromic numbers to a palindromic number. The process reverses the non-palindromic number and adds the result to the original number. If the result is not a palindromic number, the process repeats until we reach a palindrome. For example, 59 becomes a palindrome after 3 iterations: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111.

Any number that will never become a palindrome using the Lychrel process is a so-called Lychrel number. Most numbers will convert to a palindrome after a few iterations. However, the number 196 apparently never becomes a palindrome, even after hundreds of thousands of repetitions. There is no proof that Lychrel numbers actually exist. Any code to undertake the Lychrel process could run forever, which is the infamous halting problem in computer science. Sequence A023108 of the Online Encyclopedia of Integers lists numbers that apparently never iterate to become a palindrome.

The lychrel() function tests a number for Lychrel property by following the palindrome process. The output of this function is the resulting palindrome. As these numbers can be huge, we maximise the number of available digits. Unfortunately, there is no way of telling if it will ever stop for certain numbers. We know that the first 195 will terminate, but the number 196

  ## Lychrel Numbers
  lychrel <- function(l, verbose = FALSE) {
    while(l != reverse(l)) {
      l <- l + reverse(l)
      print(l)
    }
  }

  lychrel <- function(l) {
    while(l != reverse(l))
      l <- l + reverse(l)
    return(l)
  }

  ## First 195 non-Lychrel numbers
  options(digits = 22)
  sapply(10:195, lychrel)

  ## This function call apparently never halts - run at your own risk!
  lychrel(196)