Project Euler Problem 57

Problem 57

Solved a simple problem from Euler again.You can have a look at the problem statement below.

Problem statement:

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5

1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Approach:

If you look at the fractional progressions below(same given on the question as well),you will find that there is a clear arithmetical pattern to it.

3/2 , 7/5 , 17/12 , 41/29

you can clearly see that the denominator on every fraction is the summing of both nominator and denominator of the previous fraction.

for (e.g) take the fraction 3/2

3 (nom) / 2 (denom) => 3+2 = 5 (which is the denom for the next fraction 7/5)

similarly  for the next fraction 7/5

7+5= 12 (which is the denominator for the next fraction 17/12)

You will also see that the numerator on every successive fraction is the sum of previous fraction's numerator and the corresponding denominator multiplied with 2.

Lets take the first fraction on our list again which is 3/2

Numerator=3

Denominator=2

Next Numerator = (denominator x 2) + numerator

           7             =         (2 x 2)          +      3

as we have seen already the new denominator for the next fraction,would be Numerator + denominator of previous fraction(3/2)

3+2=5.

and we get the next fraction as 7/5

So to reiterate again the formula that is used to calculate the next fractions.

Next Denominator= Current Numerator + Current Denominator

Next numerator = Current Numerator+(Current Denominator X 2)

C# Code

C# with its primitive data type cannot really handle the kind of number crunching that is required for this program.As you will see the numbers can get really big before the program can complete.The basic reason is c# never was designed to do such calculations in the first place.But still framework in its release 4.5 has introduced a new datatype called BigInteger that saves the day for this challenge.BigInteger "Represents an arbitrarily large signed integer."-MSDN

This Euler challenge was basically to generate all fractions up to 1000 times and then see out of all those fractions,how many of them have their numerator's digit count greater than the denomintor's digit count.

Here is the code.Download

Not sharing my output as it would be a spoiler. Still what i would like to share is the numerator part of the fraction that got generated on the 1000th iteration.

72016336943533875056131468444247239328723197628440751797201898063588088312700201943482948477109536203740206649612702729920170001354454107173480483962605519493117789821758457767858986227019805650639002566946496865364666543562826303377877700877266135276209125278037204443042487153089226849544681245300260167141025277156482737568934079466850318276966893735585103845471745828701580706481

Yes that's a number and thanks to BigInteger :)

happy coding !!!
Polybius

Click here for other Topics