Project Euler : Problem 14 - Longest Collatz sequence

Problem Statement : Longest Collatz sequence

Problem 14 :The following iterative sequence is defined for the set of positive integers:

$$n → n/2 \ (n \ is \ even) \\ n → 3n + 1 \ (n \ is \ odd)$$

Using the rule above and starting with $13$, we generate the following sequence:

$$13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1$$

It can be seen that this sequence (starting at $13$ and finishing at $1$) contains $10$ terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at $1$.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Concept and Theory

As stated its a conjecture, meaning this haven’t be proven mathematically. So what we can all do is do what it says and find out the largest number.

Apparently if you will see at some point the cycle repeats. For eg. $13$ the cycle will look like

$$13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1$$

As we can see the number $40$’s cycle is one short than that of $13$. Simply Cache them!!! That way we don’t have to run the code everytime. What else we can see, $n → n/2 \ (n \ is \ even)$ may result in an odd number or even number and $n → 3n + 1 \ (n \ is \ odd)$ will always result in even number. Hence we can directly jump $2$ steps when $n$ is odd and save a calculation by $n → (3n + 1)/2 \ (n \ is \ odd)$.

Naive Code

/**
 * A function which tells you the largest possible number below a limit having
 * longest Collatz Cycle
 *
 * @param limit : maximum number upto which we need to scan
 *
 * @return number having largest collatz cycle
 */
public static long naiveLongestCollatzSequenceFinder(long limit) {

  long maxLength = 0;
  long maxNum = 0;

  for (long i = 1; i <= limit; i++) {

    long num = i;

    long lengthSoFar = 0;

    while (num != 1) {
      if (num % 2 == 0) {
        num /= 2;
      } else {
        num = 3 * num + 1;
      }
      lengthSoFar++;
    }
    if (lengthSoFar >= maxLength) {
      maxLength = lengthSoFar;
      maxNum = i;
    }
  }
  return maxNum;
}

Optimized Code

	private static final int CACHE_SIZE = 5_000_000;

	// stores collatz sequence for number at index
	private static int[] cache = new int[CACHE_SIZE + 1];

	// stores number with max collatz sequence at index
	private static int[] collatzCache = new int[CACHE_SIZE + 1];

	public static void main() {
		precomputeCache();

		Scanner scanner = new Scanner(System.in);
		int tests = Integer.parseInt(scanner.nextLine());
		for (int i = 0; i < tests; i++) {
			int n = Integer.parseInt(scanner.nextLine());
			System.out.println(collatzCache[n]);
		}

		scanner.close();
	}

	/**
	 * A function to precompute the collatz sequence and store them in a cache
	 */
	public static void precomputeCache() {
		cache[0] = 1;
		cache[1] = 1;
		collatzCache[0] = 1;
		collatzCache[1] = 1;
		int maxSeq = 0;
		int maxNum = 0;
		for (int j = 2; j <= CACHE_SIZE; j++) {
			int collatzSeq = 0;
			long number = j;
			while (number > 1) {
				if (cache[j] > 0) {
					collatzSeq += cache[j];
					break;
				}
				collatzSeq++;
				if (number % 2 == 0) {
					number >>= 1;
				} else {
					number = 3 * number + 1;
				}
			}
			cache[j] = collatzSeq;
			if (collatzSeq >= maxSeq) {
				maxSeq = collatzSeq;
				maxNum = j;
			}
			collatzCache[j] = maxNum;
		}
	}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as given in the above mentioned post, $main$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler
• Collatz Conjecture