Project Euler Problem #4 (R)

Problem 4 in on Project Euler’s list is the following:

Find the largest palindrome made from the product of two 3-digit numbers.

We can attack this as follows: firstly, we know that for an n-digit number, the minimum n-digit number is \(10^{n-1}\) and the maximum is \(9\sum_{i=0}^{n-1}10^{i}\). So we need the cartesian product of all numbers in this range, which we can then test for the palindrome property, and finally filter for the maximum element.

Testing for the palindrome property requires that we check each digit in the number for equality on either side. We do this first by calculating the number of digits in the product (using \(\lfloor\log_{10}(x)\rfloor\) and then just comparing the digits by using the modulus and shifting. Note a couple of points in the R code below:

• %/% is integer division;
• Note the vectorization at work in statements like (p %/% 10^x): this will divide p by successive powers of 10, where the powers are defined in the x vector;
• Note the use of the logical all() function to test whether all palindromic contenders are equal.

pal < - function(N) {
 palindromes <- c()
 min_no <- 1*10^(N-1)
 max_no <- sum(9*10^(seq(0,N-1)))
 n <- 1
 for (i in seq(max_no,min_no,-1)) {
  for (j in seq(i,min_no,-1)) {
   p <- i * j
   digits <- floor(log10(p))
   x <- seq(0, digits %/% 2)
    if (all( ((p %/% 10^x) %% 10)==((p %/% 10^(digits-x)) %% 10) )) {
     palindromes[n] <- p
     n <- n + 1
    }
  }
 }
 max(palindromes)
}