Le théorème d'Erdös-Suranyi

Théorème :
Tout entier n peut s'écrire sous la forme N = a112+a222+a332+...+ann2 où a1, a2...an appartiennent à l'ensemble {-1, 1}.

L'appliquette ci-contre retourne pour un entier naturel N strictement positif donné une écriture possible sous forme de sommes et différences de carrés.


Le problème dans ce théorème est que l'entier n est inconnu. D'où l'idée de chercher une décomposition avec n = 1 puis avec n = 2... jusqu'à trouver un décomposition qui marche. Essayer toute les combinaisons possibles de a1, a2...an peut prendre du temps quand n devient grand (2n possibilités). Ainsi si N est de l'ordre de 10000 le temps de calcul peut atteindre une heure suivant l'ordinateur utilisé. L'ordinateur affiche des points à l'écran pour faire patienter (un point chaque fois qu'on passe de n à n+1). Attention, il n' y a pas moyen d'interrompre le calcul.

L'idée dans cette appliquette consiste à utiliser les nombres 0 et 1 plutôt que -1 et 1 afin de remplacer la suite a1, a2... an par un nombre entier de n bits. Il suffit alors d'ajouter 2n fois le nombre 1 dans une boucle pour obtenir toutes les combinaisons possibles.

Ce nombre entier, nommé "pm" dans l'appliquette, peut être très grand (il est de l'ordre de 231 pour N = 10000). Il est du type "BigInteger" afin de bénéficier de la fonction "testBit ()".

Seulement la fonction "testBit (int i)"renvoie un résultat, en l'occurrence 0, même lorsque l'indice dépasse la taille de l'entier dans sa représentation binaire d'où l'utilisation de "lpm" qui contient le nombre de bits et "pm2" la valeur maximale. Si on l'atteint c'est que la valeur n est insuffisante. On l'augmente donc d'une unité (lpm= lpm + 1, pm2=2*pm2) et on recommence les essais.

[ retour page d'accueil | source | une démonstration | pour aller plus loin ]