Une autre manière de classer les nombres

[nodgim]

Bonsoir à tous.
Dans la série "accessible à tous", une autre petite enigme gentille.
Le jeune Harry temetik décide de lister les entiers naturels de cette manière: Du plus petit au plus grand, sauf que dès qu'il écrit un nombre, il écrit aussitôt, du plus petit au plus grand, tous les nombres composés des mêmes chiffres. Par exemple, s'il écrit 123, il va écrire à la suite: 123, 132,213, 231, 312 et 321. Bien entendu, dans sa liste les nombres n'apparaissent qu'une seule fois.
S'il commence à 1, quel sera le rang du nombre 9455 ?
Nota: aucun nombre ne s'écrit en commençant par 0. 10, par exemple, est donc le premier nombre de 2 chiffres, tout comme 100 le premier de 3 chiffres.

Bon amusement; :id:

[Sve@r]

Bonsoir à tous.
Dans la série "accessible à tous", une autre petite enigme gentille.
Le jeune Harry temetik décide de lister les entiers naturels de cette manière: Du plus petit au plus grand, sauf que dès qu'il écrit un nombre, il écrit aussitôt, du plus petit au plus grand, tous les nombres composés des mêmes chiffres. Par exemple, s'il écrit 123, il va écrire à la suite: 123, 132,213, 231, 312 et 321. Bien entendu, dans sa liste les nombres n'apparaissent qu'une seule fois.
S'il commence à 1, quel sera le rang du nombre 9455 ?
Nota: aucun nombre ne s'écrit en commençant par 0. 10, par exemple, est donc le premier nombre de 2 chiffres, tout comme 100 le premier de 3 chiffres.

Bon amusement; :id:

Si j'ai bien compris, imaginons qu'il arrive au nombre 123 il le classera alors de cette façon: 123; 132; 213; 231; 312; 321
Ensuite il passe ay suivant 124 donc la suite devient 123; 132; 213; 231; 312; 321; 124, 142; 214; 241; 412; 421 (avec 124 placé après 321) ?

Et ensuite aucun des nombres déjà classés ne sera réutilisé donc il finit 131, il passe alors à 133 puisque 132 a déjà été pris ?

C'est bien ça ???

[nodgim]

Si j'ai bien compris, imaginons qu'il arrive au nombre 123 il le classera alors de cette façon: 123; 132; 213; 231; 312; 321
Ensuite il passe ay suivant 124 donc la suite devient 123; 132; 213; 231; 312; 321; 124, 142; 214; 241; 412; 421 (avec 124 placé après 321) ?

Et ensuite aucun des nombres déjà classés ne sera réutilisé donc il finit 131, il passe alors à 133 puisque 132 a déjà été pris ?

C'est bien ça ???

Oui c'est bien cela :id:
Mais 131 arrivera juste après 113. C'est à dire on écrira 113, puis 131 puis 311, puis 114,...

[Sve@r]

Bon ben j'ai pas résisté, j'ai carrément fait le bourrin et écrit un programme Python qui me calcule ça. J'aurais pu l'écrire en C ou C++ mais Python est à la fois souple, puissant, portable et assez connu du monde de la programmation...

Pour ceux que ça intéresse, voici le code source

Code: Tout sélectionner

#!/usr/bin/env python
# coding: Latin-1 -*-

import sys

# Fonction d'évaluation du nombre reçu
def evaluate(
      n):                           # Nombre reçu

   # Initialisation tableau nouveaux nombres
   tab=[]

   # Traitement de tous les anagrammes du nombre
   for elem in anag(n):
      # Si l'élément commence par '0' on le passe
      if elem[0] == '0': continue

      # Le tableau reçoit l'anagramme converti en nombre
      tab.append(int(elem))

   # Le tableau est trié
   tab.sort()

   # Renvoi tableau nouveaux nombres
   return tab
# evaluate()

# Fonction de base d'anagramme
def anag(
      nb):                        # Nombre à anagrammer

   # Fonction d'anagramme (récursive)
   def __anag(
         base,                     # Chaîne de base
         sub):                     # Sous-chaîne à permuter

      # Si la sous-chaîne est la dernière
      if len(sub) == 1:
         # Fin de récursivité - On renvoie un tableau contenant la base et le dernier caractère
         return ["%s" % (base + sub)]

      # Initialisation tableau résultat
      tab=[]

      # Boucle sur chaque caractère de la sous-chaîne
      for i in range(len(sub)):
         # Appel récursivité avec base augmentée et sous-chaîne réduite du caractère en question
         tab+=__anag(base + sub[i], sub[0:i] + sub[i + 1:])

      # On renvoie le tableau résultat
      return tab
   # __anag()

   # Renvoi du tableau donné par la fonction récursive
   return __anag("", str(nb))
# anag()

# Appel principal
if __name__== "__main__": 
   # Vérification au-moins un argument
   if len(sys.argv) <= 1:
      print "usage: %s nb" % sys.argv[0]
      sys.exit(1)
   
   # Initialisation
   tab=[]
   i=0
   but=int(sys.argv[1])

   # Tant que nombre cherché pas atteint
   while but not in tab:
      # On incrémente l'indice
      i+=1

      # Si l'indice est déjà dans la liste des nombres on le passe
      if i in tab: continue

      # Traitement de chaque nombre ressorti de l'évaluation
      for n in evaluate(i):

         # Si le nombre n'est pas déjà stocké dans le tableau
         if n not in tab:
            tab.append(n)

   # Affichage du tableau et de la position du but
   print "%s (%d)" % (tab, tab.index(but) + 1)


Et ce programme qui n'est finalement pas vraiment long à écrire et qui fonctionne aussi sous Windows (juste à télécharger et installer l'interpréteur Python) m'a sorti que 9455 se trouvait en position 8469.

Arf j'ai conscience que c'était pas vraiment le but initial. Cependant, j'ai quand-même constaté que les nombres 10; 100 et 1000 se trouvaient en 10°; 100° et 1000° place. Normal, chacun d'eux marque une nouvelle étape pour laquelle tous les nombres de l'étape précédente ont été utilisés. Mais je ne suis pas allé plus loin...

[emcee]

bonjour,

moins bourin (quoi que ?) je dirais aussi 8469 - je raisonne ainsi :

- j'appelle classe d'un nombre l'ensemble des nombres formés par permutation de ses chiffres. Par exemple la classe de 123 est {123,132,213,231,312,321}. Harry classe les nombres en respectant ces classes.
- j'appelle représentant d'une classe le minimum de cette classe.
- 9455 dans la classe de 4559.
- donc il est dans l'ordre d'Harry avant tous les nombres composé exclusivement de 5, de 6, de 7, de 8, de 9 ou de 0 non initial. Or ces nombres sont 1080 (5*6*6*6).
- ensuite, 9455 est avant tout nombre comportant un seul 4 et dont les 3 autres chiffres sont exclusivement des 6, 7, 8 ou 9 : ceux ci sont 4*(4^3) = 256.
- à reculons, je connais donc l'ordre de classement du nombre 4666 : il est (10.000 - 1.080 - 256) = 8664e.
- reste à connaître les classes ordonnées entre celle de 4559 et celle de 4666 : pour cela je regarde tous les nombres compris entre ces deux-là et je regarde si leur représentant de classe est < ou > à 4559 :
(je note que si ne nombre comporte un 0, 1, 2, 3, 4 outre le 1er '4', je le zappe car il est nécessairement ordonné avant 4559 ...)
4665 : classe de 4566
4659 : classe de 4569
4658 : classe de 4568
4657 : classe de 4567
4656 : classe de 4566
4599 : classe de 4599
4598 : classe de 4589
4597 : classe de 4579
4596 : classe de 4569
4589 : classe de 4589
4588 : classe de 4588
4587 : classe de 4578
4586 : classe de 4568
4579 : classe de 4579
4578 : classe de 4578
4577 : classe de 4577
4576 : classe de 4567
4569 : classe de 4569
4568 : classe de 4568
4567 : classe de 4567
4566 : classe de 4566
Il y a donc 10 classes concernées : 4599, 4589, 4588, 4579, 4578, 4577, 4569, 4568, 4567, 4566, comptant au total 4*12+6*24=192 représentants.
- j'en suis donc à dire que "4566" est ordonné 8664-192 = 8472e
- et juste avant on a la classe de 4559, qui à reculons donne 9554,9545,9455,etc : donc 9455 est 8469e...


