     (14 votes, average: 5.00 out of 5) Loading...

## 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 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
```

#### 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.
Project Euler 57 Solution last updated

## Discussion

### 4 Responses to “Project Euler 57 Solution”

1. the python snippet didn’t return the correct answer 🙂

Posted by kids | June 20, 2019, 11:53 PM
• Yep, you’re right. I changed it to Repl.it and it worked. I will let the Trinket people know their log10 function is buggy. Thanks!

Posted by Mike Molony | June 21, 2019, 12:41 AM
2. 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
• 