Detailed mathematical approach

Problem Summary

Champernowne's constant in base 10 is \(C_{10}=0.1234567891011121314\ldots\), obtained by concatenating the positive integers in order. If \(d(n)\) denotes the \(n\)-th digit after the decimal point, the problem asks for the product

$d(1)\,d(10)\,d(100)\,d(1000)\,d(10000)\,d(100000)\,d(1000000).$

The central issue is an indexing problem inside an infinite decimal string. We only need seven specific digits, so the question is how to reach those digits cleanly and efficiently.

Mathematical Approach

The implementations use a left-to-right scan of the decimal expansion of \(1,2,3,\ldots\). That choice is mathematically justified because the requested positions are sparse, ordered, and small enough that the scan ends quickly. The natural framework is to organize the concatenation by digit length.

Digit Blocks of the Concatenation

All \(k\)-digit integers form one contiguous block inside Champernowne's constant. There are \(9\cdot 10^{k-1}\) such integers, and each contributes \(k\) digits, so the block contributes

$B_k=9k\cdot 10^{k-1}$

digits in total. The first values are

$B_1=9,\qquad B_2=180,\qquad B_3=2700,\qquad B_4=36000,\qquad B_5=450000.$

If we define the cumulative total

$S_m=\sum_{k=1}^{m} B_k,$

then \(S_m\) counts all digits contributed by integers with at most \(m\) digits. In particular,

$S_5=9+180+2700+36000+450000=488889.$

So the position \(10^6\) lies in the 6-digit block rather than deep inside the sequence.

The Relevant Checkpoints

The only positions that matter are the powers of ten

$T_p=10^p \qquad (p=0,1,\dots,6).$

These checkpoints are strictly increasing. That means a single forward pass is enough: once the scan has consumed the first \(q\) digits of the concatenation, every checkpoint at most \(q\) has already been resolved, and every larger checkpoint still lies ahead. No backtracking and no random access are needed.

A Prefix-Length Formula

If the scan has processed all integers from \(1\) through some \(d\)-digit integer \(n\), then the number of emitted digits is

$L(n)=\sum_{k=1}^{d-1} 9k\cdot 10^{k-1}+d\bigl(n-10^{d-1}+1\bigr).$

The code does not evaluate this formula directly, but it explains why the streaming method is small-scale. Since \(S_5=488889\), we still need

$10^6-S_5=511111$

digits from the 6-digit block. Because each 6-digit number contributes 6 digits, the scan needs

$\left\lceil \frac{511111}{6} \right\rceil = 85186$

six-digit integers, ending at \(100000+85186-1=185185\). So even the largest requested digit appears after scanning only up to 185185.

Worked Example: The First Three Checkpoints

The built-in checkpoint used by the implementations asks for the product at positions \(1\), \(10\), and \(100\).

For \(d(1)\), the answer is immediately \(1\). For \(d(10)\), the first 9 digits come from \(1\) through \(9\), so the 10th digit is the first digit of \(10\), again \(1\).

For \(d(100)\), remove the first 9 digits. The target is now the 91st digit inside the 2-digit block. Since each 2-digit number contributes 2 digits,

$\left\lfloor \frac{91-1}{2} \right\rfloor = 45$

shows that we are in the \(46\)-th two-digit number, namely \(10+45=55\). The position inside that number is

$(91-1)\bmod 2=0,$

so the desired digit is the first digit of \(55\), which is \(5\). Therefore

$d(1)\,d(10)\,d(100)=1\cdot 1\cdot 5=5,$

exactly matching the small verification case used by the implementations.

How the Code Works

The C++, Python, and Java implementations all use the same streaming strategy. They never build the whole million-digit prefix as one string. Instead, they walk through the integers in order, expose their decimal digits one by one, and update a tiny amount of state.

Preparing the Target Positions

The implementation first constructs the finite target list \(1,10,100,\dots,10^m\), with the default choice \(m=6\). While building that list, it guards against overflow before multiplying by 10, so the target positions always remain valid for the host integer type.

Streaming Through the Decimal Expansion

Next, the program iterates through the positive integers \(1,2,3,\ldots\). Each integer is converted to its decimal form, and its digits are processed from left to right. One running counter records the current position in Champernowne's constant, and another index marks the next unresolved checkpoint.

The key invariant is this: after processing the integers up to \(n\), the position counter equals \(L(n)\), the total number of digits emitted so far. Therefore, whenever the counter lands on the next checkpoint, the current digit is exactly the required value \(d(10^p)\), and it can be multiplied into the accumulated product immediately.

Early Termination

Because the checkpoints are sorted, the scan stops as soon as the digit at the largest requested position has been consumed. For the Project Euler instance this is the digit at position \(10^6\). Nothing beyond that point can affect the answer, so the computation ends at once.

Sanity Checks

Before returning the final product, each implementation can verify two small cases. The first asks for positions up to \(10^2\) and must return \(5\). The second asks only for position \(10^0\) and must return \(1\). These tests validate the target generation, the streaming logic, and the multiplicative accumulation together.

Complexity Analysis

If the largest requested checkpoint is \(10^m\), the algorithm processes exactly \(10^m\) emitted digits, so the running time is \(O(10^m)\). In the actual problem, \(m=6\), which means one million digit visits and a scan only up to the integer \(185185\).

The extra memory usage is \(O(m)\) for the checkpoint list, plus the decimal representation of the current integer. For the default input this is effectively constant space. The important practical point is that the code streams digits on demand instead of storing the entire concatenated prefix.

Footnotes and References

1. Problem page: Project Euler 40
2. Champernowne's constant: Wikipedia - Champernowne constant
3. Decimal representation: Wikipedia - Decimal
4. Positional notation: Wikipedia - Positional notation