Project Euler Solution #36: Double-base palindromes

Problem 36

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases. Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2. Please note that the palindromic number, in either base, may not include leading zeros.

Solution

We got a function isPalindrome for Problem 4 already to check if a number is a palindrome in base 10. This function can easily be extended for an arbitrary base:

function isPalindrome(x, base) {

    var n = 0;
    var m = x;

    while (x > 0) {
        n = n * base + x % base;
        x = x / base | 0;
    }
    return n === m;
}

This function can be further improved by using JavaScripts fast toString function and check the resulting string from left to right and right to left simultanously:

function isPalindrome(x, base) {

    var s = x.toString(base);
    var a = s.length - 1;
    var b = 0;

    while (b < a) {

        if (s[a] !== s[b]) {
            return false;
        }
        b++;
        a--;
    }
    return true;
}

We now can use this function, loop over the whole range of numbers and sum up the number if it passes the palindrome test for both bases. One optimization that we can use is that a palindrome in base two must be odd, since it can't have a leading zero. This halves the search space already and we can implement the solution like this:

function solution(limit) {

    var i = 1;
    var s = 0;
    while (i < limit) {
        if (isPalindrome(i, 10) && isPalindrome(i, 2)) {
            s+= i;
        }
        i+= 2;
    }
    return s;
}

But we can do a lot better. Instead of checking all numbers to be palindromic, we can generate palindromes and reduce the search space tremendously. If we say we have a 5 digit palindrome 'abcba' or a 6 digit palindromic number 'abccba' in base \(s\), the palindrome is fully defined by the first three digits 'abc'. It follows that every positive number less than \(s^n\) generates a palidrome less than \(s^{2n}\). This holds for every base \(s\).

To make this improvement clear: For the given limit we need to generate only 2000 palindromes in base 2 or base 10 and check if it is a palindrome in the other base. This is much faster than checking 1000000 numbers or 500000 when using the odd-numbers trick. 

To make things easier, we split the generation process in the generation of odd and even palindomes. Generating the next palindrome from a number is simply appending the digits in reverse, which is pretty similar to the palindromic check, we already conducted:

function generatePalindrome(x, base, oddPalindrome) {
    var res = x;
    if (oddPalindrome) x = x / base | 0;
    while (x > 0) {
        res = res * base + x % base;
        x = x / base | 0;
    }
    return res;
}

When we decide to generate base two palindromes and check them in base 10, we can improve this function and use binary operations:

function generatePalindrome2(x, oddPalindrome) {
    var res = x;
    x>>= oddPalindrome;
    while (x > 0) {
        res = (res << 1) | (x & 1);
        x>>= 1;
    }
    return res;
}

The final solution can then be implemented pretty straightforward:

function solution(limit) {
    var sum = 0;

    for (var parity = 0; parity < 2; parity++) {

        var p = generatePalindrome2(1, parity);
        for (var i = 2; p < limit; i++) {
            if (isPalindrome(p, 10)) {
                sum+= p;
            }
            p = generatePalindrome2(i, parity);
        }
    }
    return sum;
}
solution(1000000);