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

''' Output and answer to this question:

    min value is 257. If the last term in the sequence 1 isn't counted
    the answer obtained is 641.
'''

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

# Returns phi of n, running in O(nlgn) time. Calculates gcd between each
# integer from 1 to n-1 with n.
def phi(n):
    res = 0
    for i in range(1,n):
        if gcd(i,n) == 1:
            res += 1
    return res

# Runs the solution.
def main():

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

    # Keep going...we'll break out when we're done.
    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 == 10:
            print("min value is",len(dp)-1)
            break

# Run it.
main()