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 - 27-06-2020 09:13:02

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

DDes carrés de carrés de carrés...

Bonjour @ tous.

Soit m de N et la suite définie par : x0 = m/3 et x(n+1) = xn * [xn] ( []: partie entière )

Pour quelles valeurs initiales la suite donne des nombres entiers ?

Ce n'est pas simple.....


Bonne recherche.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 27-06-2020 16:18:02

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1492
Lieu: Coutiches

Des carrés d carrés de carrés...

bonjour nodgim,

J'ai quelques questions sur la question...

1) Le n de n/3 et celui de x(n+1) ne font pas référence au même n si ?

2) La suite ne doit-elle donner que des nombres entiers ou juste en donner à partir d'un certain rang ?

3) Pour prendre un exemple : Pour n=7 :
x0 = 7/3
x1 = 7/3*2 = 14/3 ( = 4,...)
x2 = 14/3 * 4 = 56/3 ( = 18,...)
x3 = 56/3 * 18 = 336, rang à partir duquel les termes de la suite seront entiers.

Et donc on cherche pour quelle valeur de x0 on fini par retrouver des entiers, c'est bien ça ?

 #3 - 27-06-2020 18:01:12

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

Des carrés de carrés dee carrés...

Salut Golgot59,

J'ai copié tes questions et y ai répondu, comme ça tout le monde sera au même niveau.

bonjour nodgim,

J'ai quelques questions sur la question...

1) Le n de n/3 et celui de x(n+1) ne font pas référence au même n si ?

Réponse :CORRECTION FAITE à l'énoncé.

2) La suite ne doit-elle donner que des nombres entiers ou juste en donner à partir d'un certain rang ?

Réponse : JUSTE en donner à partir d'un certain rang.



3) Pour prendre un exemple : Pour n=7 :
x0 = 7/3
x1 = 7/3*2 = 14/3 ( = 4,...)
x2 = 14/3 * 4 = 56/3 ( = 18,...)
x3 = 56/3 * 18 = 336, rang à partir duquel les termes de la suite seront entiers.

Et donc on cherche pour quelle valeur de x0 on fini par retrouver des entiers, c'est bien ça ?

Réponse: OUI !

 #4 - 28-06-2020 17:26:14

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

Des carrés d carrés de carrés...

Salut, un début de réflection smile

On note [latex]\left\{\cdot\right\}[/latex] la fonction partie fractionnaire.

Par définition [latex]X_n=X_{n-1}\lfloor X_{n-1}\rfloor=X_0\prod_{i=0}^{n-1}\lfloor X_i\rfloor[/latex].

Donc [latex]\left\{X_n\right\}=\left\{\left\{X_0\right\}\prod_{i=0}^{n-1}\lfloor X_i\rfloor\right\}[/latex].

En appliquant le théorème de la division euclidienne on peut écrire que [latex]m=3q+r[/latex] avec [latex](r,q)\in\mathbb{N}^2[/latex] et [latex]r<3[/latex].

Par conséquent [latex]\left\{X_n\right\}=\left\{\frac{r}{3}\prod_{i=0}^{n-1}\lfloor X_i\rfloor\right\}[/latex].

La suite génère des entiers à partir du plus petit rang [latex]n[/latex] vérifiant [latex]\left\{X_n\right\}=0\Leftrightarrow\frac{r}{3}\prod_{i=0}^{n-1}\lfloor X_i\rfloor\in\mathbb{N}\Leftrightarrow\lfloor X_{n-1}\rfloor\mod 3 = 0[/latex].

A mon avis expliciter cette condition en fonction de [latex]m[/latex] n'a rien d'évident à part pour quelques cas particuliers. A suivre ...

 #5 - 28-06-2020 18:35:00

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

Dees carrés de carrés de carrés...

@ Sydre : je ne suis pas convaincu par ta 1ère expression équivalente....

@ Tous : Le but n'est pas de chercher à partir de quel rang la suite donnera des entiers ( cet aspect ne me semble pas accessible....) mais bien de savoir si fatalement la suite donnera des entiers.

 #6 - 28-06-2020 19:47:53

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

Des carrs de carrés de carrés...

Tu veux parler de [latex]\left\{X_n\right\}=0\Leftrightarrow\frac{r}{3}\prod_{i=0}^{n-1}\lfloor X_i\rfloor\in\mathbb{N}[/latex] ?

J'avoue ne pas comprendre ce qui te chiffonne : si la partie fractionnaire d'un nombre est nulle c'est bien qu'il est entier ?

 #7 - 29-06-2020 12:32:21

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1657

Des carrés de carrés de crrés...

A part 4 et 5, je n'en ai pas trouvé d'autres pour l'instant.
Ca ne prouve rien et c'est peut-être faux du coup, mais enfin c'est ce que me dit mon code smile

 #8 - 29-06-2020 12:54:26

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1657

Des carrés de carrés de carrés....

Ma partie "cerveau" - maintenant que mon code a terminé de tourner.

