On dit que pendant la guerre de 1870, Édouard Lucas a fait le constat qu'il est difficile de mettre en tas pyramidal, un nombre carré de boulets. Ce dessin de David Eppstein illustre le problème:
Ce tas de boulets comprend 16+9+4+1=30 boulets et effectivement 30 n'est pas un carré.
Ce problème est intéressant du point de vue algorithmique: Comment
L'algorithme utilisé consiste à regarder s'il y a des chiffres après la virgule dans le développement décimal de √(n) :
CoffeeScript étant basé sur JavaScript, n'a pas de fonction donnant les éventuels chiffres après la virgule. Donc pour les
connaître, on soustrait à x sa partie entière avec x - Math.floor x
. Oui mais... L'image de 2,999999999999 par cette fonction
est 0,9999999999989999 qui a bien des chiffres après la virgule, alors que 2,999999999999 est entier "aux erreurs de calcul près". Donc,
Math.floor
, il vaut mieux arrondir avec Math.round
au cas où x est, de peu, inférieur à un entier;
Maintenant que CoffeeScript est enrichi d'une nouvelle fonction isInteger
, on va s'en servir pour définir une nouvelle
fonction isSquare
:
Ce qui précède (création d'algorithmes pour faciliter la suite) ne sert pas à calculer la somme des carrés, mais on s'en servira après. Par contre, l'algorithme pour la somme des carrés est classique:
sum
pour la somme et index
pour l'indice dans la boucle.index
est incrémenté avec index++
sum
Le fait de boucler avec for
plutôt que while
permet de raccourcir le code; on peut raccourcir encore plus
en inversant les proposition principale et subordonnée :
Il ne reste maintenant plus qu'à assembler les résultats des deux premières parties pour pouvoir chercher l'éventuelle possibilité que la somme des carrés des entiers successifs finisse par être elle-même un carré.
L'algorithme est simple :
On boucle à partir de n = 2
parce que des tas de 0 ou 1 boulet ne sont pas considérés comme des tas...
Si on détaille les boucles, on constate qu'on calcule plusieurs fois le carré de 2 :
Ceci parce qu'il y a des boucles imbriquées et que la somme des carrés jusqu'à n+1 est juste (n+1)2 de plus que la somme des carrés allant jusqu'à n: Autrement dit, la suite un des carrés des nombres inférieurs ou égaux à n, vérifie la relation de récurrence suivante :
Ceci permet de simplifier l'algorithme, en calculant moins souvent les carrés, et en cherchant plus vite :
On peut améliorer l'affichage final :
Ceci répond à la question de l'existence d'un nombre n (autre que 0 et 1) tel que la somme des carrés des n premiers entiers est elle-même un carré. Mais y en a-t-il d'autres ?
Pour retrouver algébriquement ces résultats, on peut faire appel à du calcul formel, en effet il existe une forme explicite pour la
somme des carrés. Ici on va utiliser Xcas, mais d'autres logiciels de calcul formel font tout autant l'affaire. Tout d'abord, on peut retrouver
la somme des 4 premiers carrés avec sum(k^2,k,0,4)
qui répond bien 30. Ensuite il suffit de remplacer 4 par n en faisant sum(k^2,k,0,n)
pour avoir (2*(n+1)3-3*(n+1)2+n+1)/6. Mieux, avec simplify(sum(k^2,k,0,n))
, on apprend que la somme des n
premiers carrés est (2*n3+3*n2+n)/6 (formule à montrer par récurrence évidemment). On a donc déjà un moyen de calculer
la somme des carrés sans boucler. Par ailleurs, en demandant à Xcas factor((2*n^3+3*n^2+n)/6)
on a une forme encore plus simple
pour la somme des carrés: n(n+1)(2n+1)/6. Il s'agit donc de résoudre l'équation diophantienne 2x3+3x2+x=6y2. Xcas n'y
arrive pas, mais Wolfram Alpha y parvient, en lui soumettant le calcul 2*x^3+3*x^2+x=6*y^2
.
Wolfram Alpha dessine la courbe elliptique (puisque l'équation qu'on lui a fournie est celle d'une courbe elliptique):
Parmi les résultats affichés, on voit