Project Euler Problem 36

Solution

Answer: 872187

We seek all integers $n < 10^6$ such that:

1. $n$ is a palindrome in base 10.
2. The binary representation of $n$ is also a palindrome.
3. No leading zeros are allowed in either representation.

We then sum all such numbers.

---

Mathematical analysis

A palindrome reads the same forwards and backwards.

For example:

• $585$ in decimal is:

$$585$$

which is palindromic.

• In binary:

$$585 = 1001001001_2$$

which is also palindromic.

We must find all such numbers below one million.

Key observations

1. Decimal palindromes are rare

Instead of checking every number from $1$ to $999999$, it is much faster to generate only decimal palindromes.

A 6-digit palindrome has the form:

$$abc|cba$$

A 5-digit palindrome has the form:

$$ab|c|ba$$

The number of decimal palindromes below one million is small:

• 1-digit: $9$
• 2-digit: $9$
• 3-digit: $90$
• 4-digit: $90$
• 5-digit: $900$
• 6-digit: $900$

Total:

$$9+9+90+90+900+900 = 1998$$

So instead of checking one million numbers, we only check about 2000.

---

2. Binary palindromes cannot end in 0

A binary palindrome cannot have leading zeros.

If a binary number ended in $0$, then by symmetry it would also begin with $0$, impossible.

Therefore every binary palindrome is odd.

Hence every valid number must be odd.

This immediately eliminates all even decimal palindromes.

---

3. Efficient palindrome testing

A string $s$ is palindromic iff:

$$s = s[::-1]$$

So:

• Decimal palindrome:

str(n) == str(n)[::-1]

• Binary palindrome:

b = bin(n)[2:]
b == b[::-1]

---

Python implementation

def is_palindrome(s):
    """Return True if string s is a palindrome."""
    return s == s[::-1]

total = 0

# Check every odd number below one million
for n in range(1, 1_000_000, 2):

    # Check decimal palindrome
    if is_palindrome(str(n)):

        # Convert to binary without '0b'
        b = bin(n)[2:]

        # Check binary palindrome
        if is_palindrome(b):
            total += n

print(total)

---

Code walkthrough

Palindrome helper

def is_palindrome(s):
    return s == s[::-1]

• s[::-1] reverses the string.
• Equality means the string reads identically forward and backward.

Examples:

is_palindrome("585")        # True
is_palindrome("1001001001") # True
is_palindrome("123")        # False

---

Initialize the sum

total = 0

This accumulates all qualifying numbers.

---

Iterate through candidates

for n in range(1, 1_000_000, 2):

• Start at 1.
• Stop before 1,000,000.
• Step by 2 so only odd numbers are checked.

Why only odd numbers?

Because binary palindromes must end in 1, hence they are odd.

---

Decimal palindrome check

if is_palindrome(str(n)):

Convert the number to decimal text and test symmetry.

Example:

str(585) -> "585"

which equals its reverse.

---

Binary conversion

b = bin(n)[2:]

• bin(585) gives:

'0b1001001001'

• [2:] removes the "0b" prefix.

So:

b = "1001001001"

---

Binary palindrome test

if is_palindrome(b):

Checks whether the binary digits are symmetric.

For $585$:

"1001001001" == "1001001001"[::-1]

True.

So $585$ is included.

---

Add to total

total += n

Accumulate all valid numbers.

---

Small example verification

The problem explicitly gives:

$$585 = 1001001001_2$$

Both are palindromes, so our program includes $585$.

Other small examples found:

Decimal	Binary	Both palindromic?
1	1	Yes
3	11	Yes
5	101	Yes
7	111	Yes
9	1001	Yes
10	1010	No

This matches expectations.

---

Final verification

• We only consider odd numbers, which is mathematically necessary.
• Every candidate is explicitly checked in both bases.
• The search space is comfortably small.
• The known Project Euler result for this problem is:

$$872187$$

So the computation is consistent.

---

Answer: 872187