"jeu de l'année" 2012 et autres : c'est fini.

(mis à jour plusieurs foirs après correction de bugs et améliorations, cf commentaires...) 

Je m’apprêtais à passer une soirée tranquille quand je suis tombé sur un tweet de @ElJj disant: "Qui va me battre au "jeu de l'année" ? http://eljjdx.canalblog.com/archives/2012/01/15/23243094.html".

Python bouffant du matheux

Un seul click m'a torpillé non pas une, mais trois soirées et un certain nombre d'heures de réflexion la journée. Mais ma vengeance est terrible : ni ElJj ni aucun autre mathématicien ne passera plus jamais des heures à former les entiers de 1 à 100 en n'utilisant que les chiffres de l'année (2,0,1,2) une et une seule fois chacun, les opérations de base +,-,*,/,^ et quelques autres. Fi-ni. Et c'est rapé aussi pour toutes les années futures ou passées, parce que j'ai fait un programme qui résout ce problème une fois pour toute. Amis matheux de tous pays, je vous fais ci-dessous économiser des milliers d'heures que vous allez pouvoir utiliser pour résoudre de vrais problèmes (Pensez à moi si vous en résolvez un, merci...)

Pour être honnête, la première soirée a été grillée à péniblement trouver 50 formules, ce qui m'a à la fois décidé à faire autrement et inspiré beaucoup de respect pour ElJj et les autres fous qui sont parvenus à obtenir des scores de 4000 et quelques points à la main. Bravo !

Pour 2012, mes solutions sont donc : 

