Les nombres premiers sont en quelque sorte les atomes des nombres, les objets primordiaux.
Un des plus anciens algorithmes connus. Sa formulation est simplissime comme le montre le code python ci-dessous mais sa puissance est redoutable.
def pgcd(a,b):
if b == 0:
return a
else:
return pgcd(b,a%b)
L’étude de sa complexité algorithmique fait intervenir le nombre d’or :
Les fractions continues permettent d’enquêter visuellement sur le degré de rationalité d’un nombre irrationnel en déterminant les fractions successives qui l’approximent le mieux.
Elles rendent plus transparents les différents compromis qu’on est amené à faire pour tenter de caler des nombres carrés dans des nombres ronds du fait de périodicités incompatibles. On explique ainsi les calendriers, les almanachs d’éclipses et les 12 notes de musiques.
Les fractions continues nous ont aussi été utiles pour l’étude de la complexité de l’algorithme d’Euclide avec lequel elles entretiennent un lien étroit.
Le nombre d’or est une sorte de tarte à la crème des mathématiques. D’infinies élucubrations lui font tenir un rôle quasi mystique.
On ne peut nier cependant qu’il apparaît parfois dans des endroits étonnants. Reste seulement à démystifier sa présence.
La vidéo suivante explique ainsi comment suite de Fibonacci et nombre d’or apparaissent dans certains arrangements des plantes. Armé d’un peu de physique et des fractions continues, leurs présences devient somme toute logique, voire triviale.
Le nombre d’or fait aussi son apparition dans l’étude de la complexité de l’algorithme d’Euclide comme on l’a vu plus haut.