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-03-2018 16:23:28

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

Syracues élargi (2)

Dans cette seconde partie, on part d'un couple d'entiers naturels (a0, n ).

" a0 " est le nombre initial de la suite, et " n " le nombre d'itérations (ou nombre de nombres impairs) de la boucle.

Montrer qu'on peut toujours trouver un  " b " entier qui est paramètre de la suite définie par : si ak pair, a(k+1)= ak / 2 sinon 3 ak + b, tel que le retour sur a0 se produise après au minimum n itérations.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 17-03-2018 22:52:43

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 727

syracuse élarfi (2)

On commence par diviser a0 par 2 jusqu'à obtenir un nombre impair, noté x.

Le problème précédent avait été l'occasion d'observer qu'il existait une boucle de n itérations si la relation suivante était vérifiée :
[TeX]\displaystyle{x\left(2^m-3^n\right)=b\left(\sum_{i=0}^{n-1}2^{i}3^{n-1-i}\right)}[/TeX]
Le calcul de la somme de droite donne [latex]3^n-2^n[/latex], d'où :
[TeX]\displaystyle{x\left(2^m-3^n\right)=b\left(3^n-2^n\right)}[/TeX]
On pourra donc trouver une valeur de b convenable si on trouve une valeur de m assez grande pour que [latex]2^m-3^n[/latex] soit positif, pour que (m-n+1) soit supérieur au nombre de facteurs 2 de a0 (ce qui assure de repasser par a0 à la dernière étape de la boucle), et telle que [latex]3^n-2^n[/latex] divise [latex]2^m-3^n[/latex].

Or [latex]2^m-3^n=2^{m-n}.2^n-3^n[/latex], donc il suffit de prendre m tel que [latex]2^{m-n}=1[/latex] mod [latex](3^n-2^n)[/latex], ce qui est possible car 2 et [latex]3^n-2^n[/latex] sont premiers entre eux.

Exemple : a0=20 et n=3.

On débarrasse 20 de ses facteurs et on obtient x=5.

[latex]3^3-2^3=19[/latex], et [latex]2^{18}=1[/latex] mod 19, donc on prend [latex]b=\frac{5.(2^{3+18}-3^3)}{19}=551875[/latex].

Vérification : on obtient la boucle 5 - 275945 - 689855 - 5 qui passe bien par 20.

J'ai pris 21 comme puissance de 2 car cela suffisait, mais j'aurais pu tout aussi bien prendre 39, 57... si cela était nécessaire.

 #3 - 18-03-2018 07:51:59

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

Syyracuse élargi (2)

C'est tout à fait ça Ebichu, bravo à toi !

Cette question est en cours sur 2 autres sites et reste sans réponse pour l'instant (cependant pas d'énigme en 2 temps comme ici).

Je donne ma propre version pour archivage, avec quelques nuances, et aussi la réponse si "a0" est multiple de 3.

Supposons tout d'abord qu'il existe "a" ( " a " considéré ici comme impair et premier avec 3. Dans les autres cas, un petit aménagement sera à apporter par la suite)  et "b" tel que :

  (3*....( 3 * ( (3 a + b) / 2 ^ p1) + b ) / 2 ^ p2...) + b ) / 2 ^ pn = a avec p1+p2+...pn = m

On développe en séparant les coefficients des " a " et des " b ", et on aboutit à :

( 2 ^ m - 3 ^ n ) * a = b *  ( 3^(n-1) + ( 2 ^ p1 ) *  3 ^ (n-2) + ( 2 ^ ( p1+ p2 ) ) * 3 ^ (n - 3) +......2 ^ ( m - pn) )

Soit k * a = j * b

Il suffit de donner à " a "  la valeur " j " et à  " b " la valeur " k " pour obtenir l'égalité.

Notons au passage (ne sert pas pour la démo) qu'il suffit de trouver un " k " qui divise " j " pour infirmer la vraie conjecture, car alors il suffit de remplacer "b" par 1.

Le fait de passer de l'écriture de l'algorithme initial à l'écriture synthétique k * a = j * b n'est équivalent que si on est sûr que les valeurs prises pour " a " et " b " donnent toujours un nombre entier au fur et à mesure des multiplications et des divisions, ce qui n'est pas évident au premier abord. Car on pourrait avoir un résultat final correct mais avec des valeurs intermédiaires non entières. Mais la réserve est levée dès qu'on se rend compte que, si dans l'algorithme multiplications / divisions successsives, un nombre intermédiaire venait à perdre son caractère entier du fait de trop ou pas assez de divisions par 2, il serait impossible d'obtenir, à la fin des n itérations, un nombre entier.

L'équivalence est donc acquise.

Le nombre d'itérations et les différentes divisions successives sont totalement décrites par un n uplet caractéristique : ( p1, p2, ....pn). Et ce " n uplet " permet le calcul de k et j.

Notons que pour le calcul de " j " on ne se sert pas de la dernière puissance de 2 : pn.  Autrement dit j (p1, p2, ....pn ) = j ( p1, p2, ....p'n) avec pn et p'n distincts.

En revanche, pour calculer k, on a besoin de m, somme de toutes les puissances de 2, mais ni de l'ordre ni de la répartition des différentes puissances de 2.

k ( p1, p2, ...pn ) = k (p'1, p'2,.....p'n) sous la seule condition que p1 + p2 + ....pn = p' 1 + p' 2 +....p' n.

Ainsi, après le calcul de k à partir d'un n uplet, " b" étant fixé par la valeur k, on peut associer un certain nombre d'autres n uplets (et donc autant de " j " et de " a " ) selon la répartition des différentes puissances de 2 au delà de la valeur minimale 1. Le nombre des n uplets est un simple calcul combinatoire.

Cas particulier

On montre facilement que j (1, 1,.....1) = - k = - 2 ^ n + 3 ^ n.

On a alors k * a = - k * b et donc en prenant b = -a l'algorithme "pas à pas" donne 3a - a = 2a qui donne " a ". C'est un justificatif court à l'égalité ci-dessus.

C'est à partir de ce cas particulier qu'on va trouver la solution au problème posé.

Soit " a " posé.

2 ^ ( r * phi(a)) - 3 ^ ( r * phi(a) ) = k = - q * a,  r permet d'ajuster le nombre d'itérations dont on a besoin. j vaut ici q * a

Comme 2 ^ phi(q) = 1 [q], on a 2 ^ ( phi(q) + r * phi(a) ) - 3 ^ ( r * phi(a) ) = q * c = k'

Et d'autre part j (1 , 1 ,.... ..1) = j ( 1 , 1 , .....1, 1 , phi(q) + 1 ),  n uplet avec n = r * phi(a).

Comme la résolution de l'équation générale est k' * a = j * b

(q * c) * a = (q * a ) * b

En attribuant à  " b " la valeur " c ", on a une solution pour " a ".

Si " a " est pair, on ajustera éventuellement " r ". Si " a " est un multiple de 3 ^ d, on prendra c' = c * 3 ^ d.

 #4 - 18-03-2018 08:30:19

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

sytacuse élargi (2)

Ce qui me surprend beaucoup dans cette histoire, ce sont les grands pgcd qu'on voit assez souvent, entre d'une part la différence entre les puissances de 2 et les puissances de 3 (ce que j'ai appelé k), et d'autre part part la sommation des n termes que j'ai appelée " j " (Soit k * a = j * b )

Par exemple, lorsque a0 = 41 et b = 23, on trouve une boucle de longueur 26.

On a alors :
k= 23 * 271.922.921.473
j = 41 * 271.922.921.473

Ou encore a0 = 235 , b =61 et pgcd = 611 704 588 814 220 001

Alors que dans le même temps on n'arrive pas à obtenir avec ce petit k = 2^8 - 3^5 = 13, un j qui soit multiple de 13, ce qui infirmerait la conjecture.

Je soupçonne que ces pgcd monstrueux ne sont pas dûs au hasard, mais à une raison bien masquée. Trouver la raison de ces pgcd monstrueux permettrait de bien avancer dans la conjecture.

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

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