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
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
Post a Comment