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