Curiosité arithmétique

J’ai depuis longtemps ce petit sujet en tête (lu dans les récréation mathématiques du Scientific American - Martin Gardner) … et je dois reconnaître que je ne sais pas si il a été exploré et résolu. Il se présente comme suit:

Choisir 4 chiffres non tous identiques.

1. Former avec ces 4 chiffres le nombre le plus grand (G) et le plus petit (p)

2. Faire la soustraction G-p

Retourner en 1.

Exemple: partons du quadruplet 2,3,2,6

En effectuant les opérations décrites on trouvera les nombres suivants: 6322-2236=4086, puis: 8172, 7443, 3996, 6264, 4176 … et là on voit que

7641-1476= 6174 point de convergence de l’algorithme.

La convergence est plus ou moins rapide selon le quadruplet de départ (si vous partez de 7614, elle est immédiate) …

Question 1 : Sait-on démontrer que l’algorithme converge ?

Question 2 : Est-ce que ça marche avec un doublet au départ … pas vraiment, je crois que l’on retombe toujours sur (0,9) …

Question 3: Est-ce que ça marche avec un triplet ? Oui mais il y a, je crois, plusieurs point de convergence: (4,9,5), (n,p,q)....

Question 5: peut-on généraliser à tout n-uplet ?

Avez-vous connaissance de cette curiosité ? Savez-vous répondre aux questions qu’elle entraîne ?

Merci de vos réponses

Cordialement Erick, Paris

Quand un problème est trop compliqué, on le simplifie. Je me suis demandé si ça marchait dans d’autre base (c’est-à-dire 4, 7, 16 ou 2 chiffres). Bonne nouvelle : la base 2 est faisable à la main :

(Cas 1) 0 0 0 1 donne 1000 - 0001 = 0111 -> voir cas 3
(Cas 2) 0 0 1 1 donne 1100 - 0011 = 1001 -> voir cas 2 (point fixe)
(Cas 3) 0 1 1 1 donne 1110 - 0111 = 0001 -> voir cas 1 (cycle)

Sauf erreur de calcul, avec 4 chiffres en base 2, ça ne marche pas. Ça ne résout pas le problème, mais ça me fait personnellement penser que ce n’est pas sûr que ce soit vrai, ou facilement généralisable.

Quelqu’un pour créer un script qui test tous les cas possibles (il n’y en a pas tant que ça – pour un ordi, j’entends) ?

Avant de montrer convergence vers une certaine valeur, est-ce qu’on peut trouver des cycles (i.e. une suite finie de nombres qui se répète) ? d’autres valeurs de convergences ?

Je viens de faire les 12 cas en base 3 (je n’irai pas plus loin), et je trouve que tous les cas convergent vers 2110 ou 2211, qui bouclent entre eux.

J’abonde donc dans le sens d’Holomos : est-ce qu’on peut trouver des cycles ?

Merci de vous pencher sur ce petit sujet.

En fait avec un triplet en base 10, on se rend compte que dès que l’on arrive à un triplet du type (9,n,3) on aboutit au "point de convergence" (9,5,4) … bof!

Salut, Je viens de faire à l’arrache un programme en C++, pour voir un peu comment ça marche. Bon le programme est dégueu mais il marche. Vous pouvez le tester ici : cpp.sh/2xv4c Au début, le programme demande $n$, en suite vous entrez vos $n$ chiffres et il vous affichera votre convergence.

Note : si le programme n’affiche rien c’est que le point de convergence est $0$ et $n > 1$

EDIT : et pour $n = 5$ j’ai l’impression qu’il y un cycle, pour quasiment tous les $5$ uplets entrés reEDIT : et en faisant des test pour $n \geq 5$, on peut dire que l’on a toujours des cycles ou une convergence de $0$

@Thinking : Ton lien pointe vers la mauvaise page, il faut sûrement ajouter un http.

Voilà un script python pour afficher les longueurs des cycles.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import itertools

def get_cycles(b,N):
  def next(z):
    xs = sorted(z)
    ys = reversed(xs)
    ans=[]
    r=0
    for x,y in zip(xs,ys):
      x -= r
      r = 0
      if y>x:
        r = 1
        x += b
      x -= y
      ans.append(x)
    return tuple(ans)

  seen = set()
  cycles = []

  def explore(n):
    nonlocal seen,cycles
    path = {}
    k = 0
    while not n in seen:
      seen.add(n)
      path[n] = k
      k += 1
      n = next(n)
    if n in path:
      cycles.add(k-path[n])

  nodes = itertools.product(range(b), repeat=N)
  for n in nodes:
    explore(n)

  return cycles

for b,N in itertools.product(range(5,12), range(3,6)):
  print("Base", b, "et", N, "chiffres.")
  print(get_cycles(b,N))

La sortie.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

