# Arup Guha
# 10/18/2022
# More Efficient Solution to CIS 3362 Hmk #5, Question #7

''' Output for n = 20 is:
    The answer here is 281929.
    If the one isn't counted, the min value for 20 steps is 557057.
'''

# Regular GCD function.
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)

# Calculates phi in roughly O(sqrt(n)) time.
def phi(n):

    # We will multiply this value every time we find a new unique
    # prime divisor of n.
    res = n
    i = 2

    # Stop when we are done searching for prime divisors.
    while i*i <= n:

        # We found out, update our result.
        if n%i == 0:
            res = res//i*(i-1)

        # Now, divide out all copies of i.
        while n%i == 0:
            n //= i

        # Go to next value.
        i += 1

    # A prime is leftover; take care of it.
    if n > 1:
        return res//n*(n-1)

    # Now done.
    return res

# Solves the problem for the input value.
def main():

    # Get user input.
    steps = int(input("What value of f(n) are you looking for?\n"))

    # dp[i] will store f(i). I seed the array here.
    dp = [0,1,2]

    # Break out when we find the value.
    while True:

        # Figure out phi of this value. Then, use our look up of f(phi(n))
        # To figure out what f(n) should be.
        value = phi(len(dp))
        dp.append(dp[value]+1)

        # We got where we needed to, let's break out.
        if dp[value]+1 == steps:
            print("min value for",steps,"steps is",len(dp)-1)
            break

# Run it!
main()