Les nombres de la forme 3n passent (trivial) du premier coup
Les nombres de la forme 9n+1 et 9n+2 passent du second coup
Les nombres de la forme 27n+14, 22, 25, 26 passent du troisième coup.
Autrement dit, il existe pour un modulo 3^k donné, tout converge vers un entier en maximum k itérations, sauf pour 2^k valeurs parmi les 3^k

Démonstration : par récurrence.
J'ai 2^k cas non convergents parmis 3^k, et donc (3^k - 2^k) cas convergents.
En considérant l'exposant k+1
* j'obtiens 3*(3^k - 2^k) cas convergents à partir de mon résultat précédent
* et pour les 2^k cas non-convergents, j'obtiens 3 nouveaux cas pour chacun, avec 3 résultats différents modulo 3 => 2^k nouveaux cas convergents, et 2*2^k cas non convergents
Au total : 3*(3^k - 2^k) + 2^k = 3^(k+1) - 2^(k+1) cas convergents; et 2^(k+1) cas non convergents


ex: k=1 => 0 mod 3 passe en un coup, 1 et 2 non

k=2 => 0, 1, 2, 3, 6 mod 9 passent en un ou deux coups, mais 4,5, 7 et 8 non
Le 1 mod 9 est ajouté depuis 1 mod 3, le 2 mod 9 est ajouté depuis 2 mod 3
4 ou 7 mod 9 viennent aussi de 1 mod 3 mais donnent des résultats avec 1/3 ou 2/3, idem pour 5 et 8 mod 9 par rapport à 2 mod 3

k=3 => 0, 1, 2, 3, 6, 9, 10, 11, 12, 14, 15, 18, 19, 20, 21, 22, 24, 25, 26 passent en max 3 coups, mais 4, 5, 7, 8, 13, 16, 17 et 23 non
22 => vient de 4 mod 9
14 => vient de 5 mod 9
25 => vient de 7 mod 9
26 => vient de 8 mod 9
etc...

Du coup, le ratio des nombres "invalides en au plus k itérations" est (2/3)^k, et il tendrait donc vers 0. Ce qui, au final, ne prouve qu'une chose : c'est toujours le cas sauf en un nombre fini de points.

 #9 - 29-06-2020 13:06:10

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1657

Des carrés de carrés de carrés....

Une dernière chose : je viens de changer mon code pour sortir les "pics" en terme de nombre d'itérations et ça m'a permis de tomber sur un Sloane : A087663
Et surtout, la série associée :  http://oeis.org/A087666

It is conjectured that an integer is always reached if the initial value n/3 is >= 2.

 #10 - 29-06-2020 16:31:19

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

Des carrés de carés de carrés...

@ Sydre : pardon, c'est sur ta toute première équation que je renâcle.

@ Scarta : D'accord avec toi sur l'analyse, notamment sur la finitude du nombre des exceptions . La référence à OEIS, je ne la connaissais pas. Celle-ci parle seulement d'une conjecture. Il faudrait aller plus loin....

 #11 - 29-06-2020 17:04:52

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1657

des carrés fe carrés de carrés...

C'est un principe chez moi de ne pas chercher plus loin que ce qui n'est pas démontré sur OEIS smile

Bon sans rire ok mais ça va être coton - et faudra penser à laisser un message à Sloane ensuite pour qu'il mette à jour la description si effectivement tu as une démo smile

D'ailleurs, y'a un papier de Sloane lui-même là dessus j'ai vu
http://neilsloane.com/doc/apsq.pdf

Edit : d'un autre côté, le papier prétend que " Showing that this “exceptional set” of starting values which fail to reach integers is in fact empty (or even finite) appears to be a difficult problem".
Pour la finitude j'ai pas eu l'impression que c'était compliqué, ou alors ma preuve est bancale - je sais pas où exactement, du coup il faudrait que je regarde son papier plus en détail...

 #12 - 29-06-2020 18:24:22

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

Des carrés de carrs de carrés...

Sauf erreur c'est direct par récurrence :

[latex]X_n=X_{n-1}\lfloor X_{n-1}\rfloor=X_{n-2}\lfloor X_{n-2}\rfloor\lfloor X_{n-1}\rfloor=X_{n-3}\lfloor X_{n-3}\rfloor\lfloor X_{n-2}\rfloor\lfloor X_{n-1}\rfloor=\ldots=X_0\prod_{i=0}^{n-1}\lfloor X_i\rfloor[/latex].

 #13 - 29-06-2020 19:18:44

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

Des carrés de carrsé de carrés...

@ Sydre : Ah vrai ! Désolé, je n'y croyais au 1er regard sad

Du coup, ça te fait avancer ?

 #14 - 30-06-2020 11:52:48

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 393

des carréq de carrés de carrés...

