## Project Euler & HackerRank Problem 40 Solution

##### Champernowne’s constant

by {BetaProjects} | MAY 25, 2009 | Project Euler & HackerRank### Project Euler Problem 40 Statement

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021…

It can be seen that the 12^{th} digit of the fractional part is 1.

If *d*_{n} represents the *n*^{th} digit of the fractional part, find the value of the following expression.

*d*_{1} × *d*_{10} × *d*_{100} × *d*_{1000} × *d*_{10000} × *d*_{100000} × *d*_{1000000}

### Solution

A simple solution to this problem is to create a string just over one million digits long by concatenating the counting numbers starting from 1 to 185,185 (known as a Champernowne’s constant). Then multiply its digits together at the positions specified in the problem statement.

We know from the problem description that the first two terms *d*_{1} & *d*_{10} evaluate to 1 and, therefore, have no effect on the product. Here’s my early Perl implementation of this brute force method:

```
$s = '.'; $n = 1;
$s.= $n++ while(length($s) <= 1_000_000);
print substr($s,100,1)*substr($s,1e3,1)*substr($s,1e4,1)*substr($s,1e5,1)*substr($s,1e6,1);
```

Of course, this will not handle the more assailing parameters of the HackerRank Project Euler 40 version with seven positions in a 10^{18} digit number and running 100,000 consecutive test cases. So we devise a better approach.

#### Understanding the structure of Champernowne’s constant

You can think of the fractional part of Champernowne’s constant, hereinafter known simply as “the constant,” as many series of concatenated counting numbers. Each series represents an order of magnitude as follows:

Series (k) |
Range | Number of terms |
Number of digits in series |
Cumulative number of digits |
---|---|---|---|---|

1 | 1–9 | 9 | 9 | 9 |

2 | 10–99 | 90 | 180 | 189 |

3 | 100–999 | 900 | 2700 | 2889 |

4 | 1000–9999 | 9000 | 36000 | 38889 |

5 | 10000–99999 | 90000 | 450000 | 488889 |

We can make a few observations:

- The number of digits for every term in the series is the series number,
*k*. That is, series 4 is composed of 4–digit numbers. - The range for each series is 10
^{k−1}to 10^{k}−1 and has 9·10^{k−1}terms. - The total number of digits in each series is
*k*× number of terms. So, series 4 has 4×9000 = 36,000 digits.

#### Making single digits in the constant quickly accessible

We can reimagine this series of concatenated integers as a virtual array with 3 indexes. One index for the series (*k*), one for the term in the series, and another for the decimal position inside the term. All of these indexes are derived from a single index that describes a specific digit inside the constant. This is made possible by the organized construction of the constant.

#### A simple example

Let’s say we want the **37 ^{th}** digit inside the constant. A partial expansion of the constant from 1–25 looks like:

with the 37^{th} digit highlighted in red. We would decode **37** into the 3 indexes as follows:

Given, the constant broken up into series as described above:

Series 1: 1, 2, 3, 4, 5, 6, 7, 8, 9

Series 2: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, …, 99

- Find the series.
- Using the cumulative totals from table above, we determine the
**37**digit is in the 2^{th}^{nd}series (10–99) as 9 <**37**≤ 189.

- Using the cumulative totals from table above, we determine the
- Find the term in the series by determining its ordinal position.
- Calculate
**37**−9 (the number of cumulative digits from the previous series) = 28^{th}digit in the 2^{nd}series. - Then, (28−1) ÷ 2 = 13 (with remainder 1) is the term’s ordinal position.
- And finally, 13+10 (starting number of the series) = 23 is the term’s value.

- Calculate
- Find the correct digit in the term’s value—our answer.
- The remainder from the above division is our zero–based index to the correct digit in the term’s value. For this example, the index 1 is the 2
^{nd}digit of 23 =**3**.

- The remainder from the above division is our zero–based index to the correct digit in the term’s value. For this example, the index 1 is the 2

The **37 ^{th}** digit in the constant is 3.

#### A more robust example

Let’s take the **37371 ^{st}** digit in the constant as another example. We first need to find the series this digit resides:

```
#nDigits is an array for the number of digits in each series: 9, 180, 2700, …, 9·x·10^(x−1)
nDigits = [pow(10, x−1) * 9*x for x in xrange(1, 50)]
n = 37371
i = 0
while n>nDigits[i]: n-= nDigits[i]; i+= 1
```

At the end of this loop we find our digit, **37371**, is in the 4^{th} series which follows our understanding of the cumulative totals listed in the above table: 2889 < **37371** ≤ 38889.

**37371**−2889 = 34482, the 34482^{nd} digit in the series and (34482−1) ÷ 4 = 8620^{th} (remainder 1) term in the series. The index is (34482−1) because our series starts with an index base of 0.

We add the starting range from the 4^{th} series, 1000, to 8620 which equals 9620 as the term’s value. Since the remainder is 1, and we base our selection starting from 0, we take the second digit of this number as our answer.

The **37371 ^{st}** digit in the constant is 6.

#### HackerRank version

Instead of finding fixed indexes of *d* {1, 10, 100, …, 10000000} we are to find the product of 7 indexes between 1 and 10^{18} running 100,000 test cases. This algorithm works without change.

### Python Source Code

### Last Word

- Reference: The On–Line Encyclopedia of Integer Sequences (OEIS) A033307: Decimal expansion of Champernowne constant (or Mahler's number), formed by concatenating the positive integers.
- Modification to output K digits of the Chapnernowne constant starting at the N–th place for given 1 ≤ K ≤ 100, and 1 ≤ N ≤ 10
^{100}.