## 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?

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;	}	}