Bonjour,
On voit rapidement que 4 et 5 bouclent.
Les multiples de 3 sont des solutions évidentes. (deviennent entiers en 0 étapes)
Les entiers congrus à 1 ou 2 modulo 9 deviennent entiers en 1 étape. (et c'est les seuls)

9n+4 devient à l'étape suivante (9n+4)(3n+1), ce qui est congru à 12n+4, ou encore 3n+4 modulo 9. Si n est congru à 2 modulo 3, alors 3n+4 est congru à 1 modulo 9. Posons n = 3m+2.
Donc 9(3m+2)+4 =27m + 22 devient entier en 2 étapes.
De même, (9n+5)(3n+1), congru à 15n+5, soit 6n+5. Si n congru à 1 modulo 3, alors 6n+5 est congru à 2 modulo 9. 9(3m+1)+5 = 27m+14 (2 étapes)
De même, (9n+7)(3n+2) => 21n+14 => 3n+14 => n = 3m+2 => 9(3m+2)+7 => 27m + 25 résolu en 2 étapes
Enfin, (9n+8)(3n+2) => 24n+16 => 6n+16 => n = 3m+2 => 9(3m+2)+8 => 27m + 26 résolu en 2 étapes.

Soit c(n) le nombre d'étapes à partir de n.

Récapitulons ce que l'on a déjà trouvé :
n : c(27m+n)
1 : 1
2 : 1
3 : 0
4 : ?
5 : ?
6 : 0
7 : ?
8 : ?
9 : 0
10 : 1
11 : 1
12 : 0
13 : ?
14 : 2
15 : 0
16 : ?
17 : ?
18 : 0
19 : 1
20 : 1
21 : 0
22 : 2
23 : ?
24 : 0
25 : 2
26 : 2

En continuant sur le même principe, la proportion de classes connues ne pourra faire qu'augmenter, mais on conservera toujours un nombre d'inconnues (qui augmentera selon 2^n, si je ne me trompe pas)
Apparemment, c'est une conjecture :
https://oeis.org/A083863
J'ai cherché l'OEIS car Scarta l'a fait (non mais oh ! tongue)
Je continue à chercher, mais pour l'instant, je n'ai pas plus d'idée pour lever la conjecture (l'as-tu fait?)

 #15 - 30-06-2020 16:04:46

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

des catrés de carrés de carrés...

@ Caduk : c'est un bon début, tu pourrais prolonger l'idée des racines, et tenter d'en dénombrer la proportion sur N.

@ Sydre : le papier de Sloane est long ! Ce que j'ai vu est plus simple, c'est la même chose que toi, j'ai juste gratté ce qu'on pouvait en tirer.

 #16 - 30-06-2020 19:51:06

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 393

Des carrés de carrés de ccarrés...

On trouve que la proportion de classes d'équivalence non fixées est de (2/3)^n pour les entiers modulo  3^n.
Ce n'est pas un résultat évident. On voit facilement que chaque classe non fixée en fournit 3 autres à l'itération suivante. On peut montrer par récurrence qu'elle en fixe exactement une, avec pour hypothèse de récurrence que les classes résolues en k itérations (données modulo 3^(k+1) ) sont uniques modulo 3^k.
Le nombre de classes non fixées double donc à chaque fois, et on a donc 2^n classes non fixées modulo 3^n.
La proportion tends donc vite vers 0, mais ça ne prouve rien de global.
Si on suppose qu'il existe un autre x0 infini autre que 4 et 5, sa suite comporte de l'ordre de log(n) autre nombres infinis. Ce n'est donc pas du tout en désaccord avec le résultat asymptotique obtenu. Je ne pense pas que l'on puisse conclure directement à partir de cette proportion, il faut encore que je creuse.

 #17 - 01-07-2020 08:35:14

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

Des carrés de crrés de carrés...

@ Caduk : un x0 infini ? Tu peux développer ? C'est important.

 #18 - 01-07-2020 15:45:28

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

Des carrés de carés de carrés...

Aïe !
En voulant rédiger proprement ma démo, je me suis rendu compte m'être planté.....
J'en suis donc au même niveau que ce qui a été dit jusqu'à maintenant. Juste une nuance tout de même, mais qui ne change pas grand chose au final. S'il y avait une exception, hé bien il y en aurait une infinité, puisque les carrés successifs d'un nombre primitif seraient tous des exceptions. Mais ça ne change rien, puisque cette infinité d'exceptions est de densité nulle.

J'anticipe à maintenant la fin de l'énigme.

 #19 - 05-07-2020 00:38:38

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1657

des carrés de carrés de caerés...

Fermat partait pareil, il a fallut juste 400 ans, le développement des courbes elliptiques et la conjecture de Shimura-Taniyama-Weil pour y arriver.

Peut-être qu’en 2420 quelqu’un aura la démo de la conjecture de nodgim big_smile

 #20 - 05-07-2020 17:02:30

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

des carrés de carrés de careés...

@ Scarta : ça ne m'arrive pas souvent sur ce forum, mais ici je ne suis pas le concepteur de cette question.

 

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 : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

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