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