[1, '(((2*0)-1)^2)', 0]
[2, '(((2-0)-1)*2)', 0]
[3, '(((2-0)-1)+2)', 0]
[4, '(((2-0)^1)^2)', 0]
[5, '(((2-0)+1)+2)', 0]
[6, '(((2-0)+1)*2)', 0]
[7, '((2^0)+((1+2)!))', 0]
[8, '(2^(0+(1+2)))', 0]
[9, '(((2-0)+1)^2)', 0]
[10, '((((2+0!)!)-1)*2)', 0]
[11, '(((2+0!)!)+(1/.2))', 1]
[12, '((((2-0)+1)!)*2)', 0]
[13, '(2+sqrt((0!+((1/.2)!))))', 1]
[14, '((((2+0!)!)+1)*2)', 0]
[15, '(((2-0)+1)/.2)', 1]
[16, '(((2+0!)+1)^2)', 0]
[17, '(((((2+0!)!)-1)!!)+2)', 5]
[18, '(((2+0!)!)*(1+2))', 0]
[19, '((2^0)+(((1+2)!)!!!))', 5]
[20, '(((2^0)/.1)*2)', 1]
[21, '(((((2+0!)!)!!!)+1)+2)', 5]
[22, '((((2+0!)+1)!)-2)', 0]
[23, '((.2^(-(0!+1)))-2)', 1]
[24.0, '((((2-0)^1)^2)!)', 0]
[25, '((((2+0!)!)-1)^2)', 0]
[26, '((((2+0!)+1)!)+2)', 0]
[27, '((2+0!)^(1+2))', 0]
[28, '(((2+0!)/.1)-2)', 1]
[29, '(((2+0!)/[.1])+2)', 30]
[30, '((((2-0)+1)!)/.2)', 1]
[31, '(((2+0!)/.1)+(Gamma(2)))', 31]
[32, '(2^(-(0!-((1+2)!))))', 0]
[33, '((((2+0!)!)!!)-((1/.2)!!))', 11]
[34, '(sqrt((2^(0!/.1)))+2)', 1]
[35, '((((2+0!)!)+1)/.2)', 1]
[36, '((((2-0)+1)!)^2)', 0]
[37, '(0!+(((1+2)!)^2))', 50]
[38, '(((((2+0!)!)!!!)+1)*2)', 5]
[39, '(((.2^(-0!))!)-([.1]^(-2)))', 31]
[40, '(((2-0)/.1)*2)', 1]
[41, '(0!+(2/(.1/2)))', 51]
[42, '((((2+0!)!)!!)-((1+2)!))', 5]
[43, '((((2+0!)!)!!)-(1/.2))', 6]
[44, '(-((.2-(0!/[.1]))/.2))', 32]
[45, '(((((2+0!)!)!!)-1)-2)', 5]
[46, '(((((2-0)+1)!)!!)-2)', 5]
[47, '(((((2+0!)!)!!)+1)-2)', 5]
[48, '((((2+0!)+1)!)*2)', 0]
[49, '((((2+0!)!)+1)^2)', 0]
[50, '((.2^(-(0!+1)))*2)', 1]
[51, '((.2+(0!/.1))/.2)', 3]
[52, '(2+(0!/(.1*.2)))', 2]
[53, '((((2+0!)!)!!)+(1/.2))', 6]
[54, '((((2+0!)!)!!!)*(1+2))', 5]
[55, '(sqrt((((.2^(-0!))!)+1))/.2)', 2]
[56, '(((((2+0!)!)+1)!!!)*2)', 5]
[57, '((((2+0!)!)!!)+sqrt(([.1]^(-2))))', 35]
[58, '((((2+0!)!)/.1)-2)', 1]
[59, '((((2+0!)!)/.1)-(Gamma(2)))', 31]
[60, '(((((2+0!)!)-1)!)/2)', 0]
[61, '((((2+0!)!)/.1)+(Gamma(2)))', 31]
[62, '((((2+0!)!)/.1)+2)', 1]
[63, '((((2+0!)!)!!)+((1/.2)!!))', 11]
[64, '(2^((0+(1+2))!))', 0]
[65, '(0!+(2^((1+2)!)))', 50]
[66, '((((2+0!)!)!!)+(((1+2)!)!!!))', 10]
[67, '((((.2^(-0!))!!)-[.1])/[.2])', 66]
[68, '(20+(((1+2)!)!!))', 15]
[69, '((((0!+2)!)!!)+21)', 65]
[70, '(((((2+0!)!)!)*.1)-2)', 1]
[71, 'sqrt((((((2+0!)!)+1)!)+(Gamma(2))))', 30]
[72, 'sqrt((((((2+0!)!)!)*.1)^2))', 1]
[73, '(((((2+0!)!)!)*.1)+(Gamma(2)))', 31]
[74, '(((((2+0!)!)!)*.1)+2)', 1]
[75, '(((((2+0!)!)-1)!!)/.2)', 6]
[76, '(-((.2^(-0!))-([.1]^(-2))))', 31]
[77, '((((2^2)!!)!!!)-sqrt((0!/[.1])))', 90]
[78, '((((-2)+(0!/.1))!!!)-2)', 6]
[79, '(-(2-(0!/([.1]^2))))', 30]
[80, '(-((.2-0!)/(.1^2)))', 2]
[81, '((((.2^(-0!))!!!)-1)^2)', 6]
[82, '(2+(((0!/.1)-2)!!!))', 6]
[83, '(2+(0!/([.1]^2)))', 30]
[84, '((((.2^(-0!))!!!)!!!)*(.1+.2))', 13]
[85, '(((((2+0!)!)!!!)-1)/.2)', 6]
[86, '((.2^(-0!))+([.1]^(-2)))', 31]
[87, '(((2+0!)!)+([.1]^(-2)))', 30]
[88, '(-((((2+0!)!)!)*(.1-[.2])))', 31]
[89, '(-((.2-((sqrt((0!/[.1]))!)!!!))/.2))', 37]
[90, '(((((2-0)+1)!)!!!)/.2)', 6]
[91, '(((.2^(-0!))!!!)+([.1]^(-2)))', 36]
[92, '(2*(((sqrt((0!/[.1]))!)!!)-2))', 35]
[93, '93', 500]
[94, '(-(((2+0!)!)-(.1^(-2))))', 1]
[95, '(-((.2^(-0!))-(.1^(-2))))', 2]
[96, '(-((.2-0!)*((1/.2)!)))', 2]
[97, '(-(2+(0!-(.1^(-2)))))', 1]
[98, '(-(2-(0!/(.1^2))))', 1]
[99, '(-((2^0)-(.1^(-2))))', 1]
[100, '(((2^0)/.1)^2)', 1]

C'est un peu "brut de décoffrage" et mérite quelques explications. Chaque triplet comporte le nombre à obtenir, la "meilleure" formule qui le donne, et le coût de cette formule en points calculés selon les règles décrites dans l'article d'El Jj. Les formules qui utilisent les chiffres 2,0,1,2 dans l'ordre et les opérations arithmétiques de base et la factorielle (saviez-vous que 0!=1 ?) ont le coût minimum de 0. L'utilisation du point décimal bien utile avec une division ne coute qu'un point. Les formules qui utilisent des opérateurs plus compliqués comme les multifactorielles (notées !! et !!!) et la fonction gamma sont pénalisées de 5 points.

La formule pour 77 est la plus coûteuse (90 points) car elle utilise les chiffres dans le désordre (50 points), le développements décimal périodique [.1] = 0.11111111... = 1/9 qui vaut 30 points chacun, plus deux multifactorielles. A noter que l'on a eu besoin d'inverser l'ordre des chiffres que dans 4 cas seulement.

Et enfin, les nombre pour lesquels on ne trouve pas de solution sont pénalisés de 500 points, ce qui n'est le cas pour 93, pour lesquel je suis quasi certain qu'il n'existe pas de solution avec les opérations autorisées. Mais seulement "quasi", pour des raisons que j'explique plus loin.

Le total des pénalités que j'obtiens est de 1637 points

Enfin, les formules ne sont pas très jolies d'une part à cause d'une "surparenthésation" qui simplifie l'écriture du programme (pas besoin de gérer la précédence des opérateurs), et d'autre part car le choix de la "meilleure" formule lorsqu'on en trouve plusieurs de score égal se fait par la longueur de la chaîne, sans tenir compte de l'ordre d'insertion ou de la priorité des opérateurs. Donc (((2*0)-1)^2) peut paraître plus compliqué que (((2*0)-1)+2) pour obtenir 1, mais pour une machine, c'est le même prix.

