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?
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
Project Euler 57 SolutionRuns < 0.003 seconds in Python 2.7.
Use this link to get the Project Euler 57 Solution Python 2.7 source.
AnswerSlowly 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.
- We start the first terms of the series by initializing n to 3 and d to 2 as shown in the description.
- The loop’s index variable
xare the points where the numerator exceeds the denominator.
- See also, Project Euler 65 Solution: Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.