Statement

All square roots are periodic when written as continued fractions and can be written in the form:

For conciseness, we use the notation sqrt(23) = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

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

sqrt(2)=[1;(2)], period=1
sqrt(3)=[1;(1,2)], period=2
sqrt(5)=[2;(4)], period=1
sqrt(6)=[2;(2,4)], period=2
sqrt(7)=[2;(1,1,1,4)], period=4
sqrt(8)=[2;(1,4)], period=2
sqrt(10)=[3;(6)], period=1
sqrt(11)=[3;(3,6)], period=2
sqrt(12)= [3;(2,6)], period=2
sqrt(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?

Solution

Here the solution mainly consists in finding an algorithm capable of generating the continued fraction and stopping when the loop is found.

Searching in google and wikipedia I've found the algorithm explained in: this wikipedia article.

All I did was implement that algorithm in Python and execute it for the first 10000 excluding the perfect squares.

if __name__ == '__main__':
    result = 0
    for n in filter(lambda x: int(x ** 0.5) ** 2 != x, range(1, 10001)):
        m = 0
        d = 1
        a = a_0 = int(n ** 0.5)
        triple_set = list()
        while (m, d, a) not in triple_set:
            triple_set.append((m, d, a))
            tmp_m = d * a - m
            tmp_d = (n - tmp_m ** 2) // d
            tmp_a = int((a_0 + tmp_m) / tmp_d)
            a = tmp_a
            d = tmp_d
            m = tmp_m
        while triple_set[0] != (m, d, a):
            triple_set.pop(0)
        if len(triple_set) & 1:
            result += 1
    print("The result is:", result)

The Python file is available for download here.