notes.html

problem 36 · 30 lines

<article>
<h3>Problem Analysis</h3>
<p>
I am asked to sum every positive integer below one million that is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> in base 10 and simultaneously a <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindrome</a> in base 2. A palindrome is a finite sequence of symbols that reads the same forwards and backwards; here the symbols are the decimal digits in one case and the binary bits in the other. The "no leading zeros" rule means the most-significant symbol must be nonzero in each base. For base 2 this is automatic: the highest bit of any positive integer is, by definition, a 1. For base 10 I simply have to avoid placing a zero in the leading position when I construct candidates.
</p>
<p>
The naive method - iterate over all N integers below the limit and test each in both bases - runs in O(N) and wastes effort, because decimal palindromes are extremely sparse among the integers. The observation that makes the problem tractable is that a decimal palindrome is completely determined by its <em>left half</em>. A k-digit prefix mirrored onto itself yields exactly one even-length palindrome of 2k digits, and inserting any of ten interior digits yields ten odd-length palindromes of 2k+1 digits. The number of distinct halves is on the order of the square root of N, so this <a class="reference-source" href="https://en.wikipedia.org/wiki/Generate_and_test" rel="noopener noreferrer" target="_blank">generate-and-test</a> strategy reduces the candidate count from O(N) to O(sqrt(N)). Each candidate is then checked for binary palindromicity in O(log N) time by inspecting its bits, so the overall cost is O(sqrt(N) log N) - which is why even the 9-digit case finishes in a fraction of a second.
</p>
<h3>Solution Approach</h3>
<h4>Decimal Palindrome Generation with a Binary Filter (s0 - Python and C)</h4>
<p>
Both files implement the same algorithm; I describe it once and note the language differences afterward.
</p>
<p>
<strong>Step 1 - single-digit seeds.</strong> The digits 1 through 9 are palindromes in every base by definition, so I emit each one (subject to the binary test). I handle them separately because the mirroring construction below would turn the half "1" into the two-digit string "11" - it can never reproduce the single-digit numbers themselves.
</p>
<p>
<strong>Step 2 - enumerate halves and mirror.</strong> The half loop runs over integers from 1 up to <code>10^(max_digits // 2) - 1</code>. For each value I take its decimal string, reverse it, and concatenate the two to form an even-length palindrome. This construction is exact and exhaustive: every even-length decimal palindrome with no leading zero is produced exactly once, since the half itself begins with a nonzero digit.
</p>
<p>
<strong>Step 3 - odd-length palindromes.</strong> When inserting a middle digit still fits the budget - guarded by <code>2 * num_digits &lt; max_digits</code> - I loop over middle digits 0 through 9 and form <code>half + mid + reverse(half)</code>. A middle digit of 0 is legal here because it is an interior symbol, not the leading one.
</p>
<p>
<strong>Step 4 - binary palindrome test.</strong> Each candidate is tested for binary palindromicity. In Python this is the one-liner <code>number == int(bin(number)[2:][::-1], 2)</code>: strip the <code>0b</code> prefix, reverse the bit string, parse it back, and compare. In C I extract bits one at a time into a small <code>char</code> array (least-significant bit first) and check <code>bits[i] == bits[len-1-i]</code>. A nice consequence falls out of the bit structure: an even number has its lowest bit 0, but a binary palindrome must have its highest bit 1, so even numbers can never pass - the test discards them implicitly at no extra cost.
</p>
<p>
<strong>Language differences.</strong> The Python version isolates generation in a <a class="reference-source" href="https://docs.python.org/3/glossary.html#term-generator" rel="noopener noreferrer" target="_blank">generator function</a> that <code>yield</code>s candidates lazily, with the filter applied in a generator expression inside <code>sum()</code>. The C version performs the same steps inline, building strings with <code>snprintf</code> and converting with <code>atoll</code>, and uses a small <code>int_pow10</code> helper for the loop bound. Both produce identical answers across every test case.
</p>
</article>