Project Euler Problem 64 Statement

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

For example, let us consider $\sqrt{23}:$

If we continue we would get the following expansion:

The process can be summarised as follows:

$\quad \quad a_0=4, \frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7$
$\quad \quad a_1=1, \frac 7 {\sqrt{23}-3}=\frac {7(\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2$
$\quad \quad a_2=3, \frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7$
$\quad \quad a_3=1, \frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} 7=8+\sqrt{23}-4$
$\quad \quad a_4=8, \frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7$
$\quad \quad a_5=1, \frac 7 {\sqrt{23}-3}=\frac {7 (\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2$
$\quad \quad a_6=3, \frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7$
$\quad \quad a_7=1, \frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} {7}=8+\sqrt{23}-4$

It can be seen that the sequence is repeating. 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:

$\quad \quad \sqrt{2}=[1;(2)]$, period=$1$
$\quad \quad \sqrt{3}=[1;(1,2)]$, period=$2$
$\quad \quad \sqrt{5}=[2;(4)]$, period=$1$
$\quad \quad \sqrt{6}=[2;(2,4)]$, period=$2$
$\quad \quad \sqrt{7}=[2;(1,1,1,4)]$, period=$4$
$\quad \quad \sqrt{8}=[2;(1,4)]$, period=$2$
$\quad \quad \sqrt{10}=[3;(6)]$, period=$1$
$\quad \quad \sqrt{11}=[3;(3,6)]$, period=$2$
$\quad \quad \sqrt{12}=[3;(2,6)]$, period=$2$
$\quad \quad \sqrt{13}=[3;(1,1,1,1,6)]$, period=$5$

Exactly four continued fractions, for $N \le 13$, have an odd period.

How many continued fractions for $N \le 10\,000$ have an odd period?

Solution

1. Importing the Math Module

The script begins by importing the math module to utilize mathematical functions:

import math

2. Defining the period_length Function

The period_length function calculates the period of the continued fraction for a given \( N \):

def period_length(N):
    r = math.isqrt(N)
    if r * r == N:
        return 0  # N is a perfect square; no periodic continued fraction
    q, k, period = r, N - r * r, 1
    while k > 1:
        r = ((q + r) // k) * k - r
        k = (N - r * r) // k
        period += 1
    return period

Explanation:

• Check for Perfect Squares:

  If \( N \) is a perfect square (i.e., \( r^2 = N \)), the continued fraction terminates, and there's no period. The function returns 0 in this case.

• Initialization:

  - \( r \) is initialized to the integer square root of \( N \).

  - \( q \) is also set to \( r \).

  - \( k \) is initialized to \( N - r^2 \), representing the initial remainder.

  - \( \text{period} \) is set to 1 since we start counting the period.

• Calculating the Period:

  The while loop continues as long as \( k > 1 \), ensuring that the fraction remains periodic.

  • Update \( r \):

    \( r = \left( \left\lfloor \frac{q + r}{k} \right\rfloor \times k \right) - r \)

    This step derives the next term in the continued fraction.

  • Update \( k \):

    \( k = \frac{N - r^2}{k} \)

    This updates the remainder for the next iteration.

  • Increment the Period:

    Each iteration signifies another term in the periodic part, so \( \text{period} \) is incremented.

• Return the Period:

  Once \( k \) is no longer greater than \( 1 \), the loop terminates, and the function returns the computed \( \text{period} \).

3. Processing the Range of Numbers

The script takes an upper limit as input, specifying the range of \( N \) values to evaluate:

limit = int(input("Enter the upper limit: "))
print(sum(period_length(n) & 1 for n in range(2, limit + 1)))

4. Counting Odd Periods and Printing Results

For each \( n \), period_length(n) & 1 checks if the period is odd:

• The expression period_length(n) & 1 is a bitwise operation that returns 1 if the period is odd and 0 if it's even.
• sum(...) adds up all the 1s, effectively counting how many periods are odd within the range.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 64

HackerRank Project Euler 64: How many continued fractions for $x\le N$, $(10\le N\le 30000)$ have an odd period?