package challenge120;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Challenge120 {

	private final static int LIM = 1 << 20; // 1<<20 = 2^20

	private final static Map<Long, Integer> CACHE = new HashMap<Long, Integer>();

	public static void main(final String[] args) {

		final long start = System.currentTimeMillis();

		int fnMax = 0;
		final List<Integer> fnMaxN = new ArrayList<Integer>();

		for (int n = 1; n <= LIM; n++) {
			final int fn = f(n);
			if (fn > fnMax) {
				fnMax = fn;
				fnMaxN.clear();
				fnMaxN.add(n);
			} else if (fn == fnMax) {
				fnMaxN.add(n);
			}
		}
		out(fnMax, fnMaxN);
		System.out.println("Time: " + (System.currentTimeMillis() - start)
				+ "[ms]");
	}

	private static int f(final int n) {
		int fn = 0;
		for (long nTemp = n; nTemp != 1;) {
			final Integer cached = CACHE.get(nTemp);
			if (cached == null) {
				nTemp = (nTemp % 2 == 0) ? nTemp / 2 : nTemp * 3 + 1;
				fn++;
			} else {
				fn += cached;
				break;
			}
		}
		CACHE.put(Long.valueOf(n), fn);
		return fn;
	}

	private static void out(final int maxN, final List<Integer> fnMaxN) {

		System.out.println("Max(f(n)) = " + maxN);
		System.out.println("n =");
		for (final int n : fnMaxN) {
			System.out.println("  " + n);
		}
	}
}