problem 14 https projecteuler netproblem14 problem statement the following iterative sequence is defined for the set of positive integers n n2 n is even n 3n 1 n is odd using the rule above and starting with 13 we generate the following sequence 13 40 20 10 5 16 8 4 2 1 it can be seen that this sequence starting at 13 and finishing at 1 contains 10 terms although it has not been proved yet collatz problem it is thought that all starting numbers finish at 1 which starting number under one million produces the longest chain returns the number under n that generates the longest sequence using the formula n n2 n is even n 3n 1 n is odd solution1000000 837799 solution200 171 solution5000 3711 solution15000 13255 returns the number under n that generates the longest sequence using the formula n n 2 n is even n 3n 1 n is odd solution 1000000 837799 solution 200 171 solution 5000 3711 solution 15000 13255
def solution(n: int = 1000000) -> int:
    
    largest_number = 1
    pre_counter = 1
    counters = {1: 1}

    for input1 in range(2, n):
        counter = 0
        number = input1

        while True:
            if number in counters:
                counter += counters[number]
                break
            if number % 2 == 0:
                number //= 2
                counter += 1
            else:
                number = (3 * number) + 1
                counter += 1

        if input1 not in counters:
            counters[input1] = counter

        if counter > pre_counter:
            largest_number = input1
            pre_counter = counter
    return largest_number


if __name__ == "__main__":
    print(solution(int(input().strip())))