// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (13 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 57 Solution

Project Euler 57 Solution

Project Euler 57: Investigate the expansion of the continued fraction for √ 2


Project Euler 57 Problem Description

Project Euler 57: 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?

Analysis

Project Euler 57
The early Pythagoreans were convinced that every conceivable number could in principle be written in fractional form, as the ratio of two natural numbers. Since there is an infinite supply of these numbers, they reasoned, there must be enough to do the job. The discovery that this was an mistaken belief, possibly by the Pythagorean philosopher Hippasus in the 5th century BCE, was shocking news. According to legend, Hippasus was hurled off a boat and drowned to prevent the truth becoming widely known, such was its threat to the Pythagorean concept of order in the Universe.

Expand the series as 2d + n for the numerator and d+n for the denominator and count the number of times the length of the numerator exceeds the denominator as strings.

Using base 10 logs for the number of digits comparison between the numerator and denominator yields a 100 times speed improvement over comparing the lengths of them converted to strings.

Also, at this time the Trinket version below is not calculating logs correctly. Until they fix it you can switch to a string comparison as:

if len(str(n)) > len(str(d)): c += 1

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank

Project Euler 57 Solution

Runs < 0.003 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 57 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|153|

Afterthoughts

Project Euler 57 Solution last updated

Discussion

2 Responses to “Project Euler 57 Solution”

  1. oh dear, I actually wrote a recursion function with the use of lib to deal with this question. I was so dumb that my program took more than half a min to run.

    Posted by PrM | January 3, 2012, 9:04 PM

Post a comment