Problem 040

---

Project Euler

Digit factorials

Champernowne’s constant

Problem 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

---

This is similar to Problem 17 where we could the letter of the number. This time we count the number of digits. For example, the first 9 position of the decimal corresponding to 1 to 9. The number 10-99 (90 of these number) will occupy 2 digit each. Thus, the position of the decimal will correspond to position 10 – 189 (90×2+9). We can calculate the minimum and maximum position by any group with the same number of digits.

void initialize () {
  digitLimit[0] = 0;

  for (int i = 1; i < MAXDIGIT; ++i) { 
    unsigned long d = (unsigned long) i;
    unsigned long min = (unsigned long) pow(10,d-1);
    unsigned long max = (unsigned long) pow(10,d) - 1;
    digitLimit[i] = ((max - min + 1) * d) + digitLimit[i-1];
  }
}

With this, we can find the digit by comparing the position we are looking for against the list of limit. Then we find the position of the group by subtraction (position – previous digit group limit). Next, we divide the result by the number of digits representing the group to find which number the digit reside in. Finally, we get the remainder from our previous division to get the position of the digit within the number.

For example, is looking for decimal position at 100. Since, 9 < 100 < 189. We know position 100 in the two-digits group. The number it corresponding to is ( 100-9) / 2 + 9 = 89 / 2 + 10 = 54. The remainder is 1 so take the first digit of 54 is 5. Following this logic will get the product of all 7 digits.