Base 5 et 3 chiffres.
[1, 2]
Base 5 et 4 chiffres.
[1, 1]
Base 5 et 5 chiffres.
[1, 4]
Base 6 et 3 chiffres.
[1, 1]
Base 6 et 4 chiffres.
[1, 6]
Base 6 et 5 chiffres.
[1, 1, 2]
Base 7 et 3 chiffres.
[1, 2]
Base 7 et 4 chiffres.
[1, 3]
Base 7 et 5 chiffres.
[1, 5]
Base 8 et 3 chiffres.
[1, 1]
Base 8 et 4 chiffres.
[1, 5, 3]
Base 8 et 5 chiffres.
[1, 4, 2]
Base 9 et 3 chiffres.
[1, 2]
Base 9 et 4 chiffres.
[1, 3, 3]
Base 9 et 5 chiffres.
[1, 5, 1]
Base 10 et 3 chiffres.
[1, 1]
Base 10 et 4 chiffres.
[1, 1]
Base 10 et 5 chiffres.
[1, 4, 2, 4]
Base 11 et 3 chiffres.
[1, 2]
Base 11 et 4 chiffres.
[1, 5, 5]
Base 11 et 5 chiffres.
[1, 4]

Ça fonctionne en base 10 pour 3 chiffres. Mais bon, je ne suis pas sûr qu’il y ait quelque chose à expliquer.

(edit : Finalement afficher uniquement les longueurs est plus clair.)

@blo yhg : je suis pas sûr de comprendre ce que ton programme fait exactement. J’ai codé un truc similaire en Haskell (pas efficace du tout vu que la génération des nombres dans allGardnerN est faite comme un sagouin) qui affiche la longueur des cycles pour la base dix (pour un nombre de chiffres donné).

Pour 5 chiffres, j’ai beaucoup plus de cycles de longueur 4 ou 2, du coup j’ai du mal à comprendre pourquoi ton programme affiche spécifiquement [1, 4, 2, 4]… À moins que ce ne sont que les cycles différents et rien à voir avec le nombre de nombres qui finissent sur un de ces cycles ?

Chose amusante, avec 6 chiffres, il y a presque que convergence vers des cycles de 7 (et 382 nombres qui arrivent sur un cycle de 1).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import Data.Char (digitToInt)
import Data.List (sort,elemIndex,nub)
import Data.Maybe (fromMaybe,fromJust)
import Control.Monad (liftM)

fldHelper :: Int -> Int -> Int
fldHelper a b = a+10*b

type Gardner = Maybe [Int]
type Ndigits = Int
type CycleLength = Int

toGardnerN :: Ndigits -> Int -> Gardner
toGardnerN n x
    |(n<=0) = Nothing
    |(x<=0 || x>=10^n) = Nothing
    |(rem x ones==0) = Nothing
    |otherwise = Just $ sort $ take n $ (map digitToInt $ show x) ++ repeat 0
        where ones = foldr1 fldHelper $ replicate n 1

smallerFromGardner :: Gardner -> Maybe Int
smallerFromGardner = liftM $ foldl1 $ flip fldHelper

biggerFromGardner :: Gardner -> Maybe Int
biggerFromGardner = liftM $ foldr1 fldHelper

step :: Gardner -> Gardner
step x = toGardnerN n =<< diff
    where diff = (-) <$> (biggerFromGardner x) <*> (smallerFromGardner x)
          n = length $ fromMaybe [] x

seqGardner :: Gardner -> [Gardner]
seqGardner = reverse . head . dropWhile unq . scanl (flip (:)) [] . iterate step
    where unq [] = True
          unq (x:xs) = not $ x `elem` xs

lenCycle :: Gardner -> CycleLength
lenCycle x = (-) (length sqg - 1) $ fromJust $ elemIndex (last sqg) sqg
    where sqg = seqGardner x

allGardnerN :: Ndigits -> [Gardner]
allGardnerN n = nub . filter (/=Nothing) $ map (toGardnerN n) [1..10^n-1]

nonConvergence :: Ndigits -> [CycleLength]
nonConvergence = filter (/=1) . map lenCycle . allGardnerN

Merci à blo yhg d’avoir cité la référence à Kaprekar Routine.

Je viens d’apprendre que 6174 et 495 sont des Nombres de Kaprekar.

L’article fait état de plusieurs cycles jusqu’à 5 chiffres … mais ne généralise pas au delà.

Erick

Je n’enlève pas les zéros initiaux des nombres et toi si il me semble.

Non, je les garde. Je travaille avec un nombre de chiffre constant (qui est la longueur de la liste de chiffres wrappée dans un Maybe, et utilisé comme argument de toGardnerN pour tranformer un nombre en sa suite de n chiffres). Il serait en fait assez facile de généraliser mon code à n’importe quelle base juste en modifiant toGardnerN et fldHelper.

Bonjour, En fait avec 3 digits c’est assez simple:

Ecrivons [abc] le nombre de départ. A la première itération le résultat sera de la forme 99(a-c)
Le résultat sera donc un multiple de 99; un élément de la table de 99 puisque (a-c) est inférieur ou égal à 9

Quand on observe la table de 99 on voit que le nombre de résultats possibles en itérant à nouveau est réduit de moitié; (à la seconde itération , 2x99=198 par exemple donnera le même résultat que 9x99=891)

Le facteur (a-c) qui résultera de la seconde itération sera 5,6,7 ou 8.
Et ainsi de suite 5, 6, 7 jusqu’à se limiter à 5, d’où la convergence vers 495.

Avec 4 chiffres au départ [abcd], je me demande si ce n’est pas un peu le même processus puisque la première itération donnera 990(a-d)+99(b-c) ?

@adri1 : Ah oui. J’avais vu que tu utilisais des Int pour stocker les nombres mais en fait le ++ repeat 0 rajoute les zéros qu’il manque.

Par contre, du coup j’ai calculé les cycles pour 6 chiffres en base 10 et j’ai pas trouvé la même chose que toi.

On ne trouve pas de cycle en moins en enlevant les zéros.

L’article fait état de plusieurs cycles jusqu’à 5 chiffres … mais ne généralise pas au delà.

On peut aller au delà avec des méthodes génériques mais pas plus que 20 chiffres j’imagine (avec des super-ordinateurs). Est-ce que quelqu’un saurait estimer jusqu’à combien de chiffres on pourrait calculer les cycles du graphe ?

Enfin, on peut sûrement analyser l’automate en base n avec un logiciel de preuve automatique (un peu comme en base 2 mais avec plein de cas à traiter automatiquement).

@Erouke : J’ai oublié de mentionner l’OEIS grâce à laquelle j’ai trouvé le nom de Kaprekar routine. http://oeis.org/search?q=Kaprekar%20map

Ici tu as les cycles en base 10 (un cycle est donné par son plus petit point) : http://oeis.org/A164718 Il y a une table donnant beaucoup de valeurs ( http://oeis.org/A164718/b164718.txt ), et on voit pas mal de régularité donc on devrait pouvoir trouver une formule comme pour la base 2.

On peut aussi voir que les deux problèmes (en retirant les zéros ou pas) sont bien équivalents. Si on fait décroître le nombre de chiffres en retirant les zéros initiaux, c’est que le nombre est de la forme $(a+1)aa \cdots a$ (à permutation des chiffres près), et donc à l’étape suivante on obtient $(a-1)(a-1)\cdots (a-1)$ puis $0$. Les cycles sont donc les mêmes et tout ce qui change c’est certains nombres (pas beaucoup apparemment) qui arrivent à 0 si on retire les zéros initiaux.

En base 10 avec 7 chiffres, on retombe forcément dans le cycle de longueur 8 contenant 7 509 843, sauf si on tombe sur 0. Est-ce que la longueur d’un cycle est majorée par le nombre de chiffres+1 ?

Par contre, du coup j’ai calculé les cycles pour 6 chiffres en base 10 et j’ai pas trouvé la même chose que toi.

Je vois que le tout somme à 1 million, tu n’aurais pas oublié de virer les nombres avec des chiffres identiques (les 10 qui arrivent sur 0) ? Et surtout, compté plusieurs fois des nombres identiques (comme par exemple 12, 21, 120, 210, etc) ? Je vire les nombres avec 4 chiffres identiques (multiples de 1111) avec la garde rem x ones==0 de toGardnerN et je vire les doublons avec le nub dans allGardnerN.

Ah, je fais effectivement ça mais c’était voulu. J’ai justement vérifié que le tout sommait bien à 10⁶. En éliminant les doublons je trouve bien comme tu dis, avec 352 et 30 points menant aux deux points fixes et tout le reste menant au cycle de longueur 7.

edit En plus en optimisant comme ça le nombre de nœuds est réduit à $\binom{\lfloor N/2 \rfloor + b-1}{b-1}$.

Pour les amateurs de curiosités de ce genre, la référence est selon moi le livre ’Les nombres remarquables’ de François Le Lionnais. L’édition que j’ai date de 1984, je ne sais pas s’il a été réédité.

Pour 6174, il écrit : ( je ne recopie que la fin) : Par ailleurs, Mikio Kano a montré qu’un phénomène analogue se produit, pour des nombres de 4 chiffres, pour les bases 5, 40, 160 et 640. Cela n’apparaît pour aucune autre base < 1000.

Pour le fun, dans ce ’dictionnaire des nombres remarquables’, le nombre suivant 6174 est 6578. Je vous laisse chercher en quoi il est remarquable. Je vous donne un indice totalement inutile : cette particularité de 6578 a été découverte en 1876 par un dénommé A.Martin.

@elegance : Alors j’ai trouvé en cherchant sur internet mais à moins d’être Ramanujan je vois pas comment faire pour trouver !

Effectivement, c’est introuvable. Par contre, la démarche inverse (connaître la propriété, puis chercher le nombre correspondant), ça a dû prendre un certain temps au dénommé Martin, mais c’est faisable.