Project Euler Problem 36

The decimal number, $585 = 1001001001_2$ (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.)

We'll solve the more general problem of finding all numbers below $N$ that are palindromes in both base $10$ and base $K$. The original problem is the case $N = 10^6$ and $K = 2$.

In Problem 4 we checked whether a number is a palindrome by reversing its digits. In base $K$ we peel off the last digit by dividing by $K$ instead of $10$ and tack it on by multiplying by $K$, so all is_palindrome needs is a base keyword:

@inline function is_palindrome(n; base=10)
    n = abs(n)  # Handle negative numbers
    base = oftype(n, base)
    original = n
    reversed = zero(typeof(n))

    while n > 0
        n, digit = divrem(n, base)
        reversed = reversed * base + digit
    end

    return reversed == original
end

The simplest solution is to check every number below $N$ in both bases, starting with base $10$ since that rules out almost everything:

function find_double_base_palindromes_naive(N, K)
    return [n for n in 0:N-1 if is_palindrome(n) && is_palindrome(n; base=K)]
end

This takes 4.380 ms for $N = 10^6$, which is plenty fast for the original problem. But almost all of that time is spent confirming that numbers aren't palindromes: only about 0.2% of the numbers below $10^6$ are palindromes in base $10$.

So instead of searching for palindromes, let's build them. A palindrome is determined by its first half: $123321$ is $123$ followed by $123$ reversed, and $12321$ is $123$ followed by $12$ reversed since the middle digit only shows up once. So every palindrome with $L$ digits can be built from a number $h$ with $k = \lceil L/2 \rceil$ digits by appending the digits of $h$ in reverse, leaving out the last one when $L$ is odd:

function make_palindrome(h; odd=false)
    ten = oftype(h, 10)
    p = h
    odd && (h ÷= ten)  # Don't repeat the middle digit

    while h > 0
        h, digit = divrem(h, ten)
        p = p * ten + digit
    end

    return p
end

Each $L$-digit palindrome is built from exactly one $h$, its own first half. There are $9 \cdot 10^{k-1}$ numbers with $k$ digits, so there are $9$ palindromes with one digit, $9$ with two digits, $90$ with three, $90$ with four, and so on. Below $10^6$ that's $9 + 9 + 90 + 90 + 900 + 900 = 1{,}998$ palindromes, not counting $0$, and in general the number of palindromes below $N$ grows like $\sqrt{N}$ since we only get to pick half of the digits.

We start with $0$, which is a palindrome in every base, and build the rest one length at a time. For $L = 3$ the first halves $h = 10, 11, 12, \dots, 99$ give the palindromes $101, 111, 121, \dots, 999$. All that's left is to check each one in base $K$:

find_double_base_palindromes(N, K) = find_double_base_palindromes(N, Val(K))

function find_double_base_palindromes(N, ::Val{K}) where {K}
    result = N > 0 ? [0] : Int[]  # 0 is a palindrome in every base

    for L in 1:ndigits(N - 1)
        k = cld(L, 2)  # number of digits in the first half
        for h in 10^(k-1):10^k-1
            p = make_palindrome(h; odd=isodd(L))
            p >= N && break
            is_palindrome(p; base=K) && push!(result, p)
        end
    end

    return result
end

The one-line method at the top is there for speed. Julia compiles a separate copy of a function for each combination of argument types, so with $K$ always an Int a single copy of the search would handle every base. It couldn't know what divrem(n, base) in is_palindrome divides by and would have to use the CPU's division instruction, which is slow. Val(K) turns the value of $K$ into a type like Val{2}, so each base gets its own copy of the search with $K$ as a constant. Since is_palindrome is marked @inline, its code gets pasted into each copy where the compiler can see what it's dividing by. Dividing by $2$ becomes a bit shift and dividing by $9$ becomes a multiplication by a precomputed constant, both much cheaper than a division. For $K = 2$ this makes the search 4.43× faster at $N = 10^{12}$ than the same code with $K$ only known at runtime. The price is compiling a new copy of the search the first time each base comes up.

This finds the double-base palindromes below $10^6$ in 17.306 μs, which is 253× faster than checking every number.

Going up to $N = 10^{12}$ takes 38.705 ms and finds $39$ double-base palindromes, the largest being $136{,}525{,}525{,}631$. That's a thousand times more palindromes to build than for $N = 10^6$, and each one takes longer to check since it has twice as many binary digits. How long a base takes depends on both how many digits numbers have in that base, from up to $40$ in base $2$ down to $13$ in base $9$ below $10^{12}$, and how cheap it is to divide by it. Dividing by a power of $2$ is a bit shift, so bases $2$, $4$ and $8$ are quicker than their number of digits would suggest. Here's every base the HackerRank version asks about, plus $N = 10^{15}$ for base $2$:

The base $2$ results match the list of every double-base palindrome below $10^{12}$ that mvz posted in the forum thread back in 2005, and the sums that NP, 8folder, and yzqt posted more recently.

We could also have built the palindromes in base $K$ and checked them in base $10$, but there are roughly as many palindromes below $N$ in any base so it wouldn't save much. And for $K = 2$ we could skip the decimal palindromes that start with an even digit, since they also end in one and every binary palindrome other than $0$ is odd, but that trick is specific to base $2$.

Eshed Schacham has a great write-up on finding really big binary-decimal palindromes, which starts with this same mirroring approach and then goes much further.

The numbers that are palindromes in both base $2$ and base $10$ are OEIS A007632. They get big fast: $175$ of them are listed, the largest with $53$ digits, and the last $28$ were found by Eshed's search. Our solution runs in $\mathcal{O}(\sqrt{N} \log N)$ time since there are $\mathcal{O}(\sqrt{N})$ palindromes below $N$ and building and checking each one takes $\mathcal{O}(\log N)$ divisions.