Journal d'un Terrien

Web log de Serge Boisse

On line depuis 1992 !

Publicité

Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/science/maths/persistance.php

persistance
Metadata
Serge Boisse
Le 27/03/2023 à 11:03
web/MOC
oui
oui

La persistance multiplicative des nombres.

Écrivons un nombre en base 10, disons 243. Multiplions ses chiffres entre eux:
2 x 4 x 3 = 24.
Recommençons : 2 x 4 = 8.  3
En deux étapes, nous arrivons à un nombre inférieur à 10. On dit que la persistance multiplicative en base 10 de 243 est 2.  
Celle de 39, par exemple, est 3 parce qu'on a 39 -> 27 -> 14 ->4. (on arrive à un seul chiffre en en trois étapes, donc)
78889 -> 32256 -> 0
Le plus petit nombre de persistance 0 est évidemment 0, celui de persistance 1 est 10. En fait la table ci-dessous donne les plus petits nombres ayant une persistance donnée:

Persistancep plus petit nombre de persistance p
0 0
1 10
2 25
3 39
4 77
5 679
6 6788
7 68889
8 2677889
9 26888999
10 3778888999
11 277777788888899 

Et après ? Et bien c'est là que ça se corse ; après... On ne sait pas ! Il existe une conjecture qui dit que tout nombre, quelque soit sa taille, a une persistance inférieure ou égale à 11. Mais personne n'a jamais pu le prouver...

En 1981, avec un ordinateur TRS-80, j'ai prouvé que tous les nombres inférieurs à 1050vérifient cette hypothèse (cela a pris environ une semaine de calculs à l'ordinateur, aujourd'hui c'est l'affaire de quelques minutes). Plus tard, j'ai appris que N. Sloane avait déja prouvé cela en 1977. Chapeau !) En fait il n'est pas bien difficile de se rendre compte que les nombres "records" (ceux du tableau ci-dessus) ont une structure particulière, dès que l'on cherche des records de persistance > 3 :

  • Ils ne contiennent pas de 0, ni de 1
  • tous leurs chiffres sont dans un ordre croissant de gauche à droite
  • s'ils contiennent un 5 il est unique et de plus il n'y a aucun chiffre pair (25 excepté)
  • S'ils contiennent un chiffre pair ils ne contiennent pas de 5
  • s'il contiennent un 2 il est unique et de plus dans ce cas il n'y a pas de 3 ni de 4 (ni de 5 of course)
  • S'il y a un 3 il est unique

Ces contraintes permettent facilement de "filtrer" les nombres "admissibles" par un programme qui cherche des records de persistance.  On peut laisser le programme calculer pendant des années, probablement sans rien trouver, mais cela ne vaut pas une démonstration... Si vous écrivez un tel programme, dites-moi jusqu'à quelle valeur vous avez testé la persistance des nombres ! Et si vous avez trouvé une démonstration de la conjecture, dites-le moi bien sûr !

Si ce sujet vous intéresse, vous trouvrez ici un article plus complet (en PDF) sur la persistance multiplicative des nombres et sur d'autres sujets connexes.

Publicité
Commentaires

Commentaires (20) :

Page : [1] 

Serge Boisse
Le 12/06/2019 à 17h59
@Genoss

rien de plus facile :

11111111111111111177
Genoss
Le 20/05/2019 à 20h01
Trouver un nombre s'écrivent avec 20 chiffres dont la persistance soit 4
edebonneuil
Le 29/09/2017 à 16h22
Bonjour, je vais faire un petit article sur le sujet. Vous conseilleriez un journal en particulier? Merci
Edouard Debonneuil
Le 26/09/2017 à 10h18
Suite sur la persistance à la Erdos:

pE( (2)6834594(3)2661292(5)8181026(7)5214775 ) = 25

Mais pour chaque couple 2 et 5, en faisant le produit des chiffre, ça va ajouter un 0 à droite: on ne change pas la persistance à la Erdos en levant les couples 2 et 5.

8181026-6834594=1346432, ainsi

pE( (3)2661292(5)1346432(7)5214775 ) = 25

C'est déjà un plus petit nombre (de 9.2 millions de chiffres...)



Edouard Debonneuil
Le 24/09/2017 à 01h58
avec le code R, qui n'était pas passé:



library(gmp)

pE = function(x)

