Algorithm notes on the back of used envelopes bound in a ring binder

Problem 64 "Odd period square roots"

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

\[ \quad \quad \sqrt{N}=a_0+\frac 1 {a_1+\frac 1 {a_2+ \frac 1 {a3+ \dots}}} \]

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

\[\quad \quad \sqrt{23}=4+\sqrt{23}-4=4+\frac 1 {\frac 1 {\sqrt{23}-4}}=4+\frac 1 {1+\frac{\sqrt{23}-3}7}\]

If we continue we would get the following expansion:

\[ \quad \quad \sqrt{23}=4+\frac 1 {1+\frac 1 {3+ \frac 1 {1+\frac 1 {8+ \dots}}}} \]

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?

問 64 「奇数周期の平方根」

平方根は連分数の形で表したときに周期的であり, 以下の形で書ける:

例えば, √23を考えよう.

となる.

この操作を続けていくと,

を得る.

操作を纏めると以下になる:

よって, この操作は繰り返しになることが分かる. 表記を簡潔にするために, √23 = [4;(1,3,1,8)]と表す. (1,3,1,8)のブロックは無限に繰り返される項を表している.

最初の10個の無理数である平方根を連分数で表すと以下になる.

• √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

N ≤ 13で奇数の周期をもつ平方根は丁度4つある.

N ≤ 10000 について奇数の周期をもつ平方根が何個あるか答えよ.

mod fraction {
    trait MixedFraction {
        fn integer_part(&self) -> u32;
    }

    pub struct QuadraticIrrational {
        rational_part: u32,
        irrational_part: u32,
        downscaling_ratio: u32,
        pub integer_part: u32,
        pub iteration: u32,
    }

    impl MixedFraction for QuadraticIrrational {
        fn integer_part(&self) -> u32 {
            let mixed_fraction
                = self.rational_part as f64 
                + (self.irrational_part as f64).sqrt();
            (mixed_fraction / self.downscaling_ratio as f64) as u32
        }
    }

    impl QuadraticIrrational {
        pub fn new(square_free_integer: u32) -> Self {
            assert!(
                ((square_free_integer as f64).sqrt() as u32).pow(2)
                != square_free_integer
            );
            let mut q = Self {
                rational_part: 0,
                irrational_part: square_free_integer,
                downscaling_ratio: 1,
                integer_part: u32::MAX,
                iteration: 0,
            };
            q.integer_part = q.integer_part();
            q
        }
        pub fn next_iteration(&mut self) {
            self.iteration += 1;
            self.rational_part 
                = self.downscaling_ratio 
                * self.integer_part 
                - self.rational_part;
            self.downscaling_ratio
                = (self.irrational_part - self.rational_part.pow(2)) 
                / self.downscaling_ratio;
            self.integer_part = self.integer_part();
        }
    }
}

fn main() {
    let mut count = 0u32;
    for n in 2..=10000 {
        if ((n as f64).sqrt() as u32).pow(2) == n {
            continue;
        }
        let mut surd = fraction::QuadraticIrrational::new(n);
        let integer_part_orig = surd.integer_part;
        while {
            surd.next_iteration();
            surd.integer_part != integer_part_orig * 2
        } {}
        if surd.iteration % 2 != 0 {
            count += 1;
        }
    }
    println!("{}", count);
    assert_eq!(count, 1322);
}