The 3n + 1 problem

Consider the following algorithm to generate a sequence of numbers.

Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1.

For example, the following sequence of numbers will be generated for

n = 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints. Input The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0. Output For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input. Sample Input

1 10

100 200

201 210

900 1000

Sample Output

1 10 20

100 200 125

201 210 89

900 1000 174

import java.util.*;
import java.math.*;
import java.io.*;

public class Main {

	// cache for already computed cycle lengths
	public static int[] cache = new int[1000000];

	// a function that returns the
	// next number in the sequence
	public static long next(long n) {
		if (n % 2 == 0)
			return n / 2;       // if n is even
		else
			return 3 * n + 1;   // if n is odd
	}

	public static int cycleLength(long n) {
		// our base case
		// 1 has a cycle length of 1
		if (n == 1)
			return 1;

		// check if we've already cached the
		// cycle length of the current number
		if (n < 1000000 && cache[(int)n] != 0)
			return cache[(int)n];

		// the cycle length of the current number is 1 greater
		// than the cycle length of the next number
		int length = 1 + cycleLength(next(n));

		// we cache the result if the
		// current number is not too big
		if (n < 1000000)
			cache[(int)n] = length;

		return length;
	}

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out, true);

		// while there is some input to read
		while (in.hasNextInt()) {
			int i = in.nextInt(),
			    j = in.nextInt(),
			    from = Math.min(i, j),
			    to = Math.max(i, j),
			    max = 0;

			// loop through all the numbers
			// and find the biggest cycle
			for (int n = from; n <= to; n++) {
				max = Math.max(max, cycleLength(n));
			}

			out.printf("%d %d %d\n", i, j, max);
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *