Le théorème de Lamé

[ast]

Connaissez vous le théorème de Lamé ?

Je l'ai découvert ce matin et je le trouve joli.
Alors le voici:


Le nombre d'étapes de l'algorithme d'Euclide pour
trouver le PGCD de 2 nombres a et b avec b <= a
est majoré par E(Ln(b)/Ln(phi)) où E() désigne la
partie entière et phi est le nombre d'or.

La majoration est atteinte quand a et b sont 2
nombres de Fibonacci consécutifs

-Algorithme d'Euclide (en python):

def gcd(a, b):

steps=0

while b:
a, b = b, a%b
steps += 1
return a, steps

-Suite de Fibonacci:

def fibonacci(n):

if n==0: return 0
a, b, = 0, 1
for i in range(n-1):
a, b = b, a+b
return b

Avec 2 entiers de Fibonacci consécutifs, je trouve toujours 1 de plus
que la majoration théorique

[fibonacci(i) for i in range(100)][-3:-1]

[83621143489848422977, 135301852344706746049]

gcd(135301852344706746049, 83621143489848422977)

(1, 96)

donc 96 étapes

math.log(83621143489848422977)/math.log(1.61803398875)

95.32772406180257
soit 95 étapes

si quelqu'un voit où ça cloche ?

[Fabrice]

Le 15/03/2018 à 12:34, ast a écrit :> si quelqu'un voit où ça cloche ?
Dans l'avant dernière itération de ta fonction gcd, tu as a=1 et b=1.
Tu as donc fini, l'étape suivante est inutile et ne doit pas être comptée.

cordialement,
Fabrice.

---
L'absence de virus dans ce courrier électronique a été vérifiée par le logiciel antivirus Avast.
https://www.avast.com/antivirus

[ast]

Post by Fabrice
Le 15/03/2018 à 12:34, ast a écrit :> si quelqu'un voit où ça cloche ?
Dans l'avant dernière itération de ta fonction gcd, tu as a=1 et b=1.
Tu as donc fini, l'étape suivante est inutile et ne doit pas être comptée.
cordialement,
Fabrice.
---
L'absence de virus dans ce courrier électronique a été vérifiée par le
logiciel antivirus Avast.
https://www.avast.com/antivirus

exact, merci