|
#1 - 04-01-2018 09:49:05
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
suited pérodiques
Bonjour @ tous.
Soit "a" un entier naturel donné , et u0 une suite de " a " chiffres. u n = la suite des carrés des chiffres de u ( n-1 ) pris dans l'ordre, suite limitée à " a " chiffres.
Exemple : 2457 --->4;16;25;49 dont on ne retient que les 4 premiers chiffres soit 4162.
La suite u est forcément périodique. Il faut donner les périodes de u en fonction de " a " et de u0.
Bonne recherche et ne vous laissez pas enfumer....
#2 - 04-01-2018 11:45:12
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Suites pérodiquess
Bonjour Nodgim
Je suppose que tu veux dire que la suite va finir par boucler et que tu demandes la "taille" de la boucle .
Vasimolo
#3 - 04-01-2018 12:48:24
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Suites péérodiques
Oui Vasimolo, la suite va nécessairement reboucler sur elle même, c'est à dire il y aura u (n+k) = u (n). C'est " k " qui est demandé.
Le terme " période " est mal approprié ? En fait elle sera périodique à partir d'un certain rang.
#4 - 04-01-2018 14:27:18
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
uSites pérodiques
Salut, Intéressant !
Supposons que la suite ne boucle pas, un terme n'ayant qu'une image, cela signifierait qu'il y a un nombre infini de termes possibles pour ne pas retomber sur un terme ayant déjà été utilisé. Or il n'y en a que 10 000 possibles, la suite boucle donc forcément...
#5 - 04-01-2018 15:45:44
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
#6 - 04-01-2018 16:30:39
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Suiets pérodiques
@ Golgot : oui, comme chaque nombre de la suite est restreint par la norme de " a " chiffres, dont la quantité est finie, il y a forcément rebouclage, la suite est périodique à partir d'un certain rang.
@ Masab: un début de réponse avec 1111, suite périodique de période 1. A remarquer qu'on a aussi ce résultat avec des zéros et des as mélangés.
Il faut maintenant résoudre pour les autres nombres. Et aussi pour "a" quelconque.
il y a encore un peu de travail, mais ne vous laissez pas enfumer....
#7 - 04-01-2018 19:28:26
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
suites pérodiqueq
Pour a=4, voici les 8 cycles d'ordre 4 : [1003, 1009, 1008, 1006, 1003] [1013, 1019, 1018, 1016, 1013] [1036, 1093, 1081, 1064, 1036] [1103, 1109, 1108, 1106, 1103] [1113, 1119, 1118, 1116, 1113] [1136, 1193, 1181, 1164, 1136] [1361, 1936, 1819, 1641, 1361] [3616, 9361, 8193, 6418, 3616]
Il semble que les périodes soient toutes égales à 1 ou 4. Il semble aussi que pour a quelconque il y a exactement [latex]2^{a-1}[/latex] cycles d'ordre 1 [latex]2^{a-1}[/latex] cycles d'ordre 4
Voilà ! Reste à le prouver...
#8 - 04-01-2018 20:00:28
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Suites péroiques
Je dirais que la suite est périodique (à partir d'un certain rang) de période 4, sauf dans le cas où les a-1 premiers chiffres de u0 sont dans {0;1} et où le dernier chiffre de u0 est dans {0;1;2;4;5;7} : la période vaut alors 1.
En fait, seul le premier chiffre de u0 différent de 0 ou 1 a de l'importance, tout ce qui est à droite de ce chiffre va se faire éjecter vers la droite au bout d'un certain temps.
#9 - 05-01-2018 08:09:18
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Suittes pérodiques
@ Masab : Tu as déja bien débroussaillé le problème, reste en effet à analyser tout ça.
@ Ebichu : Ton analyse est la bonne. Il manque toutefois encore la rédaction de la preuve, ce n'est pas bien long.
#10 - 05-01-2018 10:43:46
- LeJeu
- Passionné de Prise2Tete
- Enigmes résolues : 25
- Messages : 74
Suitess pérodiques
Quel que soit le nombre "a" c'est le premier chiffre de U0 ( différent de 1) qui va imposer la suite Un
les chiffres de Un sont poussés vers la droite par exemple pour a = 4 u0 = 9... u1 = 81.. u2 = 641. u3 = 3616
donc si u0 commence par 9 8 6 ou 3 en continuant on trouve Un de périodicité 4 de le forme 9 361 361 361..... 8 193 619 361... 6 418 193 618... 3 616 164 181... 9 361 361 361...
si U0 commence par 7 , U1 commence par 4 si U0 commence par 5 , U1 commence par 2 si U0 commence par 2 , U1 commence par 4 si U0 commence par 4 , U1 commence par 16
donc si U0 commence par 7 5 2 4, on trouve Un commençant par 1 et de périodicité 4 comme ci dessus 19 361 361 361..... 18 193 619 361 16 418 193 618 13 616 164 181 19 361 361 361
enfin si u0 commence par 1 on cherche le 1° chiffre différent de 1 ou 0 pour conclure soit une suite stationnaire de 1 et de 0 , soit on retombe sur les cas précédents
merci Nodgim pour ce joli pb.
#11 - 05-01-2018 15:23:08
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Suiites pérodiques
Ton analyse est correcte, Lejeu, cependant tu ne donnes pas vraiment de preuve. Elle est courte, mais il faut l'exhiber du constat que tu as fait.
Courage.
#12 - 05-01-2018 15:36:00
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
Suites pérodiquees
Preuve pour a=1. 1 -> 1 2 -> 4 -> 1 3 -> 9 -> 8 -> 6 -> 3 5 -> 2 -> 4 -> 1 7 -> 4 -> 1 Donc 1 -> 1 est le seul 1-cycle 3 -> 9 -> 8 -> 6 -> 3 est le seul 4-cycle
Preuve pour a=2. D'après ce qui précède, les 1 cycles commencent par 1* . Les 4-cycles contiennent 1* ou 3* . D'où 2 1-cycles et 2 4-cycles : 10 -> 10 11 -> 11 13 -> 19 -> 18 -> 16 -> 13 36 -> 93 -> 81 -> 64 -> 36
Preuve pour a=3. Les 1-cycles sont de la forme 10* ou 11*. Les 4-cycles contiennent 10* ou 11* ou 13* ou 36*. D'où 4 1-cycles et 4 4-cycles : 100 -> 100 101 -> 101 110 -> 110 111 -> 111 103 -> 109 -> 108 -> 106 -> 103 113 -> 119 -> 118 -> 116 -> 113 136 -> 193 -> 181 -> 164 -> 136 361 -> 936 -> 819 -> 641 -> 361
#13 - 05-01-2018 19:03:29
- LeJeu
- Passionné de Prise2Tete
- Enigmes résolues : 25
- Messages : 74
quites pérodiques
C'est vrai que la preuve était à peine murmurée.. je complète
Je dis que si l'on part de 9 8 6 ou3 on obtient à un moment U(n) = 9 361 361 ..... ( un 9 suivi x fois du paquet de trois chiffres 361) de longueur supérieur à a
en effet si on part de 9 on trouve un U(n) commençant par 9361 81 641 36161 9361361
idem en partant de 8 6 ou 3
Puis en partant de 9361 , on le décompose en 9 suivi de 1 paquet '361'
le 9 se transforme en 4 tour en : 81 641 36161 9361361
et le 361 se transforme en 4 tour 936 819 641 361
donc le 9 suivi de 1 paquet '361' se transforme en 9 suivi de 3 paquets '361'
si on recommence en gardant 9 suivi de 2 paquets '361' en séparant en (9 361)(361) en 4 tour on a donc 9 suivi de 4 paquets de '361
si on recommence on décompose en( 9 suivi de 3 paquets de '361' )(361) en 4 tours on a donc 9 suivi de 5 paquet de '361'
ainsi de suite pour obtenir à un moment donné U(n)= 9 suivi de x paquets de trois chiffres 361 le tout de longueur supérieur à a et on a alors U(n+4) =U(n)
#14 - 05-01-2018 19:27:33
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
suites pérodoques
@ Lejeu: désolé ta démo ne tient pas puisque tu te trompes sur le nombre récurrent. Essaye de prolonger ton nombre, tu vas t'apercevoir que la belle mécanique se dérègle au dela du 10 ème chiffre. Et ça se démontre facilement.
@ Masab : bien, mais tu ne pourras pas procéder ainsi pour de plus grands nombres. Quelque chose t'échappe encore. Il ne faut pas se laisser enfumer par l'énoncé.....
#15 - 06-01-2018 09:05:21
- LeJeu
- Passionné de Prise2Tete
- Enigmes résolues : 25
- Messages : 74
duites pérodiques
La nuit portant conseil, on oublie le 2ieme post et je viens compléter le 1°
- la seule chose importante est le 1° chiffre ( les autres seront poussés vers la droite, on ne s'en occupe pas))
- les chiffres 8,3,6,9 sont particuliers car en 4 transformations : 3->36161 6->64181936 8->819361936 9->9361361 et donc on retrouve le chiffre de départ en 1° position!
par cette simple propriété, en partant d'un seul chiffre toutes les 4 transformations on retrouve le nb précédent mais complété par de nouveaux chiffres ( peu importe la façon de les générer)
3 36161 3616116418193616
et donc quelque soit 'a' on trouvera bien les 'a' premiers chiffres égaux après un certain nb d'itérations
pour les chiffres 2,4,5,7 on trouve à chaque fois un nombre commençant par 16 le 1 est stationnaire ,et le 6 suit la règle précédente
pour le chiffre 1 on trouve le 1° chiffre différent de 1 et de 0 et on est ramené au 1° cas
#16 - 06-01-2018 11:44:16
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
suutes pérodiques
C'est bien ça, Lejeu. Je l'aurais exprimé un peu différemment, mais bon c'est OK, bravo à toi !
#17 - 07-01-2018 10:49:25
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Suties pérodiques
Le temps est écoulé, vous pouvez voir les réponses.
L'énoncé était trompeur dès le départ. Pour un chiffre autre que 0 ou 1, l'algorithme engendre des nombres strictement croissants. Donc le 1er chiffre à gauche différent de 0 ou 1 repousse vers la droite tous les autres. Autrement dit, les autres chiffres ne servent à rien pour notre problème.
Pour le 1er chiffre différent de 0 ou 1, si c'est un 7,4,2 ou 5, on aboutira en 1er chiffre sur un 1, et 6 en 2ème chiffre. Pour les chiffres 6,3,9 et 8, on boucle sur une période 4. Donc quel que soit le 1er chiffre à gauche autre que 0 ou 1, on tombe sur la boucle 6,3,9,8.
Or si on un 6 en k, on a donc un 6 en k+4, même rang dans le nombre. Donc on trouve un 36 en k+1 et aussi un 36 en k+5. et 936 en k+2 et 936 en k+6. etc....
Donc non seulement au bout d'un certain nombre d'itérations on retrouve le même nombre sur une période 4, mais en plus on trouve toujours le même nombre modulo 4 quel que soit le nombre de départ ! hormis les 0 ou 1 à droite.
Merci @ tous pour vos réponses, abouties ou pas, l'important est de participer.
|
|