Project Euler 40: Finding the n^th digit of the fractional part of an irrational number

Project Euler 40 Problem Description

Project Euler 40: 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

Analysis

A simple solution is to create a string one million digits long by concatenating the counting numbers starting from 1 to 185,185 (known as Champernowne's constant). Then multiply together the single digits at the positions specified in the problem statememt. We know from the problem description that the first two terms d₁ & d₁₀ will 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 "Answer to PE40 = ",
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 7 positions in a 10¹⁸ digit number run with 100,000 consecutive trials. A better approach must be devised.

You can think of Champernowne's constant, hereinafter known simply as "constant," as a concatenation of many series of concatenated counting numbers. Each series represents an order of magnitude or, more succinctly, a power of 10 as follows:

We can make a few observations:

• The size of each term in the series is the series number, k. That is, series 4 is composed of 4-digit numbers.
• The range for each series, k, is 10^k-1 to 10^k-1 and has 9·10^k-1 terms.
• The number of digits in each series is k * number of terms. So, series 4 is 4 * 9000 = 36000 digits

Making single digits in the constant accessible

We can reimagine this series of concatenated numbers as an array with 3 indexes. One for the series, one for the term in the series, and one for the decimal position inside the term. All of these indexes will be derived from a single index that describes the digit inside the constant. This is made possible by the organized construction of the constant.

A simple example

Let's say we want the 27th digit inside the constant. We would decode 27 into the 3 indexes as follows:
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,…,99

• All indexes, except the series, start with a base of zero. The 18th term is index 17; always one less.
• We would first determine the 27th digit is in the 2nd series as 9 < 27 ≤ 9+180.
• Since all terms in the 2nd series are 2-digits we find our term index 27-9 = 18th term in the constant and (18-1)/2 = 8 (remainder 1) as the series index or 9th in the series.
• Adding 10 (the start of the 2nd series) to 8 gives us our value as 18.
• The remainder is our last index and, again, starting from 0, points to the digit in the term. In this example the 2nd (index 1) character of 18 is the number 8.

The 27th digit in the constant is 8.

A more robust example

Let's take the 37371st digit in the constant as an example. We need first to find the series the digit resides:

#bc is the character length of each series: 9, 180, 2700, ..., 9·x·10^(x-1) 
sc = [pow(10, x-1) * 9*x for x in xrange(1, 50)]
n = 37371
i = 0
while n>sc[i]: n-= sc[i]; i+= 1

At the end of this loop we find our digit, 37371, is in the 4th series which follows our understanding: 9+180+2700 < 37371 ≤ 9+180+2700+36000. Since all the terms in the 4th series are 4-digits we take the residual value of n, the 34482nd term in the constant or (34482-1)/4 = 8620 (remainder 1) in the series. The index is (34482-1) because our series starts with an index base of 0.

We add the starting range, 1,000, for series 4 and 9620 is the term's value. Since the remainder is 1, and we base our substring selection starting from 0, we take the second digit of this number for our answer.

The 37371st digit in the constant is 6.

This program and method
solves all test cases for
Project Euler 40 on HackerRank

Project Euler 40 Solution

Afterthoughts

• 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.
  
• Mathematica: Times @@ Flatten[IntegerDigits@Range@2*^5][[10^Range@6]]