## 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{split}987,789&=9(10^0)\\&+8(10^1)\\&+7(10^2)\\&+7(10^3)\\&+8(10^4)\\&+9(10^5)\end{split}$$$$ $$$$\begin{split}65,456&=6(10^0)\\&+5(10^1)\\&+4(10^2)\\&+5(10^3)\\&+6(10^4)\end{split}$$$$

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{split}987,789&=9(10^0+10^5)\\&+8(10^1+10^4)\\&+7(10^2+10^3)\end{split}$$$$ $$$$\begin{split}65,456&=6(10^0+10^4)\\&+5(10^1+10^3)\\&+4(10^2)\end{split}$$$$

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.