Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-10-2016 10:33:56

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

l'indicr de l'air

Bonjour à tous.

Cette énigme ne requiert aucune connaissance particulière, niveau Lycée.

Soit la suite uo = m entier naturel et u ( n + 1 ) = phi (u n ). On arrête la suite quand u (k) = 1.

où phi (m) est la fonction indicatrice d' Euler, celle qui calcule le nombre de nombres premiers avec m et < m. On donne la formule :

phi ( m ) = m * (1-1/p1)*(1-1/p2).....où p1, p2, ...sont les facteurs premiers de m.

Trouvez l'intervalle, fonction de m, le plus étroit possible pour la valeur de k. 

Bon amusement.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 15-10-2016 11:43:36

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

L'indic de l'air

L'IXIIL'R

Vasimolo

 #3 - 15-10-2016 16:17:57

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 67

l'indice de k'air

Bonjour,
Je propose l'intervalle [latex][v(m),v(m)][/latex], ou v est la suite définie par l'A003434, qui dépend bien de m. Je pense que l'on ne trouvera pas plus petit comme intervalle big_smile ...
Plus sérieusement, [latex]\phi(m) < m - \sqrt{m}[/latex] si m est composé
m admet au moins un diviseur p inférieur à [latex]\sqrt{n}[/latex].
Les multiples de ce diviseur apparaissent m/p fois, qui est supérieur à [latex]\sqrt{m}[/latex].
On remarque aisément que [latex]\phi(m)[/latex] est composé (ou égal à deux)
On peut donc écrire que [latex]\phi^n(m) < \phi^{n-1}(m-1) < m-n[/latex]
Donc k est inférieur à m-1. (Je bloque un peu pour utiliser efficacement l'expression avec la racine, je ne trouve pas d'expression simple, ni de majoration suffisamment efficace). 
Du côté de la minoration, On peut écrire [latex]\phi(m) = m(p-1)/p1...(pi-1)/p i> m\times1/2\times2/3\times3/4\times...\times(p-1)/p = \dfrac{m}{\sqrt m} = \sqrt{m}[/latex]
avec p le plus grand facteur premier de m.
C'est valable pour n strictement supérieur à 6 car 6 est le plus grand nombre divisible par un nombre premier supérieur à sa racine.
On déduit que [latex]\phi^n(m) > m^{\frac{1}{2n}} [/latex] tant que ce n'est pas inférieur à 6...
[TeX]m^{1/2n} \leq 6 \iff n \geq \dfrac{ln(\dfrac{ln(m)}{ln(6)})}{ln(2)}[/TeX]
Ensuite, en minimum 1 étapes, c'est plié, donc la borne inférieure de k est [latex]\dfrac{ln(\dfrac{ln(m)}{ln(6)})}{ln(2)} + 1[/latex] Je pense pouvoir faire mieux car j'ai vu de magnifiques minorations de phi sur le net, beaucoup plus fines que celle ci... Par contre, pour la majoration, ça me semble plus compliqué d'améliorer...

 #4 - 15-10-2016 16:38:55

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

L'inice de l'air

@ Caduk:
Et donc, en application de tes formules, quel intervalle proposes tu pour, par exemple, le nombre 36235 ?

 #5 - 15-10-2016 17:08:37

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 67

L'indice e l'air

Améliorons notre minoration:
Le lien http://www.les-mathematiques.net/phorum … 317,395974 nous donne : [latex]\phi(m) > \dfrac{m}{ln(ln(m))}[/latex].
On en déduit aisément par récurrence que [latex]\phi^n(m) > \dfrac{m}{(ln(ln(m)))^n}[/latex]
On obtient alors [latex]k > \dfrac{ln(m)}{ln(ln(ln(m)))}[/latex] sauf erreur.
L'application de mes formules donne
13 <k< 36234
C'est un peu nul comme encadrement lol
mais ça doit être surtout dû à ma majoration, je vais chercher mieux dessus...
Edit: je crois que je trouve 14 pour 36235, elle a l'air assez balèze ma minoration smile

 #6 - 15-10-2016 17:50:07

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 67

l'indicr de l'air

Améliorons cette majoration:
Pour m supérieur  à p^2, on a [latex]\phi(m) < m - \sqrt p[/latex] avec m composé et supérieur à p^2.
On a donc [latex]\phi^n(m) < \phi^{n-1}(m) < m - 1 - (n-1)\sqrt p [/latex]
A partir de [latex]n = \dfrac{m-1}{p}-p-1[/latex] , [latex]\phi(m) < p^2[/latex]
On obtient donc comme majoration [latex]k < \dfrac{m+1}{p} + \psi(p^2)-p-1 [/latex] ou phi est la plus grande valeur de k en dessous de p^2.
On voit bien que si on prend p = 1, on retrouve notre majoration précédente.
Il faut choisir p de manière à avoir une majoration correcte.
En prenant l'aoeis, phi(105) = 7 donc k < (36235-1)/105+6-105-1  donc k < 245
C'est beaucoup mieux, mais on n'y est pas encore.
Il me reste peut être bien une idée de majoration, mais je ferais ça un peu plus tard..

 #7 - 15-10-2016 18:12:16

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

L'ndice de l'air

Bon, c'est une première réponse, je la retiens.

OEIS, heureusement, ne dit pas tout. C'est agaçant, cette référence quand on suggère une suite....

Ta minoration est très bonne, mais se détériore lorsque le nombre grandit.
Ta majoration est encore assez loin de ce que j'ai. Surtout, j'ai une valeur pour 36235 bien mieux centrée dans l'encadrement (ce nombre a été choisi au hasard)

Sinon, ta démarche est totalement différente de la mienne.

Cette suite s'analyse avec une feuille de papier et un stylo. Aucun outil n'est nécessaire. Aucune référence sur Internet n'est à rechercher. Il faut juste faire travailler ses petites cellules grises, comme dirait H.Poirot.

 #8 - 15-10-2016 18:22:02

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 67

L'idice de l'air

Mais oui, ça marche bel et bien!
On peut remarquer que le plus grand facteur premier p de phi diminue progressivement. Sa multiplicité diminue de 1 à chaque fois, et ne peut être supérieure à ln(m)/ln(p).
On trouve donc que [latex]k < \sum \limits_{i=0}^{\sqrt m} \dfrac{ln(m)}{ln(i)} = ln(m) \sum \limits_{i=0}^{\sqrt m} \dfrac{1}{ln(i)} < \sqrt{m}\dfrac{ln(m)}{ln(2)}[/latex]
Ce qui nous donne k < 2882
C'est moins bien, mais on sort du linéaire, c'est donc mieux pour des grandes valeurs de m. Je pense que l'on peut améliorer l'inégalité sur la somme. j'avais déjà cherché dans le même genre, mais je n'avais pas trouvé de résultats intéressants, que ce soit sur papier ou sur internet...

 #9 - 15-10-2016 18:39:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

l'induce de l'air

@ Caduk: c'est mieux déjà, mais ça dérive vite de toute façon par rapport à ma majoration. Je valide tout de même, c'est une 1ère réponse. On peut faire beaucoup mieux, et bien plus simplement (mais comme dit Vasimolo, la simplicité n'exclut pas la subtilité).   

@ tous : Les extrémités de l'intervalle, une fois qu'on a trouvé le truc, se calculent facilement à la main, sans calculette.

 #10 - 15-10-2016 20:23:26

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

L'indice de l''air

Est-ce la réponse suivante que tu attends ?
* si m<=2^n alors k<=n.
* si m>2.3^n alors k>n+1.

 #11 - 16-10-2016 08:31:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

l'ibdice de l'air

C'est cela, Ebichu, bravo !

A une nuance près tout de même pour la majoration, à laquelle j'ai ajouté +1 pour le majorant + 1 premier.

 #12 - 16-10-2016 10:55:08

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

L'indice de 'lair

Suis-je le seul à ne pas comprendre la question ?

Il faut trouver le plus petit [latex]m(k)=u_0[/latex] tel que la suite [latex]u_n[/latex] soit de longueur [latex]k[/latex] ?

Vasimolo

 #13 - 16-10-2016 12:52:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

L'indice de l'aiir

Ce n'est pas tout à fait l'énoncé, Vasimolo.

La question est d'avoir une formule simple qui donne un encadrement de k, le plus fin possible, quel que soit m. Si m est un nombre à 20 chiffres par exemple, ce serait sûrement très long de calculer la valeur exacte de k, et encore en s'aidant des logiciels de décomposition en facteurs premiers. Avec la formule, on peut donner un encadrement assez fin. Pour ce nombre à 20 chiffres, on peut estimer le k à 50 environ (milieu de l'encadrement).

 #14 - 16-10-2016 18:05:42

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 143

L'indice de lair

Salut,

Sans trop pousser la recherche j'ai [latex]\lfloor \mathbb{log}_2(m) \rfloor[/latex] comme majorant pour les pairs et [latex]\lfloor \mathbb{log}_2(m) \rfloor +1[/latex]  pour les impairs.

Difficile de trouver une minoration fine par contre ...

Je repasserai smile

 #15 - 16-10-2016 18:30:02

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

L'inddice de l'air

@Sydre : c'est bon pour le majorant, qui est en effet le plus facile à découvrir. Des 2 que tu proposes, je garde le plus grand, qui convient pour tous nombres. On m'a donné ton majorant inférieur pour tout nombre, je crois que c'est bon aussi, mais je dois confirmer. Cela dit, ça ne fait pas beaucoup de différence entre les deux.

 #16 - 16-10-2016 20:26:14

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 143

Li'ndice de l'air

Après réflexion je dirai [latex]\lfloor \mathbb{log}_3(m) \rfloor[/latex] comme minorant.

Sinon [latex]\lfloor \mathbb{log}_2(m) \rfloor[/latex] est dépassé pour les nombres premiers de la forme [latex]2^n+1[/latex]

 #17 - 17-10-2016 08:01:43

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

L'indice e l'air

@ Sydre: pour le minorant, il y a un chouia mieux, mais c'est presque ça, bravo !
Pour le majorant, l'une ou l'autre des 2 valeurs conviennent, on en reparlera à découvert.

 #18 - 18-10-2016 13:48:40

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

L'indice de l'ai

Le temps est maintenant écoulé, la réponse correcte a été donnée plusieurs fois, elle mérite tout de même quelques justifications.

Le nombre d'étapes maximum pour un nombre donné correspond au nombre de chiffres quand celui ci est écrit en binaire, et le nombre minimum d'étapes correspond au nombre de chiffres quand il est écrit en base 3.

Pour découvir la solution, il faut observer les étapes en décomposant toujours le résultat. 

Il est d'abord à remarquer que le 1er nombre de la suite est pair, et tous les suivants jusqu'à 1. Ceci est dû au fait qu'un p-1, pour tout p > 2, est pair. Quand on substitue un p-1 à un p, dans l'opération élémentaire *(1-1/p), on fait apparaitre 2 dans la décomposition du résultat. Et donc, comme un 2 présent dans une décomposition divise par 2 le nombre suivant *(1-1/2) = *1/2, chaque étape, sauf la 1ère, divise au minimum le nombre suivant par 2. Aussi, le nombre maximum d'étapes pour un nombre donné ne peut dépasser le nombre d'étapes de la puissance de 2 qui lui est supérieure.
Le facteur premier, après le 2, qui contribue le mieux raccourcir le nombre d'étapes est le 3, car (p-1)/p est le plus éloigné de 1 pour p = 3. De plus, 3 se transforme en un seul 2, à la différence de 5 par exemple, qui en se transformant en 4, donne 2 fois le 2. Pour 5, il faut passer par 4 puis 2 avant d'arriver à 1, alors que 3 ne passe que par 2. De même, on peut avec beaucoup de facteurs premiers, éloigner le rapport de diminution de 1, mais en contre-partie, on crée autant de 2 qui vont ajouter des étapes. En gros, un facteur premier impair crée au moins une étape supplémentaire par la création d'un 2. On n'a donc pas intérêt à multiplier les facteurs premiers, mais à se concentrer sur le plus performant. C'est la raison pour laquelle un nombre de la forme 2 * 3^n est celui qui exige le minimum d'étapes : le nombre suivant est divisé par 3 jusqu'à obtenir le nombre 2.

Merci aux participants et félicitations à ceux qui ont trouvé l'intervalle minimum.

 #19 - 19-10-2016 19:43:58

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

L'indice de 'air

Si on appelle s(n) la relation qui à n donne k, peut on déduire s(abc...) si on connait s(a) s(b) s(c)..... ?

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete