Problem 64:
The first ten continued fraction representations of (irrational) square roots are:
sqrt(2)=[1;(2)], period=1
sqrt(3)=[1;(1,2)], period=2
sqrt(5)=[2;(4)], period=1
sqrt(6)=[2;(2,4)], period=2
sqrt(7)=[2;(1,1,1,4)], period=4
sqrt(8)=[2;(1,4)], period=2
sqrt(10)=[3;(6)], period=1
sqrt(11)=[3;(3,6)], period=2
sqrt(12)= [3;(2,6)], period=2
sqrt(13)=[3;(1,1,1,1,6)], period=5
Exactly four continued fractions, for N <= 13, have an odd period.
How many continued fractions for N <= 10000 have an odd period?
class runner { private static int find(int[][] found, int m, int d, int a){ int c=0; for(int[] x : found){ if(x[0] == m && x[1] == d && x[2] == a) return c; else if(x[0] == 0 && x[1] == 0 && x[2] == 0) return -1; c++; } return -1; } private static int count(int S){ if(Math.floor(Math.sqrt(S)) == Math.sqrt(S)) return 0;//period is 0. int m = 0, d=1, a0 = (int) Math.floor(Math.sqrt(S)), a=a0; int k = 0; int[][] found = new int[2*S+1][3]; while(true){ int f = find(found, m,d,a); if(f > -1) return k-f; found[k][0] = m ; found[k][1] = d; found[k++][2] = a; m = d*a-m; d = (S-m*m)/d; a = (int)(Math.floor((a0+m)/d)); } } public static void main (String[] args) throws java.lang.Exception { long time = System.currentTimeMillis(); int odd=0; for(int i=2; i<10000; i++){ if(count(i)%2 == 1) odd++; //System.out.println(i+" "+count(i)); } System.out.println("odd:"+odd); System.out.println("time: "+(System.currentTimeMillis() - time)); } } |
Notes: http://en.wikipedia.org/wiki/Periodic_continued_fraction