Paul Erdös mort en 1996 à l'âge de 83 ans est très connu pour ses problèmes sur la théorie des nombres dont voici l'un d'eux : quelle est la dimension maximale d'un sous-ensemble de nombres entiers (a_1,?a_k) choisis parmi les entiers 1,2,...,n tels que a_i + a_j ne soit jamais un carré parfait (i et j quelconques y compris i=j). Par exemple si n=7 alors (1,4,6,7) est l'un des sous-ensembles recherchés.

Quelle est le sous-ensemble des 100 premiers nombres entiers qui a cette propriété avec le plus grand nombre possible d'éléments ?

 Solution