Project Euler Solution 36: Double-base palindromes

In the Project Euler series we have Problem 36: Double-base palindromes today. One has to find numbers which are palindromes in both base 10 and base 2 representations.

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.)

For this one I can use a completely pure functional style. We start off by writing a predicate for the palindrome property:

def is_palindrome(n: int) -> bool:
    s = str(n)
    return s == s[::-1]

Then we use the bin function to convert the number to a binary number and write a predicate for base 2 palindromes. We need to cut away the 0b part of the string, hence the [2:] slice there.

def is_palindrome_base_2(n: int) -> bool:
    s = bin(n)[2:]
    return s == s[::-1]

For the solution we take the numbers below a million, filter for the palindromes, then filter for the palindromes in base 10, and sum up the results.

def solution() -> int:
    return sum(filter(is_palindrome_base_2, filter(is_palindrome, range(1, 1_000_000))))

As these are all just generators, it never creates a list anywhere. It really is equivalent to this procedural variant:

def solution_procedural() -> int:
    result = 0
    for candidate in range(1, 1_000_000):
        if not is_palindrome(candidate):
            continue
        if not is_palindrome_base_2(candidate):
            continue
        result += candidate
    return result

The runtime isn't much different, it is 222 ms for the functional one and 229.436 ms for the procedural one.