San Vu Ngoc - IRMAR

Initialisations¶

In [1]:
%matplotlib inline
# inline can be replaced by notebook to get interactive plots
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as img
import matplotlib.cm as cm
import matplotlib.colors as colors
In [2]:
plt.rcParams['figure.figsize'] = (20.0, 12.0) # set figures display bigger

Suite de Fibonacci¶

digression ?

https://youtu.be/DxmFbdp7v9Q?t=474

In [3]:
def fibPaire (n):
    if n == 0:
        return (0,1)
    else:
        a,b = fibPaire (n-1)
        return (b,a+b)
    
def fib (n):
    a,b = fibPaire (n)
    return a
In [4]:
[fib(n) for n in range(0,17)]
Out[4]:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]

La complexité la "pire" est obtenue par des paires de nombres de Fibonacci consécutifs. Leur pgcd est toujours 1 (ils sont premiers entre eux). À démontrer par récurrence...

In [5]:
#voir feuille 03
def pgcdIter (a,b):
    r = a % b
    if r == 0:
        return 1
    else:
        return 1 + pgcdIter(b,r)
In [6]:
pgcdIter(9227465, 14930352)
Out[6]:
35

Pour tester des grands nombres, il faut une version non récursive de l'algorithme.

In [7]:
def fibI (n):
    a,b = 0,1
    while n > 0:
        (a,b) = (b,a+b)
        n = n-1
    return a
In [10]:
[fibI(n) for n in range(0,18)]
Out[10]:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]

On constate que les points où le nombre d'itération est le plus grand correspondent à des couples (i,j) où les i,j sont des éléments consécutifs dans la suite de Fibonacci !

In [11]:
fibI(974), fibI(974+1)
Out[11]:
(160131437125022133570186981636530600256034719271619021063640417693436516163698377535248015679488033602845112321108929620534730439060000506398830226180857811739131287777823445209422467744194016647915972857,
 259098107935652557104489133457117935287501385615468464797658075441635685688364082902818922538578546112563887878124152051556445086889386828976126497605113833423713583754975704308251673170580841059906839650)
In [12]:
float(fibI(974))
Out[12]:
1.6013143712502212e+203
In [15]:
# voir feuille 03
def pgcdI (a,b):  # version "itérative"
    while b != 0:
        (a, b) = (b, a % b)
    return a
In [16]:
pgcdI(fibI(974), fibI(974+1))
Out[16]:
1
In [17]:
pgcdIterI(fibI(974), fibI(974+1))

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
/tmp/ipykernel_55471/1978963195.py in <module>
----> 1 pgcdIterI(fibI(974), fibI(974+1))

NameError: name 'pgcdIterI' is not defined
In [18]:
fibI(972), fibI(972+1)
Out[18]:
(61164766314391710035884829815943265224568052927769577329622759945237346639032672167677108820397521093126336764093707189513015791230614183821533954756601790054548991800671186110593262317807192235925106064,
 98966670810630423534302151820587335031466666343849443734017657748199169524665705367570906859090512509718775557015222431021714647829386322577296271424256021684582295977152259098829205426386824411990866793)
In [19]:
pgcdIterI(fibI(972), fibI(972+1))

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
/tmp/ipykernel_55471/865368299.py in <module>
----> 1 pgcdIterI(fibI(972), fibI(972+1))

NameError: name 'pgcdIterI' is not defined

Mauvais (i,j)¶

On trace les (i,j) qui sont les $(F_k,F_{k+1})$ et leurs multiples. La couleur indique la complexité de l'algorithme d'Euclide pour pgcd(i,j). On commence à $k=k0$.

In [ ]:
In [20]:
def BAD (n,k0):
    T = np.zeros((n,n))
    F1, F2 = fibPaire(k0)   # on part les k0-ème et 
    m = 1                   # (k0+1)-ème nombres de Fibonacci.    
    while F2 < n:
        i, j = F1, F2
        while j < n:
            T[i,j] = m
            T[j,i] = m
            i, j = i+F1, j+F2
        m = m+1
        F1, F2 = F2, F1+F2   # on passe au couple de Fibonacci suivant
    return T
In [21]:
ar=BAD(100,4)
plt.imshow(ar, interpolation='none', cmap=cm.gist_earth)
plt.colorbar()
Out[21]:
<matplotlib.colorbar.Colorbar at 0x7efbce96b730>

Le nombre d'or¶

Les pentes des droites de l'image ci-dessus sont données par le nombre d'or !

$\phi = \frac{1+\sqrt{5}}2$

In [28]:
pgcdI(fibI(3000), fibI(3000+1))
Out[28]:
1
In [23]:
fibI(3001)
Out[23]:
664390460366960072280217847866028384244163512452783259405579765542621214161219257396449810982999820391132226802809465132446349331994409434926019045342723749188530316994678473551320635101099619382973181622585687336939784373527897555489486841726131733814340129175622450421605101025897173235990662770203756438786517530547101123748849140252686120104032647025145598956675902135010566909783124959436469825558314289701354227151784602865710780624675107056569822820542846660321813838896275819753281371491809004412219124856375121694811728724213667814577326618521478357661859018967313354840178403197559969056510791709859144173304364898001
In [24]:
import math
In [25]:
(1+math.sqrt(5))/2
Out[25]:
1.618033988749895
In [30]:
# une très bonne approximation !
fibI(3000+1) / fibI(3000)
Out[30]:
1.618033988749895
In [ ]: