Comment dire 33 avec 3 cubes ? 4


Le gars qui m’a pourri ma dernière soirée du printemps s’appelle Mike Croucher. Sur son blog « Walking Randomly » il a négligemment posé le problème suivant:

Il est possible d’écrire beaucoup d’entiers comme la somme des cubes de 3 entiers, par exemple: 99 = (-5)^3 + 2^3+ 6^3
Un exemple plus compliqué est: 91 = (-67134)^3 + (-65453)^3+(83538)^3
Votre tâche est de trouver les entiers x,y, et z tels que: 33 = x^3 + y^3 + z^3

Comme j’ai bien vu que la solution pour 91 impliquait de grands entiers, je me suis dit que 33 demanderait probablement des nombres encore plus grands, mais j’ai quand même vite pondu le programme Python suivant pour voir:

res={} #dictionary of results
def store(n,x,y,z):
    if n>=0 and n<100 and n not in res:
        res[n]=(x,y,z)
        print n,res[n]

cube=[]
x=0
while True:
    x3=x*x*x
    cube.append(x3)
    for y in range(x+1):
        y3=cube[y]
        for z in range(x+1):
            z3=cube[z]
            store(x3+y3+z3,x,y,z)
            store(x3-y3+z3,x,-y,z)
            store(x3+y3-z3,x,y,-z)
            store(x3-y3-z3,x,-y,-z)
            store(-x3+y3+z3,-x,y,z)
            store(-x3-y3+z3,-x,-y,z)
            store(-x3+y3-z3,-x,y,-z)
            # store(-x3-y3-z3,-x,-y,-z) #you're right Neamar, it's useless
    x+=1
    if x==50: #show "small" results
        for n in range(100):
            if n in res:
                print n,res[n]
            else:
                print n,'?'

En moins d’une seconde il trouve les 69 des 100 premiers entiers qui sont des sommes de cubes d’entiers inférieurs à 100. Le plus « compliqué » est 78=-55³+53³+26³ .

Ensuite il mouline pendant des heures pour trouver 51=-796³+659³+602³ et 16=1626³-1609³-511³, et pendant ce temps j’ai exploré les liens émaillant les premiers commentaires de l’article de « Walking Randomly ».

Il s’avère que le problème soumis par Mike Croucher est extrêmement difficile, voire impossible. Cette page liste les solutions trouvées par mon programme, et d’autres qui ont nécessité des algorithmes beaucoup plus fûtés que le mien pour résoudre cette équation diophantienne :

  • 87 = 4271³ – 4126³ – 1972³ , découvert en 1964 [1]
  • 96 = -15250³ + 13139³ + 10853³
  • 91 = 83538³ – 67134³ – 65453³
  • 80 = -112969³ + 103532³ + 69241³
  • 39 = -159380³ + 134476³ + 117367³ découvert en 1991 [2]
  • 75 = – 435203231³ + 435203083³ + 4381159³  découvert en 1993 [3]
  • 84 = 41639611³ – 41531726³ – 8241191³ découvert en 1994 [4]
  • 30 =  2220422932³ – 2218888517³ – 283059965³ ainsi que
    52 = -61922712865³ + 60702901317³ + 60702901317³ par la même équipe, qui a mis au point l’algo le plus performant du moment [5]
  • 24 =15584139827³ – 15550555555³ – 2901096694³ a été découvert avec l’algo précédent en 2001 par D. J. Bernstein, dont la page http://cr.yp.to/threecubes.html est consacrée à ce problème et son historique

A part ça, les matheux démontrent (essayez…) que les nombres de la forme 9n+4 et 9n+5 ne peuvent pas être la somme de trois cubes, ce qui règle le cas de 4,5,13,14,22,23 etc.

Bon… je n ai pas vraiment le droit d’utiliser ce dessin, mais il va tellement bien là que j espère que vous ne m en voudrez pas, cher Docteur G…

Reste 33 (et 42 et beaucoup d’autres), qui résistent effrontément aux informaticiens cherchant à les obtenir, ainsi qu’aux mathématiciens essayant de prouver que c’est peine perdue…

C’est énervant qu’un petit problème tout bête comme celui-ci puisse résister ainsi aux ordinateurs les plus puissants.  Et motivant de penser qu’une solution est peut-être à la portée d’amateurs éclairés. Des idées ?

Références:

  1. Gardiner, V. L., Lazarus, R. B., & Stein, P. R. « Solutions of the diophantine equation x^3+z^3=z^3-d. « , 1964, Mathematics of Computation, 18, 408-413
  2. Heath-Brown, D. R., Lioen, W. M., & te Riele, H. J. J. »On Solving the Diophantine Equation $x^3 + y^3 + z^3 = k$ on a Vector Computer« , 1993, Mathematics of Computation, 61, 235-244
  3. Andrew Bremner, « On sums of three cubes« , 1993
  4. B. Conn and L. Vaserstein, « On sums of three integral cubes », 1994, Contemp. Math. 166, 285-294.
  5. Eric Pine, Kim Yarbrough, Wayne Tarrant and Michael Beck, Noam D. Elkies, « Rational points near curves and small nonzero |x3-y2| via lattice reduction« , 2000, ANTS IV
  6.  Michael Beck, Eric Pine, Wayne Tarrant, Kim Yarbrough Jensen « New integer representations as the sum of three cubes », 2007, Math. Comp. 76, 1683-1690 (page AMS)
  7. Wacław Sierpiński "Elementary Theory of Numbers" (1988) North-Holland ISBN:0444866620 WorldCat Goodreads Google Books   (online)
  • http://drgoulu.com Dr. Goulu

    Fait un programme beaucoup plus efficace pour chercher les solutions les unes après les autres. Il trouve 87 à la régulière, et quelques suivants en trichant:

    from math import copysign
    max=200000
    cube=[x*x*x for x in range(max)]
    cubes={x*x*x:x for x in range(max)}
    def sumof3cubes(n,max=max,x=0):
        if n%9 in [4,5]: return None
        while x&lt;max:
            x3=cube[x]
            for y in range(x+1):
                y3=cube[y]
                z3=x3+y3-n
                if abs(z3) in cubes:
                    z=-int(copysign(cubes[abs(z3)],z3))
                    return x,y,z
                z3=x3-y3-n
                if abs(z3) in cubes:
                    z=-int(copysign(cubes[abs(z3)],z3))
                    return x,-y,z
                z3=-x3-y3-n
                if abs(z3) in cubes:
                    z=-int(copysign(cubes[abs(z3)],z3))
                    return -x,-y,z
            x+=1
        return '?','?','?'
    
    for n in range(100):
        print n,sumof3cubes(n,100)
    
    print 87,sumof3cubes(87,5000) #takes ~8 seconds
    print 96,sumof3cubes(96,max,13139)  #cheat a bit
    print 91,sumof3cubes(91,max,67134)  #cheat a bit more
    print 80,sumof3cubes(80,max,103532) #cheat a lot
    print 39,sumof3cubes(39,max,134476) #cheat a lot more
    
  • Kondor

    Bonjour, avez vous essayer d’exécuter le script python avec la librairie psyco (http://psyco.sourceforge.net/) … ceci devrait grandement accélérer la recherche …

    • http://drgoulu.com Dr. Goulu

      le langage de programmation, le compilateur ou même l’ordinateur ne change pas grand chose pour de tels problèmes. C’est à cause de la complexité de l’algorithme. Le programme de l’article est « O(n^3) » car il utilise 3 boucles imbriquées, donc il met environ 1’000’000 plus de temps à trouver la solution du 87 (qui demande des x,y,z autour de 4000) que pour trouver toutes les petites solutions (avec des x,y,z autour de 40)…. Ensuite pour le 96 il faut monter à 16000, ce qui multiplie encore le temps par 4x4x4=64 etc.

      La seule solution est d’utiliser des algos de complexité plus faible. Celui de mon commentaire ci-dessus est O(n^2), et je peux « tricher » en le rendant O(n) en lui soufflant le 2ème plus grand des x,y,z, ce qui lui permet de « trouver » les solutions pour 96, 91, 80 et 39 en moins de une seconde, contre des années avec le premier programme…

      mais merci quand même pour le lien vers pysco, c’est toujours intéressant. Et bienvenue sur ce blog !

  • Antoine

    J’ai codé un petit programme à mon tour et il trouve le 16 aussitôt, avec les opérateurs 14,12 et 10.
    Aussi, je suis parvenu à trouver le 51 en 1 seconde, et le 87 en moins de 20 secondes.
    Et pourtant, le tout est developpé sur une plateforme peu réactive (windev).