{

if(x<10) {return(0);}

else {return(1+pE(prod(lapply(strsplit(gsub("0","",as.character(x)),""),as.bigz)[[1]])));}

}



ym=0;for(i in 1:100) {x=(paste0(sample(strsplit("1234567890","")[[1]],100000,replace=T),collapse=""));y=pE(x);if(y>ym) {ym=y;cat(ym,as.character(x),"n")}}



j=floor(runif(4,0,10000000));x=as.bigz(2)^j[1]*as.bigz(3)^j[2]*as.bigz(5)^j[3]*as.bigz(7)^j[4];cat(pE(x),j)

edebonneuil
Le 24/09/2017 à 01h53
Un code R qui vérifie qu'avec des grands nombres on n'a que l'embarras du choix pour avoir une grande persistance à la Erdos:

library(gmp)

Je ne l'ai lancé qu'une fois et sur 100 nombres pris ainsi totalement au hasard ça ma donné une persistance à la Erdos de 21 (nombre trop long pour être accepté par ce forum; je laisse les curieux copier le code sous R pour avoir de tels nombres) alors que l'article de Pour la Science se demandait si avec beaucoup d'astuce on pouvait faire mieux que 17! Il n'y a qu'à se baisser pour ramasser: c'est une bonne illustration que quand on enlève la contrainte des 0 la persistance est illimitée



Sous vos yeux ébahis n'est-ce pas :) voici également le premier nombre (de ce que j'ai lu) connu de persistance 25 à la Erdos:

pE( (2)6834594(3)2661292(5)8181026(7)5214775 ) = 25



Comment a-t-il été obtenu? ... au hasard! Plus précisément un produit de chiffres x=2^a*3^b*5^c*7^d (où a,b,c,d sont tirés au hasard) a été pris au hasard:

j=floor(runif(4,0,10000000));x=as.bigz(2)^j[1]*as.bigz(3)^j[2]*as.bigz(5)^j[3]*as.bigz(7)^j[4];cat(pE(x),j,"n")

Résultat: 24 6834594 2661292 8181026 5214775

Bingo. Peut-être qu'en faisant 100 tirages au hasard on tombe sur une persistance à la Erdos de 30. Nb: rien que pour un nombre ça a tourné pendant une bonne dizaine vu la taille à manipuler.



* * *

Ainsi, du fait des produits par 0 la persistance multiplicative est limitée... à 11 (ce qui est observé pour les nombre entre 1 et 10^1000)? ou 12 ou 13, ou plus, jsais pas Msieur.
edebonneuil
Le 23/09/2017 à 23h32
Ha ha!!

1) j'ai repris les liens lus pour voir d'où est venue l'idée du 0 bloquant couplé au 2^i*3^j*5^k*7^k*9^l: 1a) du Pour La Science qui justement s'ouvre en cliquant sur le lien "ici" en haut de page, posté par @Serge Boissé 1b) de la remarque de @Frederik ci-dessous. 1c) d'une autre super page

http://www.primepuzzles.net/puzzles/puzz_341.htm



2) En reprenant cette dernière page, tadaa, un lien vers une magnifique courbe qui vérifie expérimentalement (dans les limites expérimentales) que la persistance à la Erdos n'est limitée: http://ahonga.fr/js/pls430-nostat.html



Bon, prochain post quand j'aurai été jusqu'à 10^10000 et/ou étendu Erdos un peu plus, pour ne pas spammer. Cheers
edebonneuil
Le 23/09/2017 à 22h48
PS: en sachant qu'il n'y a pas de persistance 12 jusqu'à 10^1000 et connaissant la forme de la décroissance du nombre de maillons on peut définir une *probabilité résiduelle* qu'il existe une persistance 12 (intégrale sous la courbe à droite de 10^1000). Ok, toujours pas une preve... et peut-être bien que la persistance 12 existe!
edebonneuil
Le 23/09/2017 à 22h45
Très juste. J'ai vérifié qu'il n'y a pas de persistance 12 jusqu'à 10^1000; je compte prochainement paralléliser le programmes et vérifié jusqu'à 10^10000. Qqn a déjà regardé ça ici?



