Project Euler Problem 64 Solution

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

HackerRank Project Euler Problem 64 overview:

We are asked to count, for each integer \( n \) from \( 2 \) up to a given \( N \), whether the period of the continued fraction representation of \( \sqrt{n} \) is odd.

1. Understanding Continued Fractions of \( \sqrt{n} \)

For a non-square positive integer \( n \), the square root \( \sqrt{n} \) can be written as a periodic continued fraction of the form:

\( \sqrt{n} = [a_0; a_1, a_2, \dots, a_k, \dots] \)

where:

• \( a_0 = \lfloor \sqrt{n} \rfloor \) is the integer part.
• The sequence \( a_1, a_2, \dots \) repeats after a certain point. The length of this repeating block is called the period.

For perfect squares (i.e., when \( \sqrt{n} \) is an integer), there is no repeating portion, so the period is defined as \( 0 \).

2. The Function period_length(n)

This function computes the period length of the continued fraction for \( \sqrt{n} \).

a. Handling Perfect Squares

m = math.isqrt(n)
if m*m == n: return 0
  

Here, math.isqrt(n) computes the integer square root of \( n \). If \( n \) is a perfect square (i.e., \( m \times m = n \)), the function returns \( 0 \) since there is no periodic part.

b. Initialization for Non-Squares

a, d, period = m, n - m*m, 1
  

Initialization details:

• \( a \) is set to the integer part \( a_0 \).
• \( \text{period} \) is initially set to \( 1 \) because we count the first step that computes the first term of the repeating sequence.

c. Iterative Process

while d > 1:
    m = ((a + m) // d) * d - m
    d = (n - m*m) // d
    period += 1
  

This loop implements the recurrence relations for generating the continued fraction:

Recurrence relations in theory:
For \( k \ge 1 \), if you denote \( m_k \) and \( d_k \) as intermediate values, then:

\( m_k = d_{k-1} \cdot a_{k-1} - m_{k-1} \)
\( d_k = \frac{n - m_k^2}{d_{k-1}} \)
\( a_k = \left\lfloor \frac{a_0 + m_k}{d_k} \right\rfloor \)

In the code:

• The expression ((a+m) // d) computes the next coefficient \( a_k \) (using floor division).
• \( m = ((a+m) // d) \times d - m \) calculates the next \( m_k \) using the recurrence \( m_k = d_{k-1} \cdot a_k - m_{k-1} \).
• \( d = \frac{n - m^2}{d} \) (implemented as (n - m*m) // d) updates \( d_k \) based on the formula \( d_k = \frac{n - m_k^2}{d_{k-1}} \).
• The period counter is incremented by \( 1 \) each iteration.

The loop stops when \( d \) becomes \( 1 \). At that point, the continued fraction would generate a term that makes the repeating sequence complete (in many formulations, the appearance of \( d = 1 \) signals that the next term would be \( 2a \), thus starting the repetition).

d. Return Value

Once the loop terminates, the function returns the computed \( \text{period} \), which represents the length of the repeating part of the continued fraction for \( \sqrt{n} \).

N = int(input())
print(sum(period_length(n) & 1 for n in range(2, N+1)))
  

Input Reading: The program reads an integer \( N \) from the user.

Summing Odd Periods: For each \( n \) in the range \( 2 \) to \( N \):
period_length(n) & 1 uses the bitwise AND operator to check the parity of the period length. This works because:

• If the period is odd, then period_length(n) & 1.
• If the period is even (or \( 0 \)), then it equals \( 0 \).

Output: Finally, the program prints the total count of \( n \) for which the continued fraction representation of \( \sqrt{n} \) has an odd period.

4. Example Continued Fraction Period Calculation for \( n=23 \)

This explanation demonstrates the process of calculating the period length of the continued fraction for \( \sqrt{23} \) using a calculator.

Just peel off the integer, add it to the list. The first number is outside of the repeating series. Now, take the reciprocal of the fractional part and repeat the peeling process. When the peeled integer equals twice the first number we have come to the end of the repeating series. Since 8 is twice the first number, 4, we are done.

The native floating point in Python without the help of imported modules is not accurate enough to propagate this method which is why the standard algorithm presented was used.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 64

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