notes.html

problem 40 · 27 lines

<article>
<h3>Problem Analysis</h3>
<p>
<a class="reference-source" href="https://en.wikipedia.org/wiki/Champernowne_constant" rel="noopener noreferrer" target="_blank">Champernowne's constant</a> is formed by concatenating the positive integers into an endless decimal string. The naive way to find the millionth digit - actually building that string - is wasteful: it would require gigabytes of memory and linear time in the position. The decisive observation is that the string is not random at all; it is a stack of regular <em>bands</em>, where each band collects all the integers with the same number of digits. The 1-digit numbers (1 through 9) contribute 9 * 1 = 9 characters; the 2-digit numbers (10 through 99) contribute 90 * 2 = 180 characters; and in general the band of d-digit numbers holds 9 * 10^(d-1) integers, each contributing d characters, for a band length of d * 9 * 10^(d-1) characters.
</p>
<p>
Because each band's length has a closed-form formula, I can locate any digit by accumulating band lengths - a running <a class="reference-source" href="https://en.wikipedia.org/wiki/Prefix_sum" rel="noopener noreferrer" target="_blank">prefix sum</a> - until the total first reaches or exceeds the target position. That tells me which band the position falls in; two integer operations (<a class="reference-source" href="https://en.wikipedia.org/wiki/Division_(mathematics)#Of_integers" rel="noopener noreferrer" target="_blank">floor division</a> and <a class="reference-source" href="https://en.wikipedia.org/wiki/Modulo" rel="noopener noreferrer" target="_blank">modulo</a>) then pinpoint the exact integer and the exact digit within it. The number of bands to examine is bounded by the number of digits in the target position, so each lookup costs <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(log n)</a> integer operations. Since the problem asks for only a handful of digits (positions 10^0 through 10^6), the total work is a few dozen integer operations and the runtime is effectively immeasurable.
</p>
<h3>Solution Approach</h3>
<h4>Arithmetic band-walk (Python and C)</h4>
<p>
The Python file <code>p0040_s0.py</code> and the C file <code>p0040_s0.c</code> implement the same algorithm. The core lookup is <code>get_nth_digit_champernowne_s_constant</code> in Python and <code>get_nth_digit_champernowne</code> in C.
</p>
<p>
<strong>Step 1 - find the band.</strong> I keep two running totals: <code>length_till_num_digits</code>, the number of characters contributed by all bands strictly before the current one, and <code>length_with_num_digits</code>, the same total after including the current band. On each iteration I increment <code>num_digits</code>, copy the old running total into <code>length_till_num_digits</code>, then add the band length <code>num_digits * 9 * 10^(num_digits-1)</code>. I stop as soon as <code>length_with_num_digits</code> reaches or exceeds <code>n</code>. At that point <code>num_digits</code> is the digit-length of the numbers in the band containing position <code>n</code>, and the two totals bracket that band's start and end. This is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Prefix_sum" rel="noopener noreferrer" target="_blank">prefix sum</a> comparison made concrete.
</p>
<p>
<strong>Step 2 - find the offset within the band.</strong> I compute <code>offset_of_number = n - length_till_num_digits - 1</code>. Subtracting <code>length_till_num_digits</code> measures how far into the band we are; the extra <code>-1</code> converts the problem's 1-based digit numbering into a 0-based index. Then <a class="reference-source" href="https://en.wikipedia.org/wiki/Division_(mathematics)#Of_integers" rel="noopener noreferrer" target="_blank">floor division</a> by <code>num_digits</code> gives the index of the number within the band, and the <a class="reference-source" href="https://en.wikipedia.org/wiki/Modulo" rel="noopener noreferrer" target="_blank">modulo</a> gives the index of the digit within that number.
</p>
<p>
<strong>Step 3 - recover the digit.</strong> The first number in the d-digit band is 10^(d-1), so the target number is <code>10^(num_digits-1) + offset_of_number // num_digits</code>. In Python I render the number with <code>str</code> and index the requested character, converting back to <code>int</code>. In C I format the number into a small stack buffer with <code>snprintf</code> and subtract <code>'0'</code> from the indexed character.
</p>
<p>
The driver loops over k from 0 to i inclusive, querying position 10^k each time and accumulating the product. Python expresses this declaratively with <a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.reduce" rel="noopener noreferrer" target="_blank"><code>functools.reduce</code></a> folding a multiplication over a generator. C uses a plain loop, multiplying the running <code>pos</code> by 10 on each iteration to avoid recomputing the power. Both compute 10^(num_digits-1) and the band length with short explicit multiplication loops in C, which sidesteps the floating-point inaccuracy that <a class="reference-source" href="https://en.wikipedia.org/wiki/C_mathematical_functions" rel="noopener noreferrer" target="_blank"><code>pow</code></a> would introduce.
</p>
</article>