Cliquez pour afficher

Sans conteste le vainqueur est  8539

7677 5369  4824 1928 1536 918 728  576 342 68 48 32  6

 Cliquez pour afficher

petit programme python pour la chose.. maximum atteint pour 8539

#=== séquence la plus longue
from math import *

def F(n):
    x=floor(n/10)
    y=n-10*x
    return x*y

# DEBUT
Nmax = 10000
Lmax = 0
Result = 0
for i in range(1,Nmax+1):
    compteur = 0
    condition = True
    init = i
    while (condition):
        compteur = compteur + 1
        init = F(init)
        condition = (init > 0)
    # end while
    if (compteur > Lmax):
        Result = i
        Lmax = compteur
    # end if
# next i
print(Result)
# FIN

 Cliquez pour afficher

Pour mémoire, il y a quelques suiveurs assez longs
4929  6077  7677   7836   8663   9166

 Cliquez pour afficher

Bonne réponse à tous les deux

Pour une limite de 10**7 la réponse est unique, ce n'est pas le cas pour 10**5, 10**6, 10**8, 10**9 ou 10**10. Le nombre de réponses reste cependant raisonnable.

Saurez vous trouvez le plus petit nombre qui produit une séquence de 1 nombre, 2 nombres, 3, 4, ... Jusqu'où irez vous?

 Cliquez pour afficher

je n'ai pas compris 10**5  etc...

 Cliquez pour afficher

Oups erreur de notation ^^'
C'est 10**7=10^7=10.000.000, 10**5=10^5=100.000,  etc.

 Cliquez pour afficher

Pour <10^5 j'ai trouvé 78477 mais au  delà excel explose....

 Cliquez pour afficher

Pour <10^5, 78477 est effectivement une solution, l'autre étant 91549
Bien joué

Cette solution m'a fait revoir mon solveur, j'avais oublié toute une série de cas. Du coup il est plus lent .

0.16s pour trouver la solution <10^6
1.71s pour trouver les deux solutions <10^7
16.7s pour trouver les sept solutions  <10^8
238s pour trouver les deux solutions < 10^9 (Et un pic à 1.5Go de ram ) : 961521439 et 946497668.

 Cliquez pour afficher

Je souhaite juste voir si on peut formaliser le problème.

Si je comprends bien, si un entier alors

Donc .

On a et comme il vient .
Par conséquent la suite itérée est strictement décroissante et est donc stationnaire pour tout .

En prenant le cas où n < 10000 alors et

Si on note la division euclidienne de par 10, on commence à avoir un début d'algorithme :