Question subsidiaire : Harry a défini en fait une permutation s, on a s(1)=1, ... s(12)=12 mais s(13)=14 car s(21)=13, etc.
Combien y a-t-il de n tels que s(n)=n ? on a déjà tous les nombres de 1 à 12, ainsi que 100, 101, 1000, 1001 ...

[Sve@r]

bonjour,

moins bourin (quoi que ?) je dirais aussi 8469 - je raisonne ainsi :

- j'appelle classe d'un nombre l'ensemble des nombres formés par permutation de ses chiffres. Par exemple la classe de 123 est {123,132,213,231,312,321}. Harry classe les nombres en respectant ces classes.
- j'appelle représentant d'une classe le minimum de cette classe.
- 9455 dans la classe de 4559.
- donc il est dans l'ordre d'Harry avant tous les nombres composé exclusivement de 5, de 6, de 7, de 8, de 9 ou de 0 non initial. Or ces nombres sont 1080 (5*6*6*6).
- ensuite, 9455 est avant tout nombre comportant un seul 4 et dont les 3 autres chiffres sont exclusivement des 6, 7, 8 ou 9 : ceux ci sont 4*(4^3) = 256.
- à reculons, je connais donc l'ordre de classement du nombre 4666 : il est (10.000 - 1.080 - 256) = 8664e.
- reste à connaître les classes ordonnées entre celle de 4559 et celle de 4666 : pour cela je regarde tous les nombres compris entre ces deux-là et je regarde si leur représentant de classe est à 4559 :
(je note que si ne nombre comporte un 0, 1, 2, 3, 4 outre le 1er '4', je le zappe car il est nécessairement ordonné avant 4559 ...)
4665 : classe de 4566
4659 : classe de 4569
4658 : classe de 4568
4657 : classe de 4567
4656 : classe de 4566
4599 : classe de 4599
4598 : classe de 4589
4597 : classe de 4579
4596 : classe de 4569
4589 : classe de 4589
4588 : classe de 4588
4587 : classe de 4578
4586 : classe de 4568
4579 : classe de 4579
4578 : classe de 4578
4577 : classe de 4577
4576 : classe de 4567
4569 : classe de 4569
4568 : classe de 4568
4567 : classe de 4567
4566 : classe de 4566
Il y a donc 10 classes concernées : 4599, 4589, 4588, 4579, 4578, 4577, 4569, 4568, 4567, 4566, comptant au total 4*12+6*24=192 représentants.
- j'en suis donc à dire que "4566" est ordonné 8664-192 = 8472e
- et juste avant on a la classe de 4559, qui à reculons donne 9554,9545,9455,etc : donc 9455 est 8469e...

Joli travail mais énormément de réflexion !!!

Question subsidiaire : Harry a défini en fait une permutation s, on a s(1)=1, ... s(12)=12 mais s(13)=14 car s(21)=13, etc.
Combien y a-t-il de n tels que s(n)=n ? on a déjà tous les nombres de 1 à 12, ainsi que 100, 101, 1000, 1001 ...

Ben une infinité !!! 1000; 1001; 10000; 10001; ... mais si la question est "combien y a-t-il de n compris entre 1 et 9455 tels que s(n)=n, alors il suffira de modifier mon programme et le terminer ainsi:

Code: Tout sélectionner

   # Affichage du tableau et de la position du but
   print "%s (%d)" % (tab, tab.index(but) + 1)

   # Compteurs de n tels que s(n)=n
   iso=[]
   for (i, n) in enumerate(tab):
      if (i + 1) == n:
         iso.append(n)
   print iso

Et ça me donne en final (entre 1 et 9455) 24 nombres tels que s(n)=n qui sont de 1 à 12 + 75; 99; 100; 101; 999; 1000; 1001; 1507; 2152; 2516; 6299 et 7736

[nodgim]

Bravo pour votre travail à tous les deux! :id:

[emcee]

bonjour,
je reste sur mes n tels que s(n) = n : pour les nombres de 1 à 12 et les 10^i et 10^i + 1, pas de surprises. Ce qui est plus intéressant c'est de constater que de temps à autre on en a un autre qui sort, comme 75 ou 2152 !!!

je baptise ces nombres les Nombres de Nodgim, en hommage au posteur initial ;-) Un mathématicien du futur trouvera bien à quoi ils servent !