Project Euler Solution #40: Champernowne's constant

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

If we had a function getDigit(n), which returns the n^th digit of the decimal number, we could simply build the product of the 7 numbers:

function solution() {
 var res = 1;
 for (var i = 0; i < 7; i++) {
   res*= getDigit(10**i);
 }
 return res;
}

That seems obvious, but how can we get the digits? When we list the decimal places again, we get

\[\underbrace{123456789}_{\text{1x}}\underbrace{101112...99}_{\text{2x}}\underbrace{100101102...999}_{\text{3x}}...\]

Since we get \(n\) as the position in this number, we need to find a way of saying in what block the number is and what the dimension of the block is. If we take \(n=12\) for example, it's clear that the digit we need to return is 1, within the number 11, in the block of two digit numbers, which ranges from 10 to 99. Since we only get the position, more importantly we need to categorize a block by it's digit position, which means that the second block ranges from index 10 to 189, which is just the cumulative length of each block. We know the first block has 9 one-digit numbers, the second has 90 two-digit numbers, the third has 900 three-digit numbers and so on, from which follows that the cumulative sum of digits until block \(m\) is

\[\sum\limits_{i=1}^m i\cdot(10^i - 10^{i-1}) = \sum\limits_{i=1}^m i\cdot 9\cdot 10^{i-1} = 10^m \left(m-\frac{1}{9}\right)+\frac{1}{9}\]

That's cool, we got a closed form solution for that! However, that isn't much helpful, since we get an index \(n\) and would need the inverse of that function - which is not possible to find without iteration. But implementing a simple iterative algorithm can solve for all desired variables at once. Let's say \(r\) is the upper bound of the previous block and \(s\) is the upper bound of the current block \(k\):

var r, s = 0, k = 0;
while (s < n) {
 r = s;
 k++;
 s+= k * 9 * 10**(k-1);
}

All we now have to do is to reconstruct the number in which the requested index \(n\) falls into. Its offset is \(10^{k-1}\) and within the block it's the original index \(n\) reduced by 1 (to make it zero indexed) reduced by the previous upper bound, all divided by the length of the current index. Of the so created number \(t\), we want digit \(p = (n - r - 1) \mod k\). That means

\[t = 10^{k-1} + \left\lfloor \frac{n - r - 1}{k} \right\rfloor\]

Okay, at the end we need a way of getting the p^th digit of number \(t\). I'm lazy now and simply convert it to a string, extract the digit and convert it back to a number. This way we can ignore the floor function as well, since we're interested in the integer part digits only. The whole algorithm then looks like this:

function getDigit(n) {
 var r, s = 0, k = 0;
 while (s < n) {
   r = s;
   s+= 9 * 10**k++ * k;
 }
 var h = n - r - 1;
 var t = 10**(k - 1) + h / k;
 var p = h % k;
 return +String(t)[p];
}