2014-09-24

# Problem 040: Champernowne's constant

Description:

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 d(n) represents the nth digit of the fractional part, find the value of the following expression.

d(1) × d(10) × d(100) × d(1000) × d(10000) × d(100000) × d(1000000)

Solution:
v
>01:55+*:55+*:55+*:55+*:55+*:55+*130p v
v                                           <
>110p120p>:10g920g**`!#v_10g920g**-10g1+10p20g55+*20p^>v          <
>30g.@               >1-:10g/20g+\      10g%10g\-1-:|>\55+/\1-:#^_v
\$                                   \$               >           :^
^_^#:                                 <#                p03*g03%+55\$<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

This one is really great - I came up with an O(log n) algorithm (crazy fast) for determining the n-th digit.
First I tested it in LinqPad, so here the C# code for the algorithm:

``````public int digitAt(int pos) {
int digitcount = 1;
int digitvalue = 1;

// Get DigitCount of current number
while(pos > digitvalue * 9 * digitcount) {
pos -= digitvalue * 9 * digitcount;
digitcount++;
digitvalue *= 10;
}

// current number and digit-position in number
int value = digitvalue + (pos - 1)/digitcount;
int digit = digitcount - (pos - 1)%digitcount - 1;

return getInternalDigit(value, digit);
}

public int getInternalDigit(int value, int digit) {
return (value / (int)Math.Pow(10, digit)) % 10;
}``````

 Interpreter steps: 1 486 Execution time (BefunExec): 16ms (0.09 MHz) Program size: 69 x 7 (fully conform befunge-93) Solution: 210 Solved at: 2014-09-24

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript