Project Euler/40/Solution

Main article: Project Euler/40

Solution

Here is a calculation of the product $ d_1 \times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000} $, where $ d_n $ is the $ n $-th digit of the Champernowne constant $ C_{10} = 0.123456789101112... $.

We use the established method involving cumulative digit counts ($ C_k $) for blocks of $ k $-digit numbers.

• $ C_1 = 9 $
• $ C_2 = 189 $
• $ C_3 = 2889 $
• $ C_4 = 38889 $
• $ C_5 = 488889 $
• $ C_6 = 5888889 $

Finding the Digits

• Finding $ d_1 $

The first digit ($ n=1 $) is the first digit of '1'.

$ d_1 = 1 $

• Finding $ d_{10} $

$ n=10 $. Falls into the 2-digit block ($ k=2 $), since $ C_1 < 10 \le C_2 $.

Position within block: $ m = n - C_1 = 10 - 9 = 1 $.

Integer index ($ 0 $-based): $ num\_index = \lfloor (m-1)/k \rfloor = \lfloor (1-1)/2 \rfloor = 0 $.

Integer $ N = 10^{k-1} + num\_index = 10^{2-1} + 0 = 10 $.

Digit position within $ N $ ($ 1 $-based): $ digit\_pos = (m-1) \pmod{k} + 1 = (1-1) \pmod 2 + 1 = 1 $. The 1st digit of 10.

$ d_{10} = 1 $

• Finding $ d_{100} $

$ n=100 $. Falls into the 2-digit block ($ k=2 $), since $ C_1 < 100 \le C_2 $.

Position within block: $ m = 100 - C_1 = 100 - 9 = 91 $.

Integer index: $ num\_index = \lfloor (91-1)/2 \rfloor = \lfloor 90/2 \rfloor = 45 $.

Integer $ N = 10^{2-1} + 45 = 10 + 45 = 55 $.

Digit position: $ digit\_pos = (91-1) \pmod 2 + 1 = 90 \pmod 2 + 1 = 1 $. The 1st digit of 55.

$ d_{100} = 5 $

• Finding $ d_{1000} $

$ n=1000 $. Falls into the 3-digit block ($ k=3 $), since $ C_2 < 1000 \le C_3 $.

Position within block: $ m = 1000 - C_2 = 1000 - 189 = 811 $.

Integer index: $ num\_index = \lfloor (811-1)/3 \rfloor = \lfloor 810/3 \rfloor = 270 $.

Integer $ N = 10^{3-1} + 270 = 100 + 270 = 370 $.

Digit position: $ digit\_pos = (811-1) \pmod 3 + 1 = 810 \pmod 3 + 1 = 1 $. The 1st digit of 370.

$ d_{1000} = 3 $

• Finding $ d_{10000} $

$ n=10000 $. Falls into the 4-digit block ($ k=4 $), since $ C_3 < 10000 \le C_4 $.

Position within block: $ m = 10000 - C_3 = 10000 - 2889 = 7111 $.

Integer index: $ num\_index = \lfloor (7111-1)/4 \rfloor = \lfloor 7110/4 \rfloor = 1777 $.

Integer $ N = 10^{4-1} + 1777 = 1000 + 1777 = 2777 $.

Digit position: $ digit\_pos = (7111-1) \pmod 4 + 1 = 7110 \pmod 4 + 1 = 2 + 1 = 3 $. The 3rd digit of 2777.

$ d_{10000} = 7 $

• Finding $ d_{100000} $

$ n=100000 $. Falls into the 5-digit block ($ k=5 $), since $ C_4 < 100000 \le C_5 $.

Position within block: $ m = 100000 - C_4 = 100000 - 38889 = 61111 $.

Integer index: $ num\_index = \lfloor (61111-1)/5 \rfloor = \lfloor 61110/5 \rfloor = 12222 $.

Integer $ N = 10^{5-1} + 12222 = 10000 + 12222 = 22222 $.

Digit position: $ digit\_pos = (61111-1) \pmod 5 + 1 = 61110 \pmod 5 + 1 = 0 + 1 = 1 $. The 1st digit of 22222.

$ d_{100000} = 2 $

• Finding $ d_{1000000} $

$ n=1000000 $. Falls into the 6-digit block ($ k=6 $), since $ C_5 < 1000000 \le C_6 $.

Position within block: $ m = 1000000 - C_5 = 1000000 - 488889 = 511111 $.

Integer index: $ num\_index = \lfloor (511111 - 1) / 6 \rfloor = \lfloor 511110 / 6 \rfloor = 85185 $.

Integer $ N = 10^{6-1} + 85185 = 100000 + 85185 = 185185 $.

Digit position: $ digit\_pos = (511111 - 1) \pmod 6 + 1 = 511110 \pmod 6 + 1 = 0 + 1 = 1 $. The 1st digit of 185185.

$ d_{1000000} = 1 $

Calculating the Product

We need to compute the product $ P $:

$ P = d_1 \times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000} $

$ P = 1 \times 1 \times 5 \times 3 \times 7 \times 2 \times 1 $

$ P = 105 \times 2 $

$ P = 210 $

The product of the specified digits is 210.