"""
 collatz.py

 See https://projecteuler.net/problem=14

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

 tested with python 3

 $ python collatz.py 
 -- collatz --
  longest sequence up to 1,000,000 
  n =  837799

 April 30 2018 , in intro coding class
"""


def next_collatz(n):
    """ return the next collatz number 
        >>> next_collatz(13)
        40
        >>> next_collatz(40)
        20
    """
    if n % 2 == 0:
        return n // 2     # integer division in python 3
    else:
        return 3 * n + 1

def count_steps(n):
    """ return number of steps to get to 1 
        >>> count_steps(13) # 13 40 20 5 16 8 4 2 1
        10
    """
    count = 1
    while n != 1:
        n = next_collatz(n)
        count = count + 1
    return count

def find_biggest(n_max):
    """ find the biggest number of steps up to n_max """
    biggest_n = 0
    biggest_count = 0
    for n in range(1, n_max):
        steps = count_steps(n)
        if steps > biggest_count:
            biggest_n = n
            biggest_count = steps
    return biggest_n

def main():
    print("-- collatz --")
    print(" longest sequence up to 1,000,000 ")
    n = find_biggest(1000000)
    print(" n = ", n)
    
if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()