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 12^{th}digit of the fractional part is 1.

Ifd_{n}represents then^{th}digit of the fractional part, find the value of the following expression.

d_{1}xd_{10}xd_{100}xd_{1000}xd_{10000}xd_{100000}xd_{1000000}

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:

d_{1 }: 1/1 + 0 = 1 => 1

d_{10 }: (10-9)/2 + 9 = 9 1/2 => 1

d_{100 }: (100-9)/2 + 9 = 54 1/2 => 5

d_{1.000 }: (1.000-189)/3 + 99 = 369 1/3 => 3

d_{10.000 }: (10.000 – 2.889) / 4 + 999 = 2776 3/4 => 7

d_{100.000 }: (100.000 – 38.889) /5 + 9.999 = 22.221 1/5 => 2

d_{1.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.

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

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.

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:

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.

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.

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)