Foreshadowing

Although the Brute force solution is fast, it will not scale well for larger values and is not an elegant solution. To find a better solution, we need to understand how the champernowne constant is constructed.

For instance, a one-digit number (\(0...9\)) represents \( 9 \) digits in the string. Meanwhile, a two-digit number (\(10...99\)) represents \( 180 \) digits in the string. This is because there are \( 99 - 9 \) number between \( 10 \) and \( 99 \) with each two digits. Thus, their concatenation results in \( 180 \) digits.

By examining the construction of the champernowne constant, we can find a pattern with \( d \) digits:

\( d = 1 \): \( 1 \times (9 - 0) = 1 \times 9 = 9 \) digits
\( d = 2 \): \( 2 \times (99 - 9) = 2 \times 90 = 180 \) digits
\( d = 3 \): \( 3 \times (999 - 99) = 3 \times 900 = 2700 \) digits
\( d = 4 \): \( 4 \times (9999 - 999) = 4 \times 9000 = 36000 \) digits

We can observ a clear pattern. Specifically, for number with \( d \) digits, the number of digits of the concatenation is \( p(d) = 9d * 10^{d-1} \).

This patten allows us to divide the constant into chunks of digits that correspond to the concatenation of numbers with the same number of digits. For instance:

The first number with one digit starts at the \( 1^{th} \) digit of the champernowne constant.
The first number with two digits starts at the \( 1 + 9 = 10^{th} \) digit of the champernowne constant.
The first number with three digits start at the \( 1 + 9 + 180 = 190^{th} \) digit of the champernowne constant.

To find the first number with \( d \) digits, we just need to sum the number of digits of all numbers with fewer digits. We can define \( s(d) = 1 + \sum_{i=1}^{d-1} p(i) \) as the index of the first number with \( d \) digits in the champernowne constant.

Being able to find the first number with \( d \) digits is very useful. Let's say we want to find \( d(1000) \), we know that \( s(3) = 190 \) and \( s(4) = 2890 \). Thus, \( d(1000) \) is among the numbers with three digits. The first number with three digits is at index \( 190 \), the second at index \( 190 + 3 \), the third at index \( 190 + 6 \) and so on. To generalize, \( d(190 + 3k) \) is the first digit of the \( (100 + k)^{th} \) number. We just need to find the greatest \( k \) such that \( 190 + 3k \leq 1001 \), which is \( k = 270 \). So \( d(190 + 3 \times 270) = d(1000) \) is the first digit of \( 10^{d-1} + k = 100 + 270 = 370 \). Hence \( d(1001) = 7 \).

In summary, to find \( d(n) \), we need to first search in which chunk of digits it lies. This is achieved by finding the largest \( d \) such that \( s(d) \leq n \). Next, we need to find the index of the number that contains \( d(n) \). This is done by finding the largest \( k \) such that \( s(d) + d \times k \leq n \). Finally, we can extract the \( (n - (s(d) + k \times d))^{th} \) digit from this number to obtain \( d(n) \).

From solution2.py:

def d(n):
    s = lambda n: 1 + 9 * sum(i * 10 ** (i - 1) for i in range(1, n))
    digit = 1
    while s(digit) <= n:
        digit += 1
    digit -= 1
    sd = s(digit)
    k = floor((n - sd) / digit)
    number = str(10 ** (digit - 1) + k)
    return int(number[n - (sd + k * digit)])

The final solution is obtained by multiplying the digit with the index of the problem.

From solution2.py:

def champernownes_constant():
    return reduce(operator.mul, (d(10**i) for i in range(7)))

Project Euler

Foreshadowing