Euler Solution 64

From ProgSoc Wiki

Jump to: navigation, search

All square roots are periodic when written as continued fractions

The first ten continued fraction representations of (irrational) square roots are:

  • √2=[1;(2)], period=1
  • √3=[1;(1,2)], period=2
  • √5=[2;(4)], period=1
  • √6=[2;(2,4)], period=2
  • √7=[2;(1,1,1,4)], period=4
  • √8=[2;(1,4)], period=2
  • √10=[3;(6)], period=1
  • √11=[3;(3,6)], period=2
  • √12= [3;(2,6)], period=2
  • √13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

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

Solutions

Python by Althalus

Runtime: 1.511s

from math import floor

def cf(D):
    m = [0,]
    d = [1,]
    a = [floor(D**0.5),]

    for n in xrange(0,10000):
        # a is one of the digits in the period. (Now how can we identify a pattern in a?)
        # http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html
        # It looks like we can find the END of the sequence when a[n] = 2*a[0]. 
        if a[n] == 2*a[0]:
            return len(a[0:n])
        m.append(int( (d[n]*a[n]) - m[n] ))
        d.append(int( (D - (m[n+1])**2)/d[n] ))
        a.append(int( floor((a[0]+m[n+1])/d[n+1]) ))

count = 0
for x in range (2,10001):
    if not (x**0.5 == int(x**0.5)):
        period = cf(x)
        if period & 1:
            count += 1
print count
Personal tools