Problem

A Collatz sequence in mathematics can be defined as follows. Starting with any positive integer:

  • If n is even, the next number in the sequence is n / 2
  • If n is odd, the next number in the sequence is 3n + 1 It is conjectured that every such sequence eventually reaches the number 1. Test this conjecture.

Bonus: What input n <= 1000000 gives the longest sequence?

Examples

Example 1

1
2
3

Input: n = 6
Output: [6, 3, 10, 5, 16, 8, 4, 2, 1]
Explanation: Starting from 6, the sequence follows: 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Example 2

1
2
3

Input: n = 11
Output: [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Explanation: Starting from 11, the sequence follows: 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Solution

Method 1 - Run the simulation

The Collatz sequence is generated by the following rules:

  1. If the number is even, divide it by 2.
  2. If the number is odd, multiply it by 3 and add 1. The conjecture states that eventually, the sequence will reach 1.

To test this conjecture, we can implement the sequence generation and print the results.

Approach

  1. Generate the Sequence: Start from the given number and apply the rules iteratively until reaching 1.
  2. Track the Sequence: Store the sequence in a list and update based on the rules.
  3. Bonus Task: Iterate through all numbers up to 1,000,000 to find the number that yields the longest sequence.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Solution {
    public List<Integer> collatzSequence(int n) {
        List<Integer> sequence = new ArrayList<>();
        while (n != 1) {
            sequence.add(n);
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n = 3 * n + 1;
            }
        }
        sequence.add(1);
        return sequence;
    }

    public int longestCollatz(int limit) {
        int maxLength = 0;
        int number = 0;
        for (int i = 1; i <= limit; i++) {
            int length = collatzSequence(i).size();
            if (length > maxLength) {
                maxLength = length;
                number = i;
            }
        }
        return number;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.collatzSequence(6));  // Output: [6, 3, 10, 5, 16, 8, 4, 2, 1]
        System.out.println(solution.collatzSequence(11));  // Output: [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
        System.out.println(solution.longestCollatz(1000000));  // Output: The number <= 1000000 with the longest Collatz sequence
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def collatzSequence(self, n: int) -> List[int]:
        sequence = []
        while n != 1:
            sequence.append(n)
            if n % 2 == 0:
                n //= 2
            else:
                n = 3 * n + 1
        sequence.append(1)
        return sequence

    def longestCollatz(self, limit: int = 1000000) -> int:
        max_length = 0
        number = 0
        for i in range(1, limit + 1):
            length = len(self.collatzSequence(i))
            if length > max_length:
                max_length = length
                number = i
        return number

# Example usage:
solution = Solution()
print(solution.collatzSequence(6))  # Output: [6, 3, 10, 5, 16, 8, 4, 2, 1]
print(solution.collatzSequence(11))  # Output: [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
print(solution.longestCollatz())  # Output: The number <= 1000000 with the longest Collatz sequence

Complexity

  • ⏰ Time complexity: O(N log N) approximately for generating the sequences, where N is the starting number.
  • 🧺 Space complexity: O(N) for the list that stores the sequence.