Project Euler #64: Odd period square roots

Question
All square roots are periodic when written as continued fractions and can be written in the form:
For example, let us consider
If we continue we would get the following expansion:
The process can be summarised as follows:










It can be seen that the sequence is repeating. For conciseness, we use the notation
, to indicate that the block (1,3,1,8) repeats indefinitely.
The first ten continued fraction representations of (irrational) square roots are:

, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period=
, period= Exactly four continued fractions, for
, have an odd period.
How many continued fractions for
have an odd period?
Answer : 1322

Hacker Rank Problem

Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int upper = in.nextInt();
        int result = 0;

        for(int n=1;n<=upper;n++)
        {
            int limit = (int) Math.sqrt(n);
            if (limit * limit == n) continue;

            int period = 0;
            int d = 1;
            int m = 0;
            int a = limit;

            do{
                m = d*a - m;
                d = (n - m * m) / d;
                a = (limit + m) / d;
                period++;
            }while(a != 2*limit);

            if (period % 2 == 1) result++;
        }
        System.out.println(result);
    }
}

Comments

Popular Posts