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'application erdos.jar retourne pour un entier naturel N strictement positif donné, une décomposition possible de N 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).

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

Ce nombre entier, nommé "pm" dans l'application, peut être très grand (il est de l'ordre de 2³¹ 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 | erdos.jar | erdos.java | une démonstration | Le théorème d'Erdös-Suranyi-Bodini ]