## Project Euler Problem #64

### March 4, 2012

Read the details of the problem here

**Summary**

How many continued fractions for N ≤ 10000 have an odd period?

**Solution**

It took a little while for me to understand how this was working so, to make it clearer this is essentially what’s required.

- Take the square root of the original number then…
- The integer portion becomes the next number in the sequence,
- Take the reciprocal of the remaining decimal portion,
- Take this number as input into Step 2.

Obviously, at step 3, if the decimal portion has been seen before, that sequence would just repeat from then on, so a cycle would have been found. In that respect it’s very similar to the solution for Problem #26.

As an example, here’s the trace for 23, with it’s square root – 4.79583.

n | Digit | Remainder |
---|---|---|

4.79583 | 4 | 0.79583 |

1.25655 | 1 | 0.25655 |

3.89792 | 3 | 0.89792 |

1.11369 | 1 | 0.11369 |

8.79583 | 8 | 0.79583 |

1.25655 | 1 | 0.25655 |

Whilst this works as an implemented algorithm for numbers with short sequences it breaks down on the longer ones, some of which are over 200 elements long, due to problems with precision. So I expanded out the algorithm to better reflect the way that Euler describes in the question and coded that up. I made the assumption that the sequence would start from the first position rather than an arbitrary one.

def cf(n) { def ( i, j, c, k ) = [ 0, 1, 0, null ] def sqrt_n = Math.sqrt(n) while (true) { j = (n - (i * i)).intdiv(j) i = -(i - ((int)(sqrt_n + i)).intdiv(j) * j) if ([i, j] == k) return c - 1 if (c == 1) k = [i, j] c++ } } def answer = (2..10000).count { (((int)Math.sqrt(it)) ** 2 != it) && (cf(it) % 2) }

This executes in Groovy 1.8.6 under Java 7u3 on my Samsung 700G7A i7-2670QM 2.2 GHz machine in around 0.45 seconds, so well within my 5 second cut-off (reduced from the old 15 seconds on my old machine). This runs quite fast as it only ever uses integers – apart from the initial sqrt calculation.

**Conclusion**

Didn’t use many Groovy features for this solution in the main apart from keeping the function initialization quite terse and the count listop on the number range. Performance was fairly good – though an equivalent Java solution does run in 55 ms – around 8 times faster.

July 18, 2012 at 15:32

translated to python 3.2 without optimization or refactoring…0.624 s