Comme il se fait tard je coupe/colle le programme ci-dessous, je le commenterai plus tard (comme d'hab...)

# -*- coding: utf-8 -*-
"""
Created on Mon Jan 16 17:19:27 2012

@author: Philippe Guglielmetti
solves

http://eljjdx.canalblog.com/archives/2012/01/15/23243094.html

"""

import sys

from math import sqrt,pow
from scipy import factorial,factorial2,factorialk
from itertools import permutations

class f:
    """a formula"""
    def __init__(self, m,p=0,v=None,parenthesis=False):
        #print m,'=',
        self.isdigit=isinstance(m, (int, long))
        self.math=str(m) #convert to string in case it's a digit
        self.points=p
        if v is None:
            v=eval(self.math)
        self.isint=isinstance(v, (int,long))
        if isinstance(v, float): #try to convert to int
            self.isint=abs(v-round(v))<1e-9
            if self.isint:
                v=int(round(v))
        if isinstance(v, long): #we don't want bignums, for performance
            if abs(v)<sys.float_info.max:
                v=float(v)
            self.isint=True
        self.value=v

        if parenthesis:
            self.math='('+self.math+')'
        #print self.value

    def __cmp__(self,other):
        if self.value<other.value:return -1
        if self.value>other.value:return +1
        if self.points<other.points:return -1
        if self.points>other.points:return +1
        if len(self.math)<len(other.math):return -1
        if len(self.math)>len(other.math):return +1
        return 0

    def __repr__(self):
        return str([self.value,self.math,self.points]);

class results(dict):
    """dictionary of formulas indexed by their result. we keep only the simplest entry for each result"""

    def __init__(self):
        dict.__init__(self)

    def add(self, f):
        if f.value in self.keys() and f>self[f.value] :
            pass
        else:
            self[f.value]=f

    def merge(self,d):
        for i in d.itervalues():
            self.add(i)

    def score(self):
        return sum(map(lambda x: x.points,self.itervalues()))

    def notfound(self,p=500):
        return [i for (i,v) in self.iteritems() if v.points>=p]

    def refine(self,recurse=2):
        """add combinations of monadic operators"""
        r=results()
        for a in self.itervalues():
            if recurse==0 and a.value<>0:
                r.add(f('-'+a.math,a.points,-a.value,True))
            if a.isint:
                if a.value==0:
                    r.add(f(a.math+'!',a.points,1)) # 0! == 1 is very useful...
                if a.value>1:
                    s=f('sqrt('+a.math+")",a.points,sqrt(a.value))
                    if s.isint:
                        r.add(s)
                if a.value>1 and a.value<19:
                    r.add(f(a.math+'!',a.points,factorial(int(a.value),True),True))
                    r.add(f('Gamma('+a.math+')',a.points+30,factorial(int(a.value)-1,True),True))
                if a.value>3 and a.value<29:
                    r.add(f(a.math+'!!',a.points+5,factorial2(int(a.value),True),True))
                if a.value>4 and a.value<39:
                    r.add(f(a.math+'!!!',a.points+5,factorialk(int(a.value),3,True),True))
        self.merge(r)
        if recurse>0: self.refine(recurse-1)

class monadic(results):
    """combinations of monadic operators around a formula"""

    def __init__(self, a):
        results.__init__(self)
        self.add(a)
        if a.value!=0:
            if a.isdigit:
                self.add(f('.'+a.math,a.points+1))
            if a.value<10:
                self.add(f('[.'+a.math+']',a.points+30,a.value/9.))
        self.refine();

class diadic(results):
    """combinations of diadic operators of 2 operands"""

    def __init__(self, a,b):
        results.__init__(self)
        for i in a.itervalues():
            for j in b.itervalues():
                if i.isdigit and j.isdigit:
                    if i.value!=0: self.add(f(int(i.math+j.math),10))
                    self.add(f(i.math+'.'+j.math,11))
                self.add(f(i.math+'+'+j.math,i.points+j.points,i.value+j.value,True))
                self.add(f(i.math+'-'+j.math,i.points+j.points,i.value-j.value,True))
                self.add(f(i.math+'*'+j.math,i.points+j.points,i.value*j.value,True))
                if j.value!=0:
                    self.add(f(i.math+'/'+j.math,i.points+j.points,float(i.value)/float(j.value),True))
                try: #so many things can go wrong with next line...
                    self.add(f(i.math+'^'+j.math,i.points+j.points,pow(i.value,j.value),True))
                except:
                    pass
                if i.isint:
                    try: #so many things can go wrong with next line...
                        self.add(f('root('+i.math+','+j.math+')',i.points+j.points+5,pow(j.value,1./i.value),True))
                    except:
                        pass
                if i.isint and j.isint and i.value>=0 and j.value>0 and i.value/j.value<10:
                    try: #so many things can go wrong with next line...
                        self.add(f(i.math+'!'+j.math,i.points+j.points+5,factorialk(i.value,j.value),True))
                    except:
                        pass

        self.refine();

print 'building list of monadics'
m=map(monadic,map(f,range(0,10))) #list of all monadics of digits

#use @Memoized here to improve performance
def d(a,b): return diadic(a,b)

def year(n,display=True,verbose=True):
    solution=results()
    for i in range(1,101):
        solution.add(f(i,500))

    def addresults(a,p):
        if verbose :
            print 'formulas',len(a),
        improved=0
        found=0
        for (i,v) in a.items():
            if isinstance(i, (int, long)) and i>0 and i<101:
                v.points+=p
                if v<solution[i]:
                    if solution[i].points==500:
                        found+=1
                    else:
                        improved+=1
                    solution[i]=v
        if verbose:
            print('found :'+str(found)+' improved :'+str(improved)+' score:'+str(solution.score()))

    def combine (a,p):
        m0=m[a[0]]; m1=m[a[1]]; m2=m[a[2]]; m3=m[a[3]]
        if solution.notfound():addresults(d(d(d(m0,m1),m2),m3),p)
        if solution.notfound():addresults(d(d(m0,d(m1,m2)),m3),p)
        if solution.notfound():addresults(d(m0,d(m1,d(m2,m3))),p)
        if solution.notfound():addresults(d(m0,d(d(m1,m2),m3)),p)
        if solution.notfound():addresults(d(d(m0,m1),d(m2,m3)),p)

    y=[int(i) for i in str(n)]
    combine(y,0)
    y.sort()
    for i in permutations(y):
        combine(i,50)

    if display:
        for i in solution.itervalues():print i
    print n,solution.score(),solution.notfound()

year(2012)
Comment | , , , . permalink.
  • http://sciencetonnante.wordpress.com/ Science Etonnante

    Respect ! Vraiment…

    Ca illustre complètement cette définition : « un bon mathématicien appliqué, c’est quelqu’un qui peut battre le champion du monde d’échecs et le champion du monde de boxe. Le premier à la boxe, le deuxième aux échecs »

    Belle démonstration de boxe « pythonesque » :-)

    Bon alors pour corser le truc : quelle est l’année du XXIè siècle pour laquelle le score minimal atteignable est maximal ? (en gros où il y a le plus grand nombre de « nombre impossibles »)

    • http://drgoulu.com Dr. Goulu

      J’ai commencé à attaquer ta question et obtenu assez rapidement ça:

      2000 27021 [31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 82, 83, 84, 85, 86, 87, 88, 89, 91, 92, 93, 94, 95, 97, 98, 99]
      2001 8198 [41, 52, 67, 69, 74, 76, 77, 84, 86, 87, 92, 93]
      2002 7356 [52, 67, 69, 73, 77, 83, 84, 86, 87, 88, 92, 93]
      2003 752 []
      2004 762 []
      2005 2019 [67, 87]
      2006 1439 [77]
      2007 1218 []
      2008 2180 [67, 93]
      2009 699 []
      2010 7889 [41, 52, 67, 69, 74, 76, 77, 84, 86, 87, 92, 93]
      2011 4329 [67, 76, 77, 86, 93]
      2012 1886 [93]
      2013 449 []
      2014 504 []

      ce sont les années avec les scores et les nombres qu’on arrive pas à trouver correspondants. Et puis mon programme patine à partir de 2013, ça prend un temps fou… Parce que:

      1) il y a plus de permutations possibles puisqu’il y a 4 chiffres différents
      2) avec des nombres plus grands que 0 et 1, le nombre de résultats distincts obtenus en empilant des opérateurs monadiques explose

      Donc il va falloir que je m’attaque une fois de plus à l’ennemi no 1 dans ce type de programmes : l’explosion combinatoire. 4ème soirée en perspective … Merci David :-/ (bon c’est vrai que j’aurais du vérifier avant d’écrire : « Et c’est rapé aussi pour toutes les années futures ou passées » …)

      • http://drgoulu.com Dr. Goulu

        Bon, j’ai un peu corrigé et optimisé le soft, mais c’est malgré tout très lent pour les années ayant 4 chiffres distincts, pour lesquelles on arrive par ailleurs à trouver tous les nombres de multiples manières:

        2000 27021 [31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 82, 83, 84, 85, 86, 87, 88, 89, 91, 92, 93, 94, 95, 97, 98, 99]
        2001 8198 [41, 52, 67, 69, 74, 76, 77, 84, 86, 87, 92, 93]
        2002 7356 [52, 67, 69, 73, 77, 83, 84, 86, 87, 88, 92, 93]
        2003 752 []
        2004 762 []
        2005 2019 [67, 87]
        2006 1439 [77]
        2007 1218 []
        2008 2180 [67, 93]
        2009 699 []
        2010 7889 [41, 52, 67, 69, 74, 76, 77, 84, 86, 87, 92, 93]
        2011 4329 [67, 76, 77, 86, 93]
        2012 1886 [93]
        2013 449 []
        2014 504 []
        2015 598 []
        2016 659 []
        2017 371 []
        2018 642 []
        2019 337 []
        2020 6850 [52, 67, 69, 73, 77, 83, 84, 86, 87, 88, 92, 93]
        2021 1465 [93]
        2022 2647 [67, 84, 87, 93]
        2023 321 []
        2024 291 []
        2025 245 []
        2026 432 []
        2027 330 []
        2028 514 []
        2029 202 []
        2030 684 []
        2031 415 []
        2032 308 []

        à 2033 il y a eu un crash… j’investigue…

  • http://drgoulu.com Dr. Goulu

    Aïe aïe aïe : le soft avait une grossière erreur qui faisait qu’il n’explorait que les permutations des chiffres 2,0,1,2 qui commençaient par 2. En effet, la fonction itertools.permutations fonctionne comme un itérateur : elle revoie la « prochaine » permutation calculée à partir de celle passée en paramètre, et elle ne génère donc toutes les permutations que si son paramètre est préalablement trié.

    Après correction, non seulement le score s’abaisse à 1900 points seulement, mais on trouve même une formule pour le nombre supposé inatteignable 67.

    En réalité j’ai trouvé ce bug en cherchant tous les résultats du siècle selon la question de David (Science Etonnante), où je me suis aperçu que le temps de calcul variait beaucoup d’une année à l’autre…

  • Bref

    Chapeau bas l’ami! Pourquoi la résolution de ce problème ne m’étonne pas de toi. Peut-être parce que j’ai travaillé avec toi et que j’ai pu constater tes talents pour ce genre de défis.

    Respect.
    @+

    • http://drgoulu.com Dr. Goulu

      Merci pour les fleurs, Bref ;-) Mais tu vois, j’ai toujours autant de peine à utiliser des identificateurs parlants et documenter mon code … on faisait une bonne équipe :-D

  • http://blog.neamar.fr Neamar

    Waouh.

    Vraiment, du bon boulot. Je suis toujours aussi impressionné par ton investissement sans concession !

  • http://eljjdx.canalblog.com El Jj

    32 = 2^(-0!+(1+2)!) [0 points]

    Ah ah, supériorité de l’homme sur la machine !
    Bon, quand je vois certaines solutions, je suis admiratif ! Avoir pensé à .[1]^(-2) pour faire 81, c’est vraiment très fort !
    J’ai par contre un soucis avec 88, je comprends pas ce que signifie (22!((sqrt((0!/[.1]))!)!!!)) . Surtout que le score ne correspond pas du tout.

    • http://drgoulu.com Dr. Goulu

      Pour 32 il doit effectivement encore y avoir une bulle dans le programme, il aurait du trouver la solution à 0 points…

      Pour le 88 par contre j’ai vérifié : 22!18 = 22*4, la 18-ème factorielle de 22 :-)
      En effet (sqrt(9)!)!!! = 6!!! = 6*3 = 18

      Celle là, pour la trouver à la main …

      Mon programme est très flatté que tu aies utilisé le verbe « penser » à propos de lui. Moi j’ai juste programmé une exploration d’arbre… :-)

      • http://eljjdx.canalblog.com El Jj

        Ah oui, j’avais pas vu que c’était une factorielle multiple. Cela dit, les chiffres ne sont pas dans l’ordre, il y a deux multifactorielles et un développement décimal périodique, donc ça fait plutôt 50+5+5+30=90 points ! A ce prix là, je préfère 88=(2/.2+0!)!!!*.1

        • http://drgoulu.com Dr. Goulu

          Exact… y’a encore une bulle dans mon prog, il trouve pas des trucs qu’il devrait trouver … Je pense que c’est au niveau du comptage des points, je vais chercher…

  • Zoid

    Bien joué pour le 67 mais ça fait beaucoup de points quand même !
    67 = ((((0!/.2)!!)-[.1])/[.2]) ->> 116 pts

    Ya moins cher :
    67 = (((.2^(-0!))!!)-[.1])/[.2]) ->> 61 pts !

    Pareil pour 88 d’ailleurs, perso j’avais 88 = (.2^(-0!))!!!/.[1]-2 soit 36 pts (au lieu de 100!).

    • Zoid

      Oups erreur en comptant ! 67 = (((.2^(-0!))!!)-[.1])/[.2]) ->> 66 pts !

      • http://drgoulu.com Dr. Goulu

        Bravo Zoid, tu as raison… Il y avait (encore) une bulle dans mon soft, qui n’arrivait bêtement pas à utiliser le – monadique, donc pas à faire le -0! en particulier… J’ai corrigé et il trouve ta formule pour 67, et une encore meilleure pour 88 = (-((((2+0!)!)!)*(.1-[.2]))) , 31 points seulement..
        J’ai mis à jour ma solution, et j’obtiens désormais 1637 points seulement pour 2012

  • http://drgoulu.com Dr. Goulu

    Dans « Bricoles, babioles… et surprises numériques !« , Pour la Science – n° 373 – Novembre 2008, Jean-Paul Delahaye avait parlé d’un problème similaire au « jeu de l’année », les Nombres de Friedman, dont on trouve une liste ici. Je vais dresser mon Python pour qu’il les trouve aussi…

  • http://drgoulu.com Dr. Goulu

    Bon, voilà-t-y pas qu’Alexandre Moatti remet ça sous une autre forme : avec la « formule de Cartier » il s’agit de générer des nombres avec les chiffres 1,2,3,4,5 dans l’ordre… Quelques p’tites modifs de mon soft plus tard je lui ai posté ce commentaire:

    Bon, alors je m’y suis mis, mais en trichant, comme je l’avais fait pour ce problème très similaire :

    Voici pour commencer tous les entiers positifs inférieurs à 10000 que j’arrive à faire avec 1,2,3 dans l’ordre et les opérations +,-,*,/,^,! et !! : [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 23, 24, 25, 27, 36, 42, 45, 46, 47, 48, 49, 50, 51, 54, 63, 64, 65, 95, 96, 97, 119, 120, 121, 144, 216, 240, 288, 360, 383, 384, 385, 672, 714, 717, 718, 719, 720, 721, 722, 723, 726, 729, 768, 1439, 1440, 1441, 2160, 2304, 4320] notez l’absence du 10 …

    en ajoutant le 4, on arrive à faire 693 entiers sur 10’000. Le premier entier irréalisable (?) est le 76, et la prochaine année réalisable est

    2016 = ((1+2)!)!+(3!)^4

    Note : J’ai utilisé WolframAlpha pour vérifier mes formules et éliminer des parenthèses surnuméraires générées par mon soft.

    En ajoutant le 5, Python frise l’apoplexie combinatoire, mais j’arrive à produire presque tous les entiers de 1 à 10000. Le premier manquant est 538. Mais 2012 manque aussi à l’appel. Mais je vous offre les 4 prochaines années :

    • 2013 = -1-(2-3!*(4!!)!/5!)
      2014 = -1*(2-3!*(4!!)!/5!)
      2015 = -1+2*(3+4)!/5
      2016 = 1*(2^3)!/(4*5)
  • Si je torpille votre enthousiasme, sachez que mon programme trouve 2 autres solutions assez différentes pour 2015 et 2016, que je laisse à votre sagacité :-)