Blogdemaths - Derniers chiffres du nombre de Graham (2ème partie)

# Calcul des cinq derniers chiffres du nombre de Graham
# Article original : https://blogdemaths.wordpress.com/?p=4921

# Fonction PGCD
def pgcd(a,b):
    while b:
        a,b = b,a%b
    return a

# Fonction indicatrice d'Euler
def phi(n):
    resultat = 1
    for i in range(2,n):
        if (pgcd(i,n)==1):
            resultat+=1
    return resultat


# Derniers chiffres du nombre de Graham
def derniers_chiffres_Graham(d):
    """ d est le nombre de chiffres voulus """

    N = 10**d

    # On calcule la suite N, phi(N), phi(phi(N)), etc.
    modulo = [N]
    while(phi(N)>1):
        modulo.append(phi(N))
        N = phi(N)


    # On renverse la liste pour faire les calculs depuis la fin
    modulo = modulo[::-1]

    # On effectue les différents calculs
    a = 3
    for k in range(len(modulo)-1):
        a= pow(3,a%modulo[k],modulo[k+1])

    return a


# Affiche les cinq derniers chiffres du nombre de Graham
print(derniers_chiffres_Graham(5))