(vous vous rappelez, la bonne vieille division du CP : je pose , je retiens et j'ajoute )

...

je pense que ça peut être long d'optimiser le biniou de façon formelle ...

 Cliquez pour afficher

Partons par exemple de 9 et demandons qui a donné naissance à 9.
Clairement il y a 19,33 et 91. On peut donc ramener le problème à une étude de facteurs premiers.
19 étant premier, il ne peut provenir que de 191, lequel étant premier ne peut provenir que de 1911.

1911 = 637.3 et peut provenir de 6373 lequel est premier et ne put provenir que de 63731.
1911 = 273.7 et peut provenir de 2737 = 391*7 et peut provenir de 3917 lequel est premier et ne peut provenir que de 39171.

33 = 11.3 et peut provenir de 331 ou de 113 lesquels sont premiers et ne peuvent provenir que de 3311 ou de 1131.
91 = 13.7 et peut provenir donc de 911 ou de 137, lesquels sont premiers et ne peuvent provenir que de 9111 et 1371.

Donc il semble que chercher des séquences longues à partir d'un nombre de 4 chiffres semble vouée à l'échec si on part de 9.

Partir de 1 ne donne guère plus de succès : 1 provient nécessairement de 11 lequel provient nécessairement de 111
111 = 37.3 et donc peut provenir de 1111 ou de 373 lequel est premier et provient donc de 3731.

3731 = 533.7 et donc provient soit de 37311 soit de 5337.

1111 = 101.11 mais 11 > 10 donc 1111 ne peut provenir que de 11111
_______________________________________________
Donc je récapitule l'algorithme :

Étant donné un nombre p, on cherche qui peut lui avoir donné naissance :
- si p est premier, il ne peut provenir que de l'entier
- sinon, on cherche toutes les décompositions sous la forme avec et alors p a pour parents les éléments de l'ensemble

On initialise le programme en demandant à l'ordinateur de prendre les nombres de 1 à 9. Essayez déjà pour 1 et 9. Ce sont des séquences pauvres.

Programmeurs, à vous de jouer pour trouver toutes les séquences ... et exhiber les plus longues sur un critère de départ donné.

 Cliquez pour afficher

Pour limiter les recherches on pense à éliminer les terminaisons par:
0    5   01  02  03  04  07  09   52   54  56  58  
ainsi que tous les nombres contenant un 0 .
Le point commun entre :
78477 et 91549 est l'apparition de 49428 dès la deuxième opération
provenant des terminaisons 929 et 386  ensuite tronc commun de 15 cas +final 30

 Cliquez pour afficher

Cette façon inverse de bâtir un nombre à forte décomposition me permet de dire que
30 892 812  est un champion car on retombe sur le fameux  49428

 Cliquez pour afficher

Que dire de:
193 080 076 562   et ainsi des suite....

 Cliquez pour afficher

Oui, effectivement les deux séquences sont très proches. C'est le cas aussi pour 961521439 et 946497668 qui se rejoignent au deuxième terme (605758496).

Je ne comprends pas comment tu peux éliminer toutes ces terminaisons. Certaines ont du sens (01, 02, 0x),  d'autres non. Par exemple 21115 fini par 5 mais produit une "longue" séquence : 21115 -> 10555 -> 5275 -> 2635 -> 1315 -> 655 -> 325 -> 160 -> 0.
Pareil pour 24043 qui contient pourtant un 0.

 Cliquez pour afficher

Pas mal, c'est effectivement le code que j'avais codé en deuxième approche. Elle est beaucoup plus efficace en mémoire.
Cependant tu n'as pas pris en compte toute une série de cas de départ.  Et j'ai fait la même erreur avant que dpi ne me montre le cas 78477 qui est (avec 91549) la séquence la plus longue pour n < 10^5.
Il se trouve que ces séquences finissent  par ... -> 56 -> 30 -> 0. Donc tu l'aurais manqué.
Il faut rajouter comme point de départ tous les nombres finissant par 0 et il y en a beaucoup. Peut-être y a-t-il moyen de limiter leur nombre quand on sait la longueur minimum à atteindre? Par exemple une fois la séquence la plus longue avec point de départ dans [1,9] trouvée?

Voici mon code actuel :

def cherche(N):
   nombres = list(range(1,10)) + list(range(10,N,10))
   while nombres:
      nombres_ = []
      for n in nombres:
         for d in range(1,10):
            if n%d == 0:
               m = n//d*10+d
               if m < N:
                  nombres_.append(m)
      if not nombres_ :
         return nombres
      nombres = nombres_

 Cliquez pour afficher

Si 30892812 est un champion alors qu'est ce 44088819 qui produit 11 termes de plus .
Et il ne passe pas par 49428 .

 Cliquez pour afficher

oui, je me suis rendu compte que les 0 pouvaient sauter lors de la multiplication ou de la  coupure , de même les 5  ne sont à éliminer que précédés  d'un chiffe pair.  

Pour 44 088 819 je ne trouve que 3 d'écart sauf erreur mais il y a une belle série de 6 et de  8.

 Cliquez pour afficher

En amont de ton 44 088 819 on peut  trouver 146 962 733 qui hélas stoppe le filon
car il est premier

 Cliquez pour afficher

Et comment !! Oublier 0 est effectivement une erreur, car ses branches parents sont les éléments de l'ensemble   tout entier. Ceci dit, c'était surtout le raisonnement qui m'intéressait.

 Cliquez pour afficher

Nous avons au delà de 40 888 819 extrapolé jusqu'à 6 998 225 397 mais nous ne sommes pas sûrs qu'une autre chaîne ait pris les relai .
Quel est votre avis?