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 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


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, d_{100} 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s