somme des diviseurs

Publié le par jö

Je viens de découvrir grâce à fsm la méthode la plus rapide que je connaisse pour construire la table de la somme des diviseurs des entiers >0 inférieurs à n.

Elle est due à Euler et procède par récurrence:

On construit une suite T_n,n>0 de travail telle que T_1=1 et T_n = T_{n-1} + n/2 si n est pair et T_n = T_{n-1} + n si n est impair.

On note D_n la somme des diviseurs de n telle que si n est premier D_n=n+1. Euler énonce que
D_n = sum( i=1, i=imax, s_i D_{n-T_i} ) où
  • imax est l'indice limite pour lequel n-T_imax>=0 et n-T_{imax+1}<0
  • s_i est un signe qui vaut +1 si i%4=1 ou si i%4=2 et -1 si i%4=3 ou si i%4=0
Il ajoute que dans le cas où n-T_imax=0 on doit remplacer, dans le terme s_imax D_{n-T_imax}, le facteur D_{n-T_imax} par n.

On commence alors par poser D_1=1.
D_2 = s_1 D_{2-T_1} + s_2 D_{2-T_2}  et, comme T_2=2, D_2 = D_1 + 2 = 3
D_3 = s_1 D_{3-T_1} + s_2 D_{3-T_2} car 3-T_3 =3- 5<0 : D_3 = D_2 + D_1 = 4
D_4 = s_1 D_{4-T_1} + s_2 D_{4-T_2} car 4-T_3<0 : D_4 = D_3 + D_2 = 7
D_5 = s_1 D_{5-T_1} + s_2 D_{5-T_2} + s_3 D_{5-T_3} = D_4 + D_3 - 5 = 6
et ainsi de suite...

Publié dans mathblog

Commenter cet article