somme des diviseurs
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ù
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...
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
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...