Project Euler > Problem 64 > Odd period square roots (Java Solution)

Problem:

All square roots are periodic when written as continued fractions and can be written in the form:

[√]N = a0 +
1
a1 +
1
a2 +
1
a3 + ...

For example, let us consider [√]23:

[√]23 = 4 + [√]23 — 4 = 4 +
1
= 4 +
1

1
[√]23—4
1 +
[√]23 – 3
7

If we continue we would get the following expansion:

[√]23 = 4 +
1
1 +
1
3 +
1
1 +
1
8 + ...

The process can be summarised as follows:

a0 = 4,
1
[√]23—4
=
[√]23+4
7
= 1 +
[√]23—3
7
a1 = 1,
7
[√]23—3
=
7([√]23+3)
14
= 3 +
[√]23—3
2
a2 = 3,
2
[√]23—3
=
2([√]23+3)
14
= 1 +
[√]23—4
7
a3 = 1,
7
[√]23—4
=
7([√]23+4)
7
= 8 + [√]23—4
a4 = 8,
1
[√]23—4
=
[√]23+4
7
= 1 +
[√]23—3
7
a5 = 1,
7
[√]23—3
=
7([√]23+3)
14
= 3 +
[√]23—3
2
a6 = 3,
2
[√]23—3
=
2([√]23+3)
14
= 1 +
[√]23—4
7
a7 = 1,
7
[√]23—4
=
7([√]23+4)
7
= 8 + [√]23—4

It can be seen that the sequence is repeating. For conciseness, we use the notation [√]23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

[√]2=[1;(2)], period=1
[√]3=[1;(1,2)], period=2
[√]5=[2;(4)], period=1
[√]6=[2;(2,4)], period=2
[√]7=[2;(1,1,1,4)], period=4
[√]8=[2;(1,4)], period=2
[√]10=[3;(6)], period=1
[√]11=[3;(3,6)], period=2
[√]12= [3;(2,6)], period=2
[√]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?

Solution:

837799

Code:
The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/* 
 * Solution to Project Euler problem 14
 * By Nayuki Minase
 * 
 * http://nayuki.eigenstate.org/page/project-euler-solutions
 * https://github.com/nayuki/Project-Euler-solutions
 */

import java.math.BigInteger;


public final class p014 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p014().run());
	}
	
	
	private static final int LIMIT = Library.pow(10, 6);
	private static final BigInteger CACHE_SIZE = BigInteger.valueOf(LIMIT);  // Any non-negative number, though there are diminishing returns
	
	
	public String run() {
		int maxArg = -1;
		int maxChain = 0;
		for (int i = 1; i < LIMIT; i++) {
			int chainLen = collatzChainLength(BigInteger.valueOf(i));
			if (chainLen > maxChain) {
				maxArg = i;
				maxChain = chainLen;
			}
		}
		return Integer.toString(maxArg);
	}
	
	
	// Memoization
	private int[] collatzChainLength = new int[CACHE_SIZE.intValue()];
	
	private int collatzChainLength(BigInteger n) {
		if (n.signum() < 0)
			throw new IllegalArgumentException();
		
		if (n.compareTo(CACHE_SIZE) >= 0)  // Caching not available
			return collatzChainLengthDirect(n);
		
		int index = n.intValue();  // Index in the cache
		if (collatzChainLength[index] == 0)
			collatzChainLength[index] = collatzChainLengthDirect(n);
		return collatzChainLength[index];
	}
	
	
	private int collatzChainLengthDirect(BigInteger n) {
		if (n.equals(BigInteger.ONE))  // Base case
			return 1;
		else if (!n.testBit(0))  // If n is even
			return collatzChainLength(n.shiftRight(1)) + 1;
		else  // Else n is odd
			return collatzChainLength(n.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE)) + 1;
	}
	
}