"""
Question 2:

If n is even, process it as n/2
If n is odd, process it as 3n + 1

Find the number of steps required for a number to get to 1.

Example: 3 -> 10 -> 5-> 16 -> 8 -> 4 -> 2 -> 1
Output = 7 steps

Find the number with the highest number of steps under 1 million.
"""




# Map to save te number of steps for a given number. We don't want to re-calculate it again and again, so we cache in this map.
d = {}


def get_steps(i):
    # If result is in map, return directly
    if i in d:
        return d[i]

    # Base case
    if i == 1:
        return 0

    # Calculate the steps using recurrence relation.
    # E.g.
    # steps(3) = steps(10) + 1
    # steps(10) = steps(5) + 1
    if i%2 == 0:
        t = i / 2
    else:
        t = (3 * i) +  1

    d[i] = get_steps(t) + 1    # Cache it in map before returning

    return d[i]


def find_max():
    max_i = None
    max_steps = 0
    for i in range(2, 1000001):
        t = get_steps(i)
        if t > max_steps:
            max_steps = t
            max_i = i
    return max_steps, max_i

#print(get_steps(3))
print(find_max())