Project Euler Problem 4

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.

First let's write a function that can quickly test whether an integer $n$ is a palindrome. This can be done pretty easily and elegantly:

function is_palindrome(n)
    n = abs(n)  # handle negative numbers
    return string(n) == reverse(string(n))
end

but this allocates memory for two strings. So when checking lots of large numbers it will be slower than a purely numerical approach that allocates no memory.

We can instead take a numerical approach where we reverse the number by extracting digits from right to left and rebuilding the number:

function is_palindrome(n)
    n = abs(n)
    original = n
    reversed = zero(typeof(n))

    while n > 0
        reversed = reversed * 10 + (n % 10)
        n ÷= 10
    end

    return reversed == original
end

We can then use this function to search for the largest palindrome made from the product of two numbers that do not exceed upper_limit each:

function largest_palindrome_product(lower_limit, upper_limit; max_product=nothing)
    T = typeof(upper_limit)
    max_palindrome = zero(T)
    best_i, best_j = zero(T), zero(T)

    for i in upper_limit:-1:lower_limit
        if i * upper_limit < max_palindrome
            break
        end

        # Start from j=i to avoid duplicate combinations as i*j == j*i
        for j in upper_limit:-1:i
            product = i * j

            if !isnothing(max_product) && product >= max_product
                continue
            end

            if product < max_palindrome
                break
            end

            if is_palindrome(product) && product > max_palindrome
                max_palindrome = product
                best_i, best_j = i, j
            end
        end
    end

    return (palindrome=max_palindrome, factors=(best_i, best_j))
end

So we search through all products $ij$ in descending order to find the largest palindrome. The search is sped up in a few ways. First, we iterate from largest to smallest values since we're searching for a maximum. This lets us terminate early if $ij$ can no longer exceed the current maximum palindrome found so far. We added the option to specify a max_product to solve the HackerRank version of this problem.

Benchmarking the 3-digit case we find the solution largest_palindrome_product(100, 999) in 14.972 μs.

For the 6-digit case we call largest_palindrome_product(100000, 999999) to find a maximum palindrome of $999,000,000,999 = 999,001 \times 999,999$ in 4.518 ms.

We can also do the 9-digit case and call largest_palindrome_product(100000000, 999999999) to find $999,900,665,566,009,999 = 999,920,317 \times 999,980,347$ in 49.334 s which is still under a minute.

Beyond that, for the 12-digit case we'll have to use 128-bit integers as the product of two 12-digit numbers will easily overflow if we keep using 64-bit integers. It will probably also take a lot longer than 1 minute! Besides Int128 operations taking more CPU cycles than Int64 operations, the solution time scales superlinearly.

Let $U$ denote the upper limit and $L$ the lower limit. Also let $R = U - L + 1$ and $d$ be the number of digits in the upper limit. In the worst case our solution takes $\mathcal{O}(R^2 d)$ time as it checks all $(i, j)$ pairs of which there are $R^2$ pairs and calls to is_palindrome take $\mathcal{O}(d)$ time. The early termination optimizations will reduce the number of pairs to check by a lot but in the worst case you're still searching a large space.