## Project Euler Problem 40 Solution

Champernowne’s constant

by {BetaProjects} | 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 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

### 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 d1 & d10 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 1018 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 10k−1 to 10k−1 and has 9·10k−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 37th digit inside the constant. A partial expansion of the constant from 1–25 looks like:

12345678910111213141516171819202122232425

with the 37th 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 37th digit is in the 2nd series (10–99) as 9 < 37 ≤ 189.
• Find the term in the series by determining its ordinal position.
• Calculate 37−9 (the number of cumulative digits from the previous series) = 28th digit in the 2nd 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.
• 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 2nd digit of 23 = 3.

The 37th digit in the constant is 3.

#### A more robust example

Let’s take the 37371st 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 4th series which follows our understanding of the cumulative totals listed in the above table: 2889 < 37371 ≤ 38889.

37371−2889 = 34482, the 34482nd digit in the series and (34482−1) ÷ 4 = 8620th (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 4th 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.

#### 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 1018 running 100,000 test cases. This algorithm works without change.

### Python Source Code

``````q = [9*(x+1) * pow(10, x) for x in range(20)]
def d(n):
i=0
while n>q[i]: n-= q[i]; i+= 1
L, d = divmod((n-1), i+1)
return int(str(pow(10, i)+L)[d])
n = input("Enter some indicies, separated by a space? ")
m = 1
for ci in map(int, n.split()):
m*= d(ci)
print ("product =", m)	``````