Savoir si 11 est la limite est plus palpitant, c'est sûr; après savoir s'il y a une limite ou pas est en soit la question fondamentale: j'ai vu ce Pour la Science de 2013 http://www.lifl.fr/~jdelahay/pls/2013/237.pdf et a) vers la fin ils posent la question pour tout base fixe (pas seulement la base 10), et le raisonnement que j'ai posté ici s'applique bien aux bases 5/8/318 etc. b) en haut de la page 4 un mathématicien définit une persistance multiplicative sans la contrainte des 0 (à la Erdos) et conjecture que cette persistance 'à la Erdos' a une limite a un maximum, alors.. qu'il se trompe là je crois: avec le même raisonnement que j'ai posté, il y a O(n^3) maillons à la Erdos de taille n, o(n^a), a>0 maillons de maillons de maillons.. de maillions à la Erdos de taille n: bref quelque soit la persistance à la Erdos voulue on a l'embarras du choix.

Du coup, à vérifier expérimentalement
Serge Boisse
Le 20/09/2017 à 22h15
@edebonneuil

intéressant,mais ça ne prouve pas que ce maximum d'étapes est bien 11...
edebonneuil
Le 20/09/2017 à 13h32
correction:

non pas A mais O(n^2): c'est le nombre de nombres de type 2^i*3^j*7^k ou 3^i*5^j*7^k qui s'écrivent avec n chiffres.

car 1O^n < 2^i*3^j*7^k < 10^(n+1) s'écrit n<i*log2+j*log3+k*log7<n+1. Et le nombre de i*log2+j*log3+k*log7<n est le volume d'un demi cube de côté n/log2, n/log3, n/log4.



Entre un polynome et une exponentielle ça ne change pas que l'exponentielle l'emporte: le nombre de 2^i*3^j*7^k ou 3^i*5^j*7^k n'augmente "que" polynomialement avec leur taille n alors que la part des nombres sans 0 décroit exponentiellement avec la taille n. Quand compte (intègre) sur l'ensemble des tailles n ça fait un nombre fini de maillons et non pas illimité: la persistance multiplicative est donc limitée, c'est la faute aux 0!
edebonneuil
Le 19/09/2017 à 16h58
J'ai trouvé ce matin pourquoi la persistance multiplicative des nombres a un maximum: le nombre de maillons possibles (au sens: nombres qui sont des produits de chiffres et dont l'écriture ne contient pas de 0) n'est pas infini!

Du coup la persistance est limitée: on ne peut pas construire une suite (décroissante) infinie entre un nombre limité de maillons.



Je fais l'hypothèse, c'est vrai, que les produits de chiffres n'ont pas une écriture bizarroïde du type absence fréquente de 0 -- et on obtient alors qu'il y a asymptotiquement A*(9/10)^n maillons potentiels de taille n [A=(log2+log5)*log3*log7/2], c'est à dire s'écrivant avec n chiffres. Comme 9/10 < 1 c'est intégrable donc le nombre total de maillons potentiels sur les entiers existe, il n'est pas infini. CQFD.
Fredrick
Le 28/07/2016 à 08h54
Bonjour,

Le gros problème est que dès qu'il y a un 0 dans un nombre la persistance multiplicative tombe à 1.

Et lorsqu'on fait des recherches avec des nombres ayant plusieurs centaines de chiffres, la probabilité de trouver un 0 dans ce nombre est énorme. Idem dans le nombre obtenu en multipliant ses chiffres.

Donc plus on recherche de grand nombre, moins on a de chance d'avoir une grande persistance multiplicative.
Fredrick
Le 27/07/2016 à 16h50
Bonjour,

Le gros problème est que dès qu'il y a un 0 dans un nombre la persistance multiplicative tombe à 1.

Et lorsqu'on fait des recherches avec des nombres ayant plusieurs centaines de chiffres, la probabilité de trouver un 0 dans ce nombre est énorme. Idem dans le nombre obtenu en multipliant ses chiffres.

Donc plus on recherche de grand nombre, moins on a de chance d'avoir une grande persistance multiplicative.
S.Yas.
Le 26/07/2016 à 22h03
@lopito12<br />rnOui en effet, je l'ai testé aussi avec plusieurs nombres mais cela n'a pas abouti à un nombre qui respecte les règles citées dans cet article. Du coup, il faut la prendre avec des pincettes.<br />rnN'empêche, cette méthode pourrait ouvrir d'autres voies de réflexion quant au problème. En tout cas, big up!
page suivante (plus anciens) >

Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !
Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.
< Retour en haut de la page