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

Written by on 7 May 2011

Topics: Project Euler

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 1*1*5*3*7*2*1 = 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.

9 Comments For This Post I'd Love to Hear Yours!

  1. randall says:

    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

  2. Kristian says:

    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

  3. Ronnie says:

    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

  4. Darren says:

    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())
    
    
  5. Max says:

    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);
    
  6. mrb says:

    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;
    
  7. Akul says:

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

  8. Kristian says:

    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.

  9. Jean-Marie Hachey says:

    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)

Trackbacks For This Post

  1. Project Euler 40 Solution -
  2. Найти любую заданную по позиции цифру последовательности 1234567891011….(Константа Чамперноуна 0,123456789101112…….) - Мой цифровой блог

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.

This site uses cookies.