Project Euler 40: Finding the nth digit of the fractional part of the irrational number

I am currently sitting in a train, and writing this post since I solved problem 40 in Project Euler using pen & paper waiting for my computer to start up and get online.  It is not a terribly difficult problem to answer, at least it wasn’t for me. The problem reads

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 x d10 x d100 x d1000 x d10000 x d100000 x d1000000

I read the problem description last night and started solving it in my head, but I quickly get lost when I handle numbers, so I knew that I needed a scrap of paper in order to jot down my notes.

The integers 1-9 represents digit 1-9 in the fraction which is easy to deduct. The integers 10-99 represents the digits 10-189 in the fraction and so on. We need to make this exercise until we reach a million digits which gives us

1-9: 1-9
10-99: 10-189
100-999: 190-2.889
1.000-9.999:  2.890-38.889
10.000-99.999: 38.890 – 488.889
100.000-999.999: 488.890 – 5.888.889

As an example I will start with finding d1000. We are in the 100-999 range so we deduct 189 which  is the starting point of that number. Which gives us 1000-189 = 811. Each number is 3 dgits, so we are at number 811/3 + 99 = 369 with 1/3 left over. So the digit we are looking for is 1/3 into 370, meaning the first digit of 370 => 3

So with the given example, I think we are ready to plow through the 7 digits we need to find for the solution:

d1 :  1/1 + 0 = 1 => 1

d10 :  (10-9)/2 + 9 = 9 1/2 => 1

d100 :  (100-9)/2 + 9 = 54 1/2 => 5

d1.000 :  (1.000-189)/3 + 99 = 369 1/3 => 3

d10.000 :  (10.000 – 2.889) / 4 + 999 = 2776 3/4 => 7

d100.000 :  (100.000 – 38.889) /5 + 9.999 = 22.221 1/5 => 2

d1.000.000 :  (1.000.000 – 488.889)/6 + 99.999  = 185.184 1/6 => 1

So the result is 1153721 = 210

Pretty easy huh? I must admit that it took me a bit more than a minute to solve when you include the time I spent thinking about the problem. But not too much more.

As a side note this number is known as the Champernowne constant.

I know it can be brute forced as well, but I haven’t had the chance to throw a computer at the problem. If you want to see programming solutions for the problem I have found 2 different approaches.  The Burning Monk has a solution for the problem using linq. Free Lancers Unite has a C# solution closer to what I think I would have implemented.

A short post for what I consider a simple problem. I hope my trail of thoughts was clear otherwise feel free to ask questions or come with comments.

Posted by Kristian

12 comments

Nice solution.
but your ans confuse at a glance.
d100 : (100-9)/2 + 9 = 45 1/2 => 5
should be
d100 : (100-9)/2 + 9 = 54 1/2 => 5

Hi Randall

Thanks for your comment and thanks for spotting that. Either I was too quick or I made a typo. It is now corrected so it should be easier to read.

/Kristian

Maybe you like to have a look at traditional bf methiod

import string
a="0"
i=0 
while 1:
	i+=1
	s=str(i)
	if len(a) <= 10**6:
		a+=s
	else: break
	
def d(n):
	return int(a[n])
	
print d(1)*d(10)*d(100)*d(1000)*d(10000)*d(100000)*d(1000000)

Took 0.159s in python

Hi Kristian,

I am using a similar method as you did. But instead of creating a table like the one you did, I made the process automatic such that the program can do for arbitrary large numbers. Or perhaps you also did it this way but just did not elaborate it in the post. Anyway, here is a piece of Python code for this problem. Hope it would be a good supplement.

def func():
    """Calculate the product.
    """
    prod = 1
    i = 1
    while i <= 1000000:
        prod *= get_digit(i)
        i *= 10
    return prod

# single-digit, total space: 9*1
# double-digit, total space: 90*2
# triple-digit, total space: 900*3
# ...
def get_digit(index):
    """Get the index-th digit of the fractional part.
    """ 
    i = 1
    n = 9
    while index - n * i > 0:
        index -= n * i
        i += 1
        n *= 10
    the_number = 10 ** (i-1) + (index-1) // i
    return int(str(the_number)[(index%i)-1])
    
if __name__ == '__main__':
    print(func())

[…] There are intuitive manual methods for solving this problem, one good explanation can be found on Math Blog. […]

Nice solution approach! I implemented it in Java. Instead of building a String containing 1mio characters I decided to just keep track of the length of the String and the numbers which need to be appended. Maybe you also like this (pretty fast) solution:

int dn = 1;
int i = 1;
int len = 0;
int prod = 1;
		
while(dn &lt;= 1E6){
	String number = String.valueOf(i++);
	int l = number.length();
	if(len + l &gt;= dn){
		prod *= Integer.valueOf(String.valueOf(number.charAt(dn - len - 1)));
		dn *= 10;
	}
	len += l;
}
		
System.out.println(&quot;product: &quot;+prod);

Here is the code I implemented in C, where I use some very simple self made functions. It runs about 47 ms and can be executed easily for different positions.

    int i=0,j=0,total=0,product=1,index;
    int milestones[7] = {1,10,100,1000,10000,100000,1000000};

    while(j&lt;=6){
        if(total+number_of_digits(i+1) &gt;= milestones[j]){
            index = milestones[j] - total - 1;
            product *= get_digit_from_begin(i+1,index);
            j++;
        }
        i++;
        total += number_of_digits(i);
    }
    printf(&quot;answer: %d&quot;,product);
    return 0;

What do you mean by 1/3rd left over?

When I do the division I end up with 369 and 1/3, which means I need the to look at the digit 1/3 into the number 370. Since the number is 3 digits long, this corresponds to the first digit.

Jean-Marie Hachey

Table 1
Some continuous digits sequences in the
Champernowne’s constant.

http://img11.hostingpics.net/pics/872939pe40tab1champconst.jpg

Table 1 shows that the 9th digit in the Champernowne’s constant
is 9, the 10th digit is 1, the 11th digit is 0, etc…

Results in Table 1 were obtained by adapting Free Lancers Unite’s algorithm (1).

___

Sources:
1) PE40, Free Lancers Unite’s algorithm
http://freelancersunite.net/project_euler/project-euler-problem-40/
2) Microsoft Visual C# 2010 Express
3) Microsoft Office Excel (2007)

VS2017 solution:

using System;
using System.Text;

namespace Euler40
{
internal class Program
{
private static void Main(string[] args)
{
StringBuilder st = new StringBuilder();
int value = 0;
int idx = 1;
int product = 1;
int n = 1;

while (st.Length < 1e6) //make million long string
{
st.Append(n.ToString());
n++;
}

string s = st.ToString(); //make regular string
string s1 = "";

for (int i = 0; i < 6; i++)
{
//get (idx-1)'th digit (idx = 1, want [0], 10 want[9]
s1 = s.Substring(idx – 1, 1);

value = int.Parse(s1);
idx *= 10;
product *= value;
}
Console.WriteLine(product);
}
}
}

Leave a Reply