Project Euler – Problem 64

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