Problem 36: Double-base Palindromes

Mathematical Development

Definitions

Definition 1. Let $b \ge 2$ be an integer. A positive integer $n$ is a palindrome in base $b$ if its base-$b$ representation $(a_k, a_{k-1}, \ldots, a_1, a_0)_b$ with $a_k \ne 0$ satisfies $a_i = a_{k-i}$ for all $0 \le i \le k$.

Definition 2. A positive integer $n$ is a double-base palindrome if it is simultaneously a palindrome in base 10 and a palindrome in base 2.

Theoretical Development

Theorem 1 (Parity constraint). Every double-base palindrome is odd.

Proof. Let $n$ be a binary palindrome with representation $(b_k, b_{k-1}, \ldots, b_0)_2$, where $b_k = 1$ (since leading zeros are excluded). By Definition 1, $b_0 = b_k = 1$. Since $n = \sum_{i=0}^{k} b_i \cdot 2^i$ and $b_0 = 1$, we have $n \equiv 1 \pmod{2}$. $\blacksquare$

Corollary 1.1. All even numbers can be excluded from the search, halving the candidate space.

Lemma 1 (Enumeration of base-10 palindromes below $N = 10^6$). The number of base-10 palindromes in $\{1, 2, \ldots, N-1\}$ is exactly $1998$, partitioned by digit count as follows:

Proof. A $d$-digit palindrome is uniquely determined by its first $\lceil d/2 \rceil$ digits. The leading digit $a_1$ ranges over $\{1,\ldots,9\}$ (9 choices), and each subsequent free digit ranges over $\{0,\ldots,9\}$ (10 choices each). For $d$ digits, the count is $9 \cdot 10^{\lceil d/2 \rceil - 1}$. Summing: $9 + 9 + 90 + 90 + 900 + 900 = 1998$. $\blacksquare$

Lemma 2 (Binary palindrome test). A positive integer $n$ is a binary palindrome if and only if $\mathrm{rev}_2(n) = n$, where $\mathrm{rev}_2(n)$ denotes the integer obtained by reversing the binary digits of $n$. This test requires $\Theta(\lfloor \log_2 n \rfloor + 1)$ bit operations.

Proof. Let $n$ have $\ell = \lfloor \log_2 n \rfloor + 1$ binary digits. Construct $\mathrm{rev}_2(n)$ by iterating: extract the least significant bit of $n$ via $n \bmod 2$, append to an accumulator via left-shift-and-add, then right-shift $n$. After $\ell$ iterations, the accumulator equals $\mathrm{rev}_2(n)$. By Definition 1, $n$ is a binary palindrome iff this reversed value equals $n$. Each iteration performs $O(1)$ work, giving $\Theta(\ell)$ total. $\blacksquare$

Theorem 2 (Efficiency of palindrome generation). Generating all $P = 1998$ base-10 palindromes below $N = 10^6$ and testing each for the binary palindrome property requires $O(P \log N)$ operations, which is strictly less than the $O(N \log N)$ cost of testing every integer below $N$.

Proof. Each binary palindrome test on a number $n < N$ costs $O(\log_2 N) \le 20$. Testing all generated palindromes: $1998 \cdot 20 = 39{,}960$ operations. The brute-force alternative tests $10^6$ numbers at cost $10^6 \cdot 20 = 2 \times 10^7$. Since $P = 1998 \ll 10^6 = N$, the generation approach is superior by a factor of $N/P \approx 500$. $\blacksquare$

Editorial

We avoid scanning all integers below $10^6$ by generating only the decimal palindromes in that range. Each such palindrome is obtained by mirroring its free leading digits, and then its binary representation is tested for the same palindromic property. Summing exactly those candidates that pass both tests yields the required total.

Pseudocode

Algorithm: Sum of Double-base Palindromes
Require: The bound 10^6.
Ensure: The sum of all numbers below 10^6 that are palindromic in both base 10 and base 2.
1: Initialize total ← 0.
2: Generate every decimal palindrome below 10^6 by mirroring a positive seed, considering both even and odd lengths.
3: For each generated palindrome p, compute its binary expansion.
4: If that binary expansion is also palindromic, update total ← total + p.
5: Return total.

Complexity Analysis

Proposition. The algorithm runs in $O(P \cdot \log N)$ time and $O(1)$ auxiliary space, where $P = 1998$ and $N = 10^6$.

Proof. The generation phase enumerates exactly $P$ palindromes using nested loops with $O(1)$ work per palindrome (arithmetic construction, no string operations needed). Each palindrome is tested via $\mathrm{REV}_2$ in $O(\log_2 N) = O(20)$ time (Lemma 2). No arrays or sieves are required; only a running sum and loop variables are maintained. Total time: $O(P \cdot \log N)$. Auxiliary space: $O(1)$. $\blacksquare$

Answer

#include <bits/stdc++.h>
using namespace std;

bool isBinaryPalindrome(int n) {
    int rev = 0, orig = n;
    while (n > 0) {
        rev = (rev << 1) | (n & 1);
        n >>= 1;
    }
    return rev == orig;
}

int main() {
    int total = 0;

    // 1-digit palindromes
    for (int a = 1; a <= 9; a++)
        if (isBinaryPalindrome(a)) total += a;

    // 2-digit: aa
    for (int a = 1; a <= 9; a++) {
        int n = a * 11;
        if (isBinaryPalindrome(n)) total += n;
    }

    // 3-digit: aba
    for (int a = 1; a <= 9; a++)
        for (int b = 0; b <= 9; b++) {
            int n = a * 101 + b * 10;
            if (isBinaryPalindrome(n)) total += n;
        }

    // 4-digit: abba
    for (int a = 1; a <= 9; a++)
        for (int b = 0; b <= 9; b++) {
            int n = a * 1001 + b * 110;
            if (isBinaryPalindrome(n)) total += n;
        }

    // 5-digit: abcba
    for (int a = 1; a <= 9; a++)
        for (int b = 0; b <= 9; b++)
            for (int c = 0; c <= 9; c++) {
                int n = a * 10001 + b * 1010 + c * 100;
                if (isBinaryPalindrome(n)) total += n;
            }

    // 6-digit: abccba
    for (int a = 1; a <= 9; a++)
        for (int b = 0; b <= 9; b++)
            for (int c = 0; c <= 9; c++) {
                int n = a * 100001 + b * 10010 + c * 1100;
                if (isBinaryPalindrome(n)) total += n;
            }

    cout << total << endl;
    return 0;
}

"""Project Euler Problem 36: Double-base Palindromes"""

def is_binary_palindrome(n):
    rev, t = 0, n
    while t:
        rev = (rev << 1) | (t & 1)
        t >>= 1
    return rev == n

def generate_base10_palindromes(limit):
    pals = []
    for a in range(1, 10):
        if a < limit: pals.append(a)
    for a in range(1, 10):
        n = a * 11
        if n < limit: pals.append(n)
    for a in range(1, 10):
        for b in range(10):
            n = a * 101 + b * 10
            if n < limit: pals.append(n)
    for a in range(1, 10):
        for b in range(10):
            n = a * 1001 + b * 110
            if n < limit: pals.append(n)
    for a in range(1, 10):
        for b in range(10):
            for c in range(10):
                n = a * 10001 + b * 1010 + c * 100
                if n < limit: pals.append(n)
    for a in range(1, 10):
        for b in range(10):
            for c in range(10):
                n = a * 100001 + b * 10010 + c * 1100
                if n < limit: pals.append(n)
    return pals

total = sum(p for p in generate_base10_palindromes(1_000_000) if is_binary_palindrome(p))
print(total)