Problem 4 - Largest Palindrome Product

Black Bridge overlooking the top of Kuda Ravana waterfall & surrounding valley
Ella, Sri Lanka - April 29th, 2025

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

https://projecteuler.net/problem=4

Thoughts

One of the lessons of working through the Project Euler problems is to learn to see & use patterns as mathematical shortcuts.

An observation that a user on Stackoverflow made is that all even digit palindromes (e.g. for even values of n in the answers below) are divisible by 11.

Increasing n in this problem is a great example of the battle between writing efficient logic & conducting in-memory compute.

I do not implement the divisible by 11 logic in any of the answers below, but I do share my thoughts on 1st order improvements to my original answers to handle runtime complexity. I may come back to implementing this pattern sometime to discover calculating larger even digit palindromes.

None of the answers are optimized for values of \(m > 2\).

R

Answer 1

palindrome_m2n3 <- function(m = 2, n = 3) {
  # check from largest to least of product of m n-digit numbers
  x <- seq(((10^n)-1)^m, 1)
  y <- as.character(x)
  for (i in 1:length(x)) {
    # find reverse digits & check if palindrome 
    # then check for compatible n-digit m-factor product
    yr <- lapply(strsplit(y[i], ""), function(i) paste(rev(i), collapse = ""))[[1]]
    if (identical(y[i], yr)) {
      # n-digit sequence
      f_i <- seq((10^n)-1, 10^(n-1))
      # booleans of the factor
      f_x0 <- x[i] %% f_i == 0
      f_x <- x[i] / f_i
      # compatibility check: of factor 'f2'
      if (any(f_x0)) {
        # compatibility check: of n-digit factor 'f2'
        bool_n <- f_x[f_x0] %in% f_i
        if (any(bool_n)) {
          i_f <- min(which(f_i %in% f_x[f_x0]))
          f1 <- f_i[i_f]
          f2 <- f_x[i_f]
          return(data.frame(p = x[i], f1, f2, iter = i))
        }
      }
    }
  }
}

tic()
palindrome_m2n3(m = 2, n = 3)
toc()

       p  f1  f2  iter
1 906609 993 913 91393
0.616 sec elapsed

Answer 2

The real machine memory/RAM issues occur when we increase n.

We can make this more efficient by looping through a sequence of products. Storing a sequence of products with increasing values of n (e.g. n = 5) will lead to out of memory errors, possibly due to the fact that R is not allowing to store tables in memory larger than ~2 billion rows (2^31).

One way to deal with these out of memory errors is to chunk/partition the sequence of product results incrementally. Additionally, we should not even attempt to push the matrix row upper bound limit of 2^31 rows, because it is inefficient to store in memory & slow to generate.

Thus, we should use a max rational increment, such as \(10^{n-1}\), but also keep it well below \(\sqrt{2^{31}}=46,340.95\) — striking a good balance. The loop iterations to find the palindrome is the main bottleneck, not the matrix product calculations.

After running some tests, it seems like setting increment to \(10^3 = 1,000\) is a good idea b/c outer(1:10^3, 1:10^3) calculates fast.

I’ve discovered below does not fully check the correct possibilities.

e.g. only taking outer products of the indices seq((j-1)*inc + 1, j*inc) of s & not checking j+1, j+2, etc.

i.e. more complexity is added when chunking by inc=1000 than I had accounted for.

palindrome_m2n3 <- function(m = 2, n = 3) {
  # check from largest to least of product of m (10^n)-1 digit numbers
  s <- seq((10^n)-1, 10^(n-1))
  inc <- 10^3
  p <- length(s)/inc
  for (j in 1:p) {
    so <- s[seq((j-1)*inc + 1, j*inc)]
    xo <- so
    for (i in 1:(m-1)) xo <- sort(unique(as.vector(outer(xo, so))), decreasing = T)
    y <- as.character(xo)
    # find reverse digits & check if palindrome 
    for (i in 1:length(xo)) {
      ij <- (j-1)*inc+i
      yr <- lapply(strsplit(y[i], ""), function(i) paste(rev(i), collapse = ""))[[1]]
      if (identical(y[i], yr)) {
        p = xo[i]
        # conduct reverse lookup for factors of palindrome product
        # Note: this is unnecessary if we store factors with outer products in a dataframe
        # booleans of the factor
        f_x0 <- p %% so == 0
        f_x <- p / so
        i_f <- min(which(so %in% f_x[f_x0]))
        f1 <- so[i_f]
        f2 <- f_x[i_f]
        return(data.frame(p = p, f1, f2, iter = ij, j))
      }
    }
  }
}

tic()
palindrome_m2n3(n = 5)
toc()

           p    f1    f2  iter j
1 9966006699 99979 99681 28880 1
0.269 sec elapsed

Python

Answer 1

import time

def palindrome_m2n3(m: int, n: int) -> int:
  # check from largest to least of product of m n-digit numbers
  x = [i for i in range(((10**n)-1)**m, 0, -1)]
  # n-digit sequence
  f_i = [i for i in range(10**n-1, 10**(n-1)-1, -1)]
  for i in x:
    # find reverse digits & check if palindrome 
    # then check for compatible n-digit m-factor product
    if str(i) == str(i)[::-1]:
      # compatibility check: of an n-digit factor
      f_x = [i / j for j in f_i]
      f = [j for j in f_x if j == int(j) and j in f_i]
      if len(f) > 0:
        f1 = f[0]
        f2 = i / f1
        return {'p': i, 'f1': f1, 'f2': f2, 'iter': x.index(i)+1}

t0 = time.perf_counter()
print(palindrome_m2n3(m=2, n=3))
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

{'p': 906609, 'f1': 913.0, 'f2': 993.0, 'iter': 91393}
0.046 sec elapsed