The 3n + 1 Problem

UVA Online Judge ID - 100

Welcome to one of the most famous and fascinating problems in all of mathematics — the 3n + 1 problem, also known as the Collatz conjecture.

It’s simple to describe, easy to code, yet incredibly deep — and to this day, no one has been able to prove it completely. 😮

Let’s explore the story behind it, understand what it’s asking, and then walk through how to solve it using Python.

The Idea

Here’s the rule:

Start with any positive integer n.

Then repeat the following steps until n becomes 1:

• If n is even, divide it by 2.
• If n is odd, multiply it by 3 and add 1.

And keep doing that — over and over.

Example

Let’s try it with n = 10:

So the full sequence looks like this:

10 5 16 8 4 2 1

That’s 16 numbers in total — so we say the cycle length for 10 is 7.

❓ The Challenge

Given two numbers, i and j, you need to find the maximum cycle length for any number between i and j (inclusive).

For example, if i = 1 and j = 10, we compute the cycle length for every number from 1 to 10, and the maximum among them turns out to be 20.

💾 Input and Output Format

Input: A series of pairs of integers i and j, one per line.(Each number is between 1 and 1,000,000.)

Output: For each pair, print three numbers on one line:

i j max_cycle_length

The first two are the same as the input, and the third is the maximum cycle length between them.

Example Input

1 10
100 200
201 210
900 1000

Example Output

1 10 20
100 200 125
201 210 89
900 1000 174

🐍 Python Solution — Step by Step

Let’s write a simple Python program to solve this.

Step 1: Define the Cycle Length Function

def cycle_length(n):
    count = 1
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        count += 1
    return count

This function follows the rules of the Collatz sequence until n becomes 1, counting how many steps it takes.

Step 2: Compute the Maximum Cycle Length Between Two Numbers

def max_cycle_length(i, j):
    start, end = min(i, j), max(i, j)
    max_length = 0
    for n in range(start, end + 1):
        max_length = max(max_length, cycle_length(n))
    return max_length

Notice we use min and max because sometimes i might be greater than j.

Step 3: Handle Multiple Input Lines

import sys
for line in sys.stdin:
    if not line.strip():
        continue
    i, j = map(int, line.split())
    print(i, j, max_cycle_length(i, j))

This reads pairs of numbers until the input ends and prints the results exactly as specified.

🚀 Optimization Tip

The straightforward version works fine for small inputs, but if you want to handle the full range (up to 1,000,000), you can cache results (a technique called memoization).

cache = {}

def cycle_length(n):
    if n in cache:
        return cache[n]
    original_n = n
    count = 1
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        count += 1
        if n in cache:
            count += cache[n] - 1
            break
    cache[original_n] = count
    return count

This way, repeated numbers are calculated only once — saving you precious seconds during large test cases. ⚡