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₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × 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₁ & d₁₀ 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¹⁸ 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:

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^th digit is in the 2^nd 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) = 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.
• 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 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.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 40

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

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¹⁰⁰.