## Problem:

A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?

NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length you could use red (3), black (1), and red (4).

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