Detailed mathematical approach

Problem Summary

We seek every integer \(n\) with \(1 \le n < 10^6\) whose standard decimal representation and standard binary representation are both palindromes. The required result is the sum of all such numbers.

The phrase "without leading zeros" matters. In base 10 we already use the usual decimal writing, and in base 2 we use the canonical binary expansion. So a number like \(10\) is binary \(1010_2\), not \(01010_2\), and only the canonical form is allowed in the palindrome test.

Mathematical Approach

The problem is small enough that a direct search is completely practical, but the search is guided by a few clean structural facts about palindromes in two bases.

Digit symmetry in base 10 and base 2

Write the decimal expansion of \(n\) as

$n=d_{m-1}10^{m-1}+d_{m-2}10^{m-2}+\cdots+d_1 10+d_0,$

with \(d_{m-1}\neq 0\). Write the binary expansion as

$n=b_{\ell-1}2^{\ell-1}+b_{\ell-2}2^{\ell-2}+\cdots+b_1 2+b_0,$

with \(b_{\ell-1}=1\). The two palindrome conditions are simply

$d_i=d_{m-1-i}\quad\text{for }0\le i<m,$

and

$b_j=b_{\ell-1-j}\quad\text{for }0\le j<\ell.$

So the entire task is to find integers whose decimal digit string and binary digit string are both mirror-symmetric around the center.

An immediate binary consequence: every valid number is odd

Because the binary expansion has no leading zeros, its first digit is always \(1\). If the binary string is also a palindrome, the last digit must match the first one, so \(b_0=1\) as well. But \(b_0\) is exactly the parity bit, therefore every double-base palindrome is odd.

This does not change the mathematical definition, but it explains why even numbers can never contribute to the sum. The implementations keep the simpler full scan, yet the binary palindrome test rejects all even inputs automatically.

Size bounds for this problem

Since the search stops below \(10^6\), a decimal candidate has at most six digits. In binary we have

$2^{19}=524288 < 10^6 < 2^{20}=1048576,$

so every candidate has at most twenty binary digits. That means each palindrome check is tiny: at most 6 character comparisons for the decimal string and at most 20 characters in the binary string.

There are also only

$\sum_{k=1}^{6} 9\cdot 10^{\lceil k/2\rceil-1}=9+9+90+90+900+900=1998$

decimal palindromes below one million. This count shows how restrictive the condition already is, even before imposing the binary palindrome condition.

Worked example: \(585\)

The example from the statement is a good illustration because both symmetries are visible. In decimal,

$585=5\cdot 10^2+8\cdot 10+5,$

so the digit pattern is \(5,8,5\), which reads the same from either side.

In binary, repeated division by 2 gives

$585=2^9+2^6+2^3+2^0=1001001001_2.$

The binary digits are again symmetric: the first and last bits are \(1\), the second and next-to-last are \(0\), and so on. Therefore \(585\) is one of the terms that must be added.

Why a direct search is enough

A more optimized strategy could generate only decimal palindromes first, but the implementations intentionally use the simpler method: scan all integers from \(1\) up to the limit, test decimal symmetry, build the binary expansion, and test binary symmetry. Because the upper bound is only one million and the digit lengths are so small, that straightforward approach is already fast enough.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They accept an optional upper limit, defaulting to \(10^6\), and they optionally run small checkpoints before the full computation.

The main loop visits each integer \(n\) with \(1 \le n < \text{limit}\). First the implementation converts \(n\) to its decimal string and compares mirrored positions from the two ends toward the center. If any pair differs, \(n\) is discarded immediately.

If the decimal test succeeds, the implementation constructs the binary representation manually. It repeatedly takes the least significant bit, appends the corresponding character, and divides by 2. After \(t\) iterations, the collected characters are exactly the lowest \(t\) bits of \(n\), written from low bit to high bit; reversing that sequence yields the canonical binary expansion with no leading zeros. The same mirrored-character palindrome test is then applied to the binary string.

Whenever both tests succeed, the number is added to a running sum. The optional checkpoints verify two things: the palindrome test accepts a known symmetric string, and the partial sum below \(1000\) is \(1772\). Those checks ensure that both the symmetry logic and the accumulation logic are behaving correctly before the full run.

Complexity Analysis

Let \(L\) be the limit. The implementation examines every integer from \(1\) to \(L-1\), so there are \(O(L)\) candidates. For each one, decimal conversion and the decimal palindrome test cost \(O(\log_{10} L)\), while binary conversion and the binary palindrome test cost \(O(\log_2 L)\). Therefore the total running time is

$O(L\log L).$

The extra space per candidate is \(O(\log L)\), because the implementation stores short decimal and binary strings. For the specific Project Euler bound \(L=10^6\), those strings never exceed 6 and 20 characters respectively, so the constant factors are very small.

Footnotes and References

1. Project Euler problem page: Project Euler 36 - Double-base palindromes
2. Palindromic numbers: Wikipedia - Palindromic number
3. Binary numerals: Wikipedia - Binary number
4. Positional notation: Wikipedia - Positional notation