Blogdemaths

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

Apr 24th, 2021 (edited)
534
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.00 KB | None
  1. # Calcul des cinq derniers chiffres du nombre de Graham
  2. # Article original : https://blogdemaths.wordpress.com/?p=4921
  3.  
  4. # Fonction PGCD
  5. def pgcd(a,b):
  6.     while b:
  7.         a,b = b,a%b
  8.     return a
  9.    
  10. # Fonction indicatrice d'Euler
  11. def phi(n):
  12.     resultat = 1
  13.     for i in range(2,n):
  14.         if (pgcd(i,n)==1):
  15.             resultat+=1
  16.     return resultat
  17.  
  18.  
  19. # Derniers chiffres du nombre de Graham
  20. def derniers_chiffres_Graham(d):
  21.     """ d est le nombre de chiffres voulus """
  22.  
  23.     N = 10**d
  24.  
  25.     # On calcule la suite N, phi(N), phi(phi(N)), etc.
  26.     modulo = [N]
  27.     while(phi(N)>1):
  28.         modulo.append(phi(N))
  29.         N = phi(N)
  30.  
  31.  
  32.     # On renverse la liste pour faire les calculs depuis la fin
  33.     modulo = modulo[::-1]
  34.  
  35.     # On effectue les différents calculs
  36.     a = 3
  37.     for k in range(len(modulo)-1):
  38.         a= pow(3,a%modulo[k],modulo[k+1])
  39.  
  40.     return a
  41.  
  42.  
  43. # Affiche les cinq derniers chiffres du nombre de Graham
  44. print(derniers_chiffres_Graham(5))    
  45.  
RAW Paste Data Copied