Palindromes

Problem 4 at Project Euler poses the following challenge:

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.

A Naïve Approach

A naïve solution would be to multiply all the three-digit numbers by one another, pull out all the palindromes, and find the greatest:

var isPalindrome = function(n){  
  n = n.toString();
  return n === n.split("").reverse().join("");
};

var findBiggest = function(){  
  var allProducts = [];
  for (var n = 100; n < 1000; n++){
    for (var m = 100; m < 1000; m++){
      allProducts.push(m * n);
    }
  }
  var palindromes = allProducts.filter(isPalindrome);
  return Math.max.apply(null, palindromes);
};

But the naïve appraoch means making a huge-ass array with 810,000 numbers in it, consuming 3.09MiB of memory and taking many milliseconds to build. We can do better with a little number theory.

Don’t include obvious duplicates

$m \times n = n \times m$

Instead of starting m at 100 for each value of n, start it at n. This avoids duplicates and cuts array size roughly in half, to only 405,450 entries.

Don’t include multiples of 10

Observe that $n \times 10$ always ends in $0$. We don’t ordinarily write positive non-zero integers in decimal with leading zeros, so we can safely exclude all multiples of 10 from $n$ and $m$, saving us another 76,995 entries in allProducts, almost 19%, for a new total of 328,445 entries.

Assume the greatest palindrome has six digits

This is a pretty safe assumption in the instance the Project Euler problem describes, but may not be safe in other situations. Of our remaining 404,550 products of two three-digit decimal numbers, only 69,787 (17.25%) of them do not have six digits. It turns out these 17.25% include over 60% of the palindromes, but all we need is one six-digit palindrome in there to safely ignore the five-digit ones. $101,101 = 143\times707$ and has six digits; that’s enough to let us dismiss five-digit entries.

But how do we exclude five-digit products from our array without having to spend time calculating those products? We don’t. But limiting ourselves to condisering only six-digit products (actually, to products with an even number of digits) lets us do something nifty.

As it turns out, palindromic numbers with an even number of digits have a nifty property: they all share a common, easily identifiable factor.

Let $\mathbb{P}\subset\mathbb{N}$ be the set of palindromic numbers with $k+1$ digits $a_0...a_k$ in an arbitrary base $b:b\geq2$:

$\mathbb{P}=\left\{ n\in\mathbb{N}:n=\sum\limits_{i=0}^{k}a_ib^i\middle|a_i=a_{k-i}\right\}$

Note that $n$ is palindromic if and only if $a_i=a_{k-i}$. By way of example:

$$\begin{equation}\begin{split}987,789&=9(10^0)\\&+8(10^1)\\&+7(10^2)\\&+7(10^3)\\&+8(10^4)\\&+9(10^5)\end{split}\end{equation}$$$$\begin{equation}\begin{split}65,456&=6(10^0)\\&+5(10^1)\\&+4(10^2)\\&+5(10^3)\\&+6(10^4)\end{split}\end{equation}$$

Looks like a pattern! Turns out we can rewrite the sum like this, but only for palindromes with an even number of digits:

$n=\sum\limits_{i=0}^{\frac{k+1}{2}}a_i\left(b^i+b^{k-i}\right)\Big|k+1\text{ is even}$

Essentially, we pair up the digit $a_i$ with its matching digit $a_{k-i}$ and thereby only deal with half the digits. This doesn’t work with palindromes with an odd number of digits because of the pesky middle digit, which has no mate.

$$\begin{equation}\begin{split}987,789&=9(10^0+10^5)\\&+8(10^1+10^4)\\&+7(10^2+10^3)\end{split}\end{equation}$$$$\begin{equation}\begin{split}65,456&=6(10^0+10^4)\\&+5(10^1+10^3)\\&+4(10^2)\end{split}\end{equation}$$

For palindromes with an even number of digits, we can factor the addend:

$a_i(b^i+b^{k-i})=a_ib^i(1+b^{k-2i})$

Check it out! We can make $1+b^{k-2i}=0$ with modular arithmetic!

$$\begin{alignat*}{2}\begin{split}1+b^{k-2i}&=1-1^{k-2i}&\mod{b+1}\\&=1-1&\mod{b+1}\\&=0&\mod{b+1}\end{split}\end{alignat*}$$

Every palindrome with an even number of digits is evenly divisible by $b+1$, where $b$ is the radix. We’re working in decimal, so $b+1=11$.

We needn’t bother with any products but those that are divisible by 11. 11 being prime makes things easy. We'll only multiply $m\times n$ and push() the product to allProducts if at least one of $\lbrace m,n\rbrace$ is divisible by 11. This brings allProducts.length down to only 55,764, a reduction of over 93.1% from our original 810,000.

Putting it All Together

All this makes for lots of savings in computation and storage, but it makes our program a lot uglier:

var isPalindrome = function(n){  
  n = n.toString();
  return n === n.split("").reverse().join("");
};

var findBiggest = function(){  
  var allProducts = [];
  var start, end, step;
  for (var n = 101; n < 1000; n++){
    if (n % 10){
      if (n % 11){
        start = 11*Math.ceil(n/11);
        end = 11*Math.floor(1000/11);
        step = 11;
      } else {      
        start = n;
        end = 1000;
        step = 1;
      }
    }
    for (var m = start; m < end; m+=step){
      if (m % 10){
        allProducts.push(m * n);
      }
    }
  }
  var palindromes = allProducts.filter(isPalindrome);
  return Math.max.apply(null, palindromes);
};

Messy, but fast. The naïve version ran in 1,158.8ms, while this version runs in only 74.2ms.

Tom G Varik