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

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

This program and method
solves all test cases
on HackerRank

Afterthoughts

• 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 x are the points where the numerator exceeds the denominator.
  
• See also, Project Euler 65 Solution: