Une explication au 1 final
Bonjour,
Je reviens avec de nouvelles informations puisque je suis parvenu a expliquer ce qui provoque l'apparition d'un terme égal à 1 dans une suite définie par kn+1, cette fois-ci sans aucun apriorisme mais comme conséquence de la valeur particulière d'une somme de fractions. J'explique également l'origine de la parité de l'exposant d'un diviseur.
Il s'agit toujours du même document revu, corrigé et complété depuis deux ans, si bien que ceux qui connaissent déjà le concept de suite impaire symbolique peuvent débuter sa lecture à la page 3.
PS : conséquence de ce qui précède, le lien vers ce document est le même que dans le sujet "Suite impaire symbolique de Collatz", lequel est du coup obsolète.
Wilfrid
Je reviens avec de nouvelles informations puisque je suis parvenu a expliquer ce qui provoque l'apparition d'un terme égal à 1 dans une suite définie par kn+1, cette fois-ci sans aucun apriorisme mais comme conséquence de la valeur particulière d'une somme de fractions. J'explique également l'origine de la parité de l'exposant d'un diviseur.
Il s'agit toujours du même document revu, corrigé et complété depuis deux ans, si bien que ceux qui connaissent déjà le concept de suite impaire symbolique peuvent débuter sa lecture à la page 3.
PS : conséquence de ce qui précède, le lien vers ce document est le même que dans le sujet "Suite impaire symbolique de Collatz", lequel est du coup obsolète.
Wilfrid
Réponses
-
Dommage, parce que pour $k \neq 3$, ce résultat est faux en général (par exemple pour $k=5$ et $u_0=5$)
-
Tout à fait, et d'ailleurs mon document se termine par cette phrase : "Mais c'est sans doute possible avec k > 3".
J'ai trouvé la formule des prédécesseurs il y a environ trois ans, mais sans noter le cheminement qui m'y avait conduit, si bien que je suis pour l'instant incapable de l'étendre à tout k. Si on y parvient, alors il sera sans doute possible de savoir pourquoi une suite basée sur kn+1 avec k > 3 peut croître indéfiniment. -
Ceux qui ont lu mon document savent que (9 - n mod 6) donne 6, 4 ou 8 (avec n impair), 6 lorsque n est un multiple de 3. Comme il n'en existe aucun dans une suite de Collatz (hormis comme 1er terme), on n'en a tout simplement pas besoin, si bien que 4 et 8 suffisent. J'envisage de modifier mon document en conséquence pour l'accorder avec ce qui suit, si je parviens à une formule générale valable pour tout k.
Attention avec les suites 7n+1, il existe toute une flopée d'entiers impairs ne possédant aucun prédécesseur, et pas seulement les multiples de 7. Exemple : 3, 5, 7, 13, 17, 19, 21, 27, 31, 33, 35, 41, 45, 47, 49, 55, 59, 61, 63, 69, 73, 75, 77, 83, 87, 89 … Dans ce cas la formule renvoie une fraction (du moins dans Mathematica).
4 (3 - n mod 3) = 4 ou 8. Concernant la formule pour une suite 7n+1, 2 c (c - 7) + 28 = 8, 4 ou 16. J'ai cherché une expression du même type que la précédente afin d'unifier les deux formules, mais en vain. Par exemple une expression dans laquelle apparaîtrait 7 - n mod 7. Quelqu'un aurait-il une idée ? -
Dans mon post précédent j'ai ajouté la formule des prédécesseurs pour une suite 5n+1.
A l'intention de ceux qui voudraient trouver une formule universelle, voici les données, triées de deux manières différentes. Je doute cependant que ce soit possible, elles sont trop disparates :
Je rappelle que r est le rang d'un terme dans la liste des prédécesseurs de n. Il peut donc prendre toutes les valeurs entières > 0.
On remarque que k = 7 représente un cas particulier. On se serait en effet attendu à ce que c ait les valeurs 1, 2, 3, 4, 5, 6, ce qui n'est pas le cas. Ça s'explique par le fait que, comme je le disais dans mon précédent post, un grand nombre d'entiers impairs ne peuvent pas figurer dans une suite 7n+1 faute de prédécesseur. -
J'ai souvent du mal de comprendre pourquoi les solutions les plus simples ne viennent pas immédiatement à l'esprit. Dans le cas de la formule des prédécesseurs il suffisait de procéder comme suit :
- Prendre n'importe quel entier impair non multiple de 3 et construire la suite de ses prédécesseurs par programmation, en testant tous les entiers impairs jusqu'à en obtenir 6 ou 8.
- Analyser cette suite et tenter de trouver une relation de récurrence.
- Si ça fonctionne, calculer sa forme explicite.
La méthode paraît si simple, évidente et directe que je suis à peu près persuadé de retrouver cette formule dans quelque antique ouvrage consacré aux suites de Collatz (pour peu bien sûr que je m'intéresse à cette littérature et que je fasse provision d'aspirine). -
Voici une formule qui s'oppose à l'idée qu'une suite de Collatz puisse croître indéfiniment. Il existe une infinité de séquences croissantes (qui provoquent les pics observés dans un graphe), mais leur longueur est finie. Cette formule permet de calculer le premier terme d'une séquence croissante de longueur égale à q+1 termes :
Iq(x) = 2q+1 ( 3 (2 x - 1) - 2 (-1)q ) - 1 , q et x > 0. Le premier caractère est un iota majuscule
Exemple : I7(3) = 4351, ce qui donne le début de la suite impaire 4351, 6527, 9791, 14687, 22031, 33047, 49571, 74357, 6971, ...
Il y a bien q+1 = 8 termes croissants.
La question est de savoir si, lorsque q tend vers l'infini, la suite n'atteindra jamais 1. Qu'en pensent les mathématiciens ?
Voir détails dans mon document, section "Étude du graphe d'une suite impaire" au bas de la page 8. J'y ai ajouté un lien vers un notebook Mathematica contenant toutes les formules et fonctions utilisées dans le document. -
Hey Wilfrid, ça fait longtemps.....
Dans l'idée d'une suite croissant indéfiniment, il n'est nullement question de croissance continue.
Il est effectivement connu que toute "portion" de croissance continue démarre avec $a\cdot 2^n-1$ et croît jusqu'à $a\cdot 3^n-1$ en exactement $n$ étapes (note: $a$ impair et $a\cdot 3^n-1$ est toujours pair), mais rien n'empêche qu'après ces $n$ étapes et une division par 1 ou quelques facteurs de $2$, la suite reparte de plus belles, selon le même principe....
Sinon pour les "prédécesseurs" de 31 (ou tout autre nombre), il est aussi connu que l'on peut les trouver avec $p_n=4\cdot p_{n-1}+1$ (ex: 165 = 4*41+1)
En reprenant mon message ici: http://www.les-mathematiques.net/phorum/read.php?43,1505780,1510790#msg-1510790 , on peut le voir simplement sur les enfants (prédécesseurs) de $6i+1$ (ex:31): premier enfant $8i+1$ (ex:41), le second $(8i+1)\cdot 4+1=32i+5$ (ex:165), ....
(et idem pour les enfants de $6i+5$).
Note: en utilisant $1\pmod 6$ et $5\pmod 6$ plutôt que $1\pmod 3$ et $2\pmod 3$ tu élimines les multiples de 2 et 3 au passage. -
Salut Collag3n,
Merci d'avoir pris le temps de rompre mon monologue ! :-)Il est effectivement connu que toute "portion" de croissance continue démarre avec a·2n-1 et croît jusqu'à a·3n-1 en exactement n étapes (note: a impair et a·3n-1 est toujours pair)
Je mets ce qui suit en texte medium à cause de la notation indicée.
[size=medium]La séquence croissante possède n termes, donc croît sur n-1 étapes (c'était juste pour pinailler). Appelons t1, t2, ..., tn les termes successifs de la séquence. ti+1 = (3 ti + 1) / 21 jusqu'au terme tn. Mais si tu poursuis au-delà, le terme tn+1 sera le résultat de (3 tn + 1) / 21, alors que le diviseur est cette fois-ci >= 22, ce qui d'ailleurs constitue la raison pour laquelle le successeur de tn, dans la suite impaire, est plus petit que lui.[/size]
Exemple : avec a = 11 et n = 7 on obtient la séquence 1407, 2111, 3167, 4751, 7127, 10691, 16037, 24056, alors que le successeur de 16037 dans la suite est 3007. (3 x 16037 +1) étant divisible par 24, on obtient 3007 en divisant 24056 trois fois supplémentaires par 2.
En réalité, la séquence ne croît pas jusqu'à a 3n - 1 mais jusqu'à 2 a 3n-1 - 1.
Pour répondre globalement au sens de ton post, je me doute bien que certains de mes résultats sont déjà connus sous une forme ou une autre, mon ignorance venant de ce que je n'ai rien lu sur le problème 3n+1 en dehors de quelques articles en ligne. Mais d'autres ne le sont pas, en particulier la somme de fractions systématiquement égale à 3 x (l'avant dernier terme d'une suite) + 1, qui à elle seule devrait suffire à démontrer que toutes les suites se terminent par 1. Et je continuerai de le penser jusqu'à ce que quelqu'un me démontre que j'ai tort. -
Oui, si on ne regarde que les impairs, on a effectivement $n-1$ steps et on s'arrête à $2\cdot a\cdot 3^{n-1}-1$. C'est pourquoi j'ai précisé qu'en $n$ steps on arrive sur $a3^n-1$ qui est pair (on ne le voit donc pas réellement dans la suite d'impair, vu qu'il doit encore être divisé au moins une fois par 2). Je trouve juste la formule plus simple et plus jolie à présenter sous cette forme.
-
Le problème est justement là : on connaît à l'avance le diviseur de tous les termes d'une séquence croissante jusqu'à l'avant-dernier, 21, mais on n'a aucune idée de celui du dernier terme. Il est de ce fait hautement recommandé de fuir a 3n - 1 comme la peste.
Je reviens sur ton premier post après avoir pris le temps d'y réfléchir. S'il est vrai que la relation de récurrence fonctionne dans tous les cas, par contre le calcul du premier prédécesseur de n n'est pas le même selon que ce dernier est de la forme 6i + 1 ou 6i + 5 (auxquels je préfère 6i + 1 et 6i - 1) :
6i + 1 -> 8i + 1
6i + 5 -> 4i + 3
6i -1 -> 4i - 1
Pour éviter de calculer la suite des prédécesseurs en utilisant la formule de récurrence, il est plus simple d'utiliser sa forme explicite, qui elle aussi varie :
(4r (6i + 1) - 1) / 3
(4r (6i + 5) - 2) / 6
(4r (6i - 1) - 2) / 6
où r est le rang d'un prédécesseur dans sa suite. On en revient finalement à la formule que j'ai postée ci-dessus et qui a le mérite d'être universelle, à savoir (4r n / n mod 3 - 1) / 3.
Pourrais-tu m'expliquer concrètement, par un exemple numérique, comment tu élimines les multiples de 3 dans le calcul des prédécesseurs ? -
A mon avis, le nombre de facteurs de 2 de $a\cdot 3^n-1$ doit probablement être prévisible. Par exemple, $3^n-1$ a deux facteurs de 2 de plus que $n$ (ou 1 si $n$ n'en a pas).
A noter qu'on sait que $a\cdot2^n-1$ conduit toujours à $a\cdot3^n-1$ en $2n$ étapes (en comptant les divisions par 2 aussi comme des étapes), on sait aussi que $a\cdot 2048^n-61$ conduit toujours à $a\cdot 2187^n-61$ en $18n$ étapes.
On sait aussi que $a\cdot8^n-5$ conduit toujours à $a\cdot9^n-5$,
que $a\cdot4^n+1$ conduit toujours à $a\cdot3^n+1$,
que $a\cdot8^n-7$ conduit toujours à $a\cdot9^n-7$,
que $a\cdot2048^n-25$ conduit toujours à $a\cdot2187^n-25$,
que $a\cdot2048^n-37$ conduit toujours à $a\cdot2187^n-37$,
que $a\cdot2048^n-55$ conduit toujours à $a\cdot2187^n-55$,
que $a\cdot2048^n-41$ conduit toujours à $a\cdot2187^n-41$,
que $a\cdot2048^n-17$ conduit toujours à $a\cdot2187^n-17$,
que $a\cdot2048^n-91$ conduit toujours à $a\cdot2187^n-91$ -
Je n'ai pas de solution. Voici le principe de fonctionnement d'une suite impaire :
- Les entiers de la forme 6x - 1 (ou n mod 3 = 2) ont un prédécesseur plus petit qu'eux.
- Les entiers de la forme 6x + 1 (ou n mod 3 = 1) ont des prédécesseurs tous plus grands qu'eux.
- La suite est fondamentalement constituée d'une succession plus ou moins longue de séquences croissantes reliées par le dernier terme de l'une à l'un des termes de la suivante.
- Lorsqu'elle ne rencontre plus aucune séquence croissante, la suite descend vers 1, parce qu'elle tend toujours à décroître. De ce fait, le sommet le plus important est le dernier (pourquoi n'y a-t-il plus de séquence croissante après lui ?).
Le terme initial d'une séquence croissante (points rouges les plus bas dans l'illustration) se calcule ainsi :
[size=medium]m = 3 (2x - 1) - 2 (-1)q
Iq(x) = 2q+1 m - 1[/size] , q et x > 0
Elle compte q+1 termes. Le dernier est :
[size=medium]nq+1 = 2 . 3q m - 1[/size]
On sait donc que le dernier terme + 1 est divisible par 2 et par 3q, mais ça ne permet pas d'en déduire son diviseur sous forme d'exposant de 2. Si quelqu'un a la solution je suis preneur. :-)
EDIT : j'ai oublié de préciser que le terme initial d'une séquence croissante peut être un multiple de 3, visible si c'est le premier terme de la suite, ou invisible dans le cas contraire (il équivaut alors à un point rouge fantôme dans l'illustration). Ce sont les multiples de 3 de la forme 12 x - 9. -
@Collag3n,
Dans un autre sujet tu évoquais le problème de la construction d'une suite impaire au moyen des exposants de ses diviseurs, en partant bien sûr de 1, évoquant au passage la nécessité qu'une suite d'exposants soit cohérente (si elle est aléatoire elle ne fonctionnera pas, sauf par miracle). Je ne sais pas si tu as trouvé une solution, ni même si tu t'intéresses toujours à la question, mais voici un moyen extrêmement simple d'obtenir la parité des exposants d'une suite. On procède en trois étapes :- Prendre une suite quelconque, par exemple 33, 25, 19, 29, 11, 17, 13, 5, 1. Incrémenter chaque terme puis le diviser par 6, ce qui donne 17/3, 13/3, 10/3, 5, 2, 3, 7/3, 1, 1/3
- Remplacer les entiers par i (impair) et les rationnels par p (pair).
- Supprimer la première lettre de la liste résultante. On obtient p, p, i, i, i, p, i, p (les exposants réels sont 2, 2, 1, 3, 1, 2, 3, 4)
p, p, i, i, i, p, i, 4 --> 5, 1
A partir de là les choses se compliquent, parce que l'exposant impair qui doit précéder 4 pourra avoir trois effets : 1) produire un multiple de 3 ; 2) produire un terme dont le prédécesseur aura pour diviseur un exposant impair de 2 ; 3) idem ... un exposant pair de 2. Il est donc nécessaire de prendre en compte les deux lettres précédentes, et non pas une seule, et pour cela on doit créer une fonction à laquelle on passe le premier terme de la suite résultante (ici 5) et qui renvoie les choix possibles :
p, p, i, i, i, p, i, 4 --> 5, 1 | m3 <-- (1, 7, 13), i <-- (5, 11, 17), p <-- (3, 9, 15)
Comme le i en cours est précédé de p, on doit choisir 3, 9 ou 15. Prenons 9 :
p, p, i, i, i, p, 9, 4 --> 853, 5, 1 | m3 <-- (2, 8, 14), i <-- (6, 12, 18), p <-- (4, 10, 16)
Le p en cours est précédé de i, alors on choisit 6 :
p, p, i, i, i, 6, 9, 4 --> 18197, 853, 5, 1 | m3 <-- (3, 9, 15), i <-- (1, 7, 13), p <-- (5, 11, 17)
Etc. On arrive au remplacement de la dernière lettre (ou plutôt la première) :
p, 2, 3, 1, 1, 6, 9, 4 --> 28753, 21565, 8087, 12131, 18197, 853, 5, 1 | m3 <-- (2, 8, 14), i <-- (6, 12, 18), p <-- (4, 10, 16)
Étant donné que cette lettre n'est précédée d'aucune autre, on peut choisir n'importe quel exposant. Prenons 2 pour faire débuter la suite par un multiple de 3 :
2, 2, 3, 1, 1, 6, 9, 4 --> 38337, 28753, 21565, 8087, 12131, 18197, 853, 5, 1. La parité de chaque exposant dans la suite de 38337 est bien la même que dans la suite de 33, à savoir p, p, i, i, i, p, i, p.
Si on n'essaie pas de reproduire un modèle mais qu'on tente plutôt de créer un motif particulier de i et de p, il y a fort à craindre que ce soit difficile, ou alors il faudra s'y reprendre à de nombreuses fois. Par exemple, si on avait pris 8 au lieu de 4 pour le premier p, on n'aurait pas pu le faire précéder d'un exposant impair. Il existe donc peut-être des motifs faisables et d'autres qui ne le sont pas, mais ce n'est qu'une hypothèse. -
Je m'intéresse toujours à la question, mais ça fait plusieurs semaines que je n'ai plus eu l'occasion de faire des maths. J'aimerais trouver le temps de creuser ces deux sujets (qui sont liés à ce problème):
https://math.stackexchange.com/questions/2539458/n-0-to-n-i-and-n-0k-cdot2j-ton-ik-cdot3i-same-glide
https://mathoverflow.net/questions/288807/a-problem-involving-the-inverse-collatz-map -
Je ne suis pas d'accord avec ton énoncé du problème sur stackexchange :
Voici ma propre approche :
Ce qui pose problème est que tu fais apparaître m1 au dénominateur de chaque fraction, alors qu'il ne figure que dans la première. De plus, dans la dernière d'entre elles tu poses 30 / 2m1, alors qu'en réalité il s'agit de 30 / 2mi.
J'avais déjà proposé cette approche en juillet dernier, et c'est d'ailleurs ce qui m'avait conduit à ne plus calculer séparément n1, n2, ... mais à effectuer un seul calcul global (celui de la page 1 de mon document) afin d'obtenir directement l'expression du dernier terme d'une suite, c'est-à-dire ni. -
Effectivement, petite erreur d'énoncé. J'ai l'habitude d'utiliser $n_0$ dans l'autre sens (plus proche de 1 sur l'arbre Collatz, et même souvent $n_0=1$ comme sur ce forum ci). ça n'a pas beaucoup d'importance pour le problème soulevé.
-
Euh ... si, ça a une énorme importance, parce que l'expression de ni est complètement fausse. Si tu utilises des valeurs numériques le résultat sera erroné.
Tu fais disparaître tout à tour mi, mi-1, mi-2, ... à chaque nouvelle fraction, alors que c'est m1, m2, m3, ... qui disparaissent successivement. C'est la raison pour laquelle tu te retrouves avec une dernière fraction égale à 30 / 2m1, alors qu'à ce moment-là il ne reste que 30 / 2mi. Tu n'obtiendra jamais une valeur juste de ni dans ces conditions. -
Je dis que ça n'a aucune importance parce que ce n'est qu'une erreur d'indice dans l'énoncé qui lui même n'avait pour but qu'un mise en situation (pour ceux qui découvrent Collatz). C'est bien simple, deux ligne plus loin je remplace l'ensemble par $\delta$ pour simplifier.
Les exemples numériques donnés sont eux tout à fait corrects et basé sur la "bonne formule" -
Collag3n a écrit:Les exemples numériques donnés sont eux tout à fait corrects et basé sur la "bonne formule"
Je reprends l'exemple numérique que tu fournis sur la page de stackexchange (après avoir fini par comprendre comment poster en LaTex) : $$
n_6=\frac{3^6}{2^{10}}\cdot n_0+\frac{3^5}{2^{10}}+\frac{3^4}{2^9}+\frac{3^3}{2^8}+\frac{3^2}{2^7}+\frac{3^1}{2^5}+\frac{3^0}{2^2}
$$ Pour obtenir cette somme de fractions on doit partir de la suite d'exposants 0, 1, 1, 1, 2, 3, 2. On l'inverse et on calcule sa somme cumulée : 2, 5, 7, 8, 9, 10, 10. Le problème est que l'exposant du diviseur de 36 est le même que celui de 35, ce qui est impossible. C'est d'ailleurs pourquoi j'ai dû faire débuter la suite d'exposants par 0, ce qui n'arrive jamais dans des conditions normales parce qu'aucun terme d'une suite n'a 20 pour diviseur.
Il y a quelque chose qui m'échappe totalement dans ton raisonnement. Pourrais-tu expliquer d'où sort cette somme de fractions ? -
Je ne suis pas sur de comprendre
Lorsqu'on part d'un nombre $n_0$ et qu'on applique successivement la formule $n_{i+1}=\frac{3\cdot n_i +1}{2^{m_i}}$ pour remonter jusqu'à 1 (dans mon exemple, je m'arrête à $n_6$), les deux premiers termes ont toujours le même diviseur:
$n_1 = \frac{3}{2^{m_1}}\cdot n_0 + \frac{1}{2^{m_1}}$
$n_2 = \frac{3}{2^{m_2}}\cdot n_1 + \frac{1}{2^{m_2}} = \frac{3^2}{2^{m_1+m_2}}\cdot n_0+\frac{3^1}{2^{m_1+m_2}}+\frac{3^0}{2^{m_2}}$
...
e.g. $13 = \frac{3^3}{2^4}\cdot 7+\frac{3^2}{2^4}+\frac{3^1}{2^3}+\frac{3^0}{2^2}$
Edit: Apparemment tu écris ça sous cette forme: $\frac{3^5\cdot(3\cdot n_0 +1)}{2^{m_1+m_2+...+m_i}}+...$ ce qui est équivalent à $\frac{3^6\cdot n_0 + 3^5}{2^{m_1+m_2+...+m_i}}+...$ ou $\frac{3^6}{2^{m_1+m_2+...+m_i}}\cdot n_0 + \frac{3^5}{2^{m_1+m_2+...+m_i}}+...$, mais c'est du pareil au même -
D'accord sur l'équivalence des deux formes d'écriture de la somme de fractions, ce qui élimine la nécessité d'introduire le diviseur 20. J'étais resté scotché à l'idée que ton calcul de ni étant faux, tu avais probablement reproduit cette erreur quelque part, et ceci d'autant plus que la somme de fractions en question, égale à n6, ne peut pas exister avec ces diviseurs. A moins, comme tu le proposes, que pour les besoins de la démonstration on admette l'existence de la suite $\frac{13}{3},7,11,17,13,5,1$, ce qui donnerait, après attribution à $\frac{13}{3}$ du diviseur 21
[size=x-large]$n_6=\frac{3^0}{2^4}+\frac{3^1}{2^7}+\frac{3^2}{2^9}+\frac{3^3}{2^{10}}+\frac{3^4}{2^{11}}+\frac{3^5 \left(\frac{3\ 13}{3}+1\right)}{2^{12}}=1$[/size]
Tu dis par ailleurs que n6 est le premier terme < n0. Dans ce cas, pourquoi ne pas faire le choix d'une séquence croissante n0, ..., n5 suivie de n6 < n0 ? Par exemple 2623, 3935, 5903, 8855, 13283, 19925, 467, ou encore 5695, 8543, 12815, 19223, 28835, 43253, 4055. -
n'importe quel exemple avec un $n_i<n_0$ (et $n_i$ premier $n$ inférieur à $n_0$ par définition d'un "Glide") aurrait fait l'affaire. L'important n'est pas la suite d'exposant, mais le fait que cette suite d'exposant est identique qu'on parte de $n_0$ ou de $n_0+k\cdot 2^j$, et surtout qu'il n'existe pas de démonstration ou de contre exemple où le "glide" en partant de $n_0+k\cdot 2^j$ serait différent de celui qu'on a en partant de $n_0$.
L'exemple choisi fonctionne probablement parce que le ratio $\frac{3^5}{2^8}$ est proche de 1 (Attention: C'est le ratio pour atteindre $n_5$, pas $n_6$ dont la fraction première est $\frac{3^6}{2^{10}}$), mais cela reste un exemple "fabriqué" (il utilise un rationel) puisqu'il n'existe pas d'exemple "réel" connu.
Note: la suite d'exposant et de fractions $n_6=\frac{3^6}{2^{10}}\cdot n_0+\frac{3^5}{2^{10}}+\frac{3^4}{2^9}+\frac{3^3}{2^8}+\frac{3^2}{2^7}+\frac{3^1}{2^5}+\frac{3^0}{2^2}
$, elle, existe bien (e.g.: $n_0=1711$ et $n_6=1219$) -
La suite de $\frac{13}{3}$ fonctionne tout simplement parce qu'au numérateur de la dernière fraction on a 3u (3 n0 + 1). Avec $\frac{13}{3}$ ça donne 13 + 1 = 14, dont le diviseur est 21, et 14 / 2 = 7. Ça revient donc à faire débuter la suite par 14 suivi de 7.
Je pense que ce principe devrait fonctionner avec tous les entiers pairs dont le diviseur est 21 soit 6, 10, 14, 18, ..., et le dernier est particulièrement intéressant parce que 18/2 = 9 étant un multiple de 3 il n'a pas de prédécesseur. La suite impaire de 9 a pour exposants 2, 1, 1, 2, 3, 4. Si on les fait précéder de 1 on obtient la suite $\frac{17}{3},9,7,11,17,13,5,1$ :
[size=large]$\frac{3^0}{2^4}+\frac{3^1}{2^7}+\frac{3^2}{2^9}+\frac{3^3}{2^{10}}+\frac{3^4}{2^{11}}+\frac{3^5}{2^{13}}+\frac{3^6 \left(\frac{3\ 17}{3}+1\right)}{2^{14}}=1$[/size] -
Bonjour
pour répondre à ta dernière question en fin de document :
tout simplement un vol I impair = $2^{n} - 1$ étant donné que ces vol ont : lorsque l'exposant $n$ tends vers + l'infini, une infinité de termes pairs et impairs en ascension constante...!
Bien sûr, au bout de la $n$ième itérations qui tends vers l'infini, il va se diviser par 2; mais comment prouves tu qu'il n'y aura pas une itération ayant un terme encore plus Haut....dans cette suite de Syracuse...Alors que dans ces types de vols de cette forme , il y a des itérations qui montent encore plus haut...que le $n$ ième termes...
Tu donnes un exemple avec un petit entier , ayant 200 termes en ascension et qu'est ce que tu fais du vol $2^{2001} - 1$
qui a 2001 termes pairs consécutifs et 2000 termes impairs consécutifs; soit un total de 4001 termes pairs et impairs en ascension constante ....et l'exposant $n = 2001$ est loin d'atteindre l'infini.....non ..?
Si tu prends comme exposant n = le dernier nombre premier de Mersenne , qui a plusieurs millions de chiffres , tu n'es pas près de compter le nombre d'ascensions consécutives et tu serra très très loin de l'océan de l'infini....Je plaisante...X:-( -
@LEG,
L'esprit humain éprouve autant de difficulté à se représenter un univers infini qu'une suite d'entiers impairs de longueur infinie. Pourtant il existe une différence notoire entre les deux : la seconde est bornée ; aussi bien son premier terme que le dernier sont calculables (les formules figurent d'ailleurs dans le document en question), même si aucun super-calculateur ne serait capable de gérer de tels nombres. Une suite bornée ne peut pas, par définition, être infinie, aussi longue qu'on désire qu'elle soit.
@Collag3n,Collag3n a écrit:Note: la suite d'exposants et de fractions $n_6=\frac{3^6}{2^{10}}\cdot n_0+\frac{3^5}{2^{10}}+\frac{3^4}{2^9}+\frac{3^3}{2^8}+\frac{3^2}{2^7}+\frac{3^1}{2^5}+\frac{3^0}{2^2}$, elle, existe bien (e.g.: n0=1711 et n6=1219)
D'accord, et bravo ! Ton algorithme de recherche a clairement mieux fonctionné que le mien, qui n'a pas été fichu de trouver la suite d'exposants 1, 1, 1, 2, 3, 2 parmi le premier million de suites impaires ! Après l'avoir modifié il a toutefois fini par cracher les bons résultats.
Dans un post précédent tu disais que les données que j'avais proposées pour trouver le Glide de n0 étaient "fabriquées". Je ne sais pas si tu faisais allusion au premier terme rationnel ou à l'utilisation de séquences croissantes. Dans le dernier cas, je te propose d'étudier la suite que voici. C'est celle de 1711 dans laquelle les séquences croissantes sont en rouge et les candidats au "Gliding" en vert. Les termes en gris sont ajoutés ; ils représentent la portion d'une séquence croissante qui n'appartient pas à la suite de 1711. Les barres verticales évitent de confondre en une seule deux séquences croissantes consécutives. Enfin, 167 est répété parce qu'il appartient à une séquence croissante tout en étant un Glide :
1711, 2567, 3851, 5777, 4333, 1083,1625, 1219, 1829, | 343, 515, 773, 145, 109, 27, 41, | 31, 47, 71, 107, 161, 121, 91, 137, | 103, 155, 233, | 175, 263, 395, 593, 445, 167, 111, 167, 251, 377, | 283, 425, | 319, 479, 719, 1079, 1619, 2429, 607, 911, 1367, 2051, 3077, 577, 433, 325, 61, 15, 23, 35, 53, 3, 5, 1
Ceci confirme ce que je disais plus haut, à savoir qu'une suite impaire est essentiellement composée de séquences croissantes (on a tendance à ne pas les remarquer parce que les plus fréquentes n'ont que deux termes). Sinon elle descendrait directement vers 1. Et surtout, ça confirme le fait qu'il faut en tenir compte dans les recherches sur les Glides, parce qu'ils leurs sont concomitants et que sans elles le Glide de toutes les suites serait le second terme.
La suite d'exposants 1, 1, 1, 2, 3, 2 dénote une séquence croissante de 4 termes dont le dernier est divisible par 22. Voici une méthode pour en trouver d'autres : on applique la formule $2^{q+1} \left(6 x-2 (-1)^q-3\right)-1$ dans laquelle on remplace q par 3 (puisque la longueur d'une séquence croissante est q + 1), ce qui donne $16 (6 x-1)-1$. En attribuant successivement à x les valeurs 1, 2, ..., 18 on obtient le terme initial de 18 séquences croissantes de 4 termes : 79, 175, 271, 367, 463, 559, 655, 751, 847, 943, 1039, 1135, 1231, 1327, 1423, 1519, 1615, 1711, le dernier étant justement 1711. Parmi eux il en existe cinq dont le Glide est n5 :
175, 263, 395, 593, 445, 167
847, 1271, 1907, 2861, 1073, 805
943, 1415, 2123, 3185, 2389, 7
1615, 2423, 3635, 5453, 2045, 767
1711, 2567, 3851, 5777, 4333, 1625
et un dont le Glide est n6 : 367, 551, 827, 1241, 931, 1397, 131. C'est le seul parmi les 18. Mais tu peux toujours essayer d'autres valeurs de x et de q. Tu peux également remplacer $-2 (-1)^q$ par $+2 (-1)^q$ afin d'obtenir des termes initiaux multiples de 3. -
Est-ce que suite finie te conviendrait ?
-
Par curiosité, j'aimerais comprendre l'objet que tu désignes par "suite de longueur infinie" ; sinon, nous jouons sur les mots.
Bruno -
LEG disait en substance qu'une suite impaire (ou vol impair) dont le premier terme est $2^n-1$ est croissante sur les $n$ premiers termes, et donc que lorsque $n$ tend vers l'infini la longueur de cette suite tend elle-même à devenir infinie, si bien qu'il existe vraisemblablement une suite dont la longueur est telle qu'elle ne redescendra jamais vers 1.
Je dois commencer par lever une ambigüité. Voici la suite de $2^7-1$ dans laquelle la séquence croissante est en rouge :
127, 191, 287, 431, 647, 971, 1457, 1093, 205, 77, 29, 11, 17, 13, 5, 1
Ce qui se passe après 1457, dernier terme de la séquence, n'a aucune importance. C'est la séquence initiale qui pourrait être de longueur infinie, pas la suite, ce qui pose un sérieux problème d'interprétation du concept de suite infinie, car aussi longue soit-elle elle dispose du moyen de redescendre vers 1.
Je reconnais que ma réponse n'ajoutait rien aux propos de LEG, puisque la séquence croissante de $2^n-1$ est par définition finie : on connaît son premier terme et sa longueur, donc on peut calculer son dernier terme (ce que j'appelais ses bornes).
Ce qui me fait douter de l'existence d'une séquence qui croîtrait indéfiniment est que l'écart entre $2^n-1$ et $2^{n+1}-1$, égal à $2^n$, s'accroît avec $n$ jusqu'à tendre lui-même vers l'infini. Il s'ensuit une raréfaction croissante des entiers de ce type dont on pourrait tout aussi bien conclure qu'à l'infini il n'en existe plus.
Comme les deux hypothèses sont de toute façon invérifiables, la conclusion que chacun en tire ne peut relever que d'une croyance en (ou préférence pour) l'une ou l'autre.
Merci de m'avoir donné l'occasion de fournir une réponse plus élaborée ! -
Je reviens sur la suite d'exposants 1, 1, 1, 2, 3, 2 que mon algorithme bugué n'avait pas trouvée parmi le premier million de suites impaires. La question qui se pose est de savoir s'il est nécessaire de pousser la recherche aussi loin avant de conclure qu'une suite d'exposants existe ou non. Eh bien la réponse est non. Si $u_1, u_2, u_3, ...$ est la suite recherchée et que $n_{\min }$ est le plus petit entier impair qui en est à l'origine, alors
[size=medium]$n_{\min }<2^{\sum u_i+1}$[/size]
1, 1, 1, 2, 3, 2 nécessite donc de lancer une recherche parmi les entiers impairs inférieurs à $2^{11}=2048$, c'est-à-dire les 1024 premiers, ce qui fait une fameuse économie de calcul et de temps. On sait depuis peu (grâce à Collag3n) que dans ce cas $n_{min}=1711$. Pour calculer les valeurs suivantes de $n_0$ il suffit d'ajouter récursivement $2^{\sum u_i+1}$ au terme précédent, ce qui donne la liste 1711, 3759, 5807, 7855, 9903, ... des entiers impairs à l'origine de cette suite d'exposants.
Si $n_{\min }$ n'est pas trouvé dans ladite plage de valeurs, c'est que la suite d'exposants recherchée n'existe pas (ce qui signifie bien sûr qu'on ne la trouvera dans aucune suite impaire).
Ceci permet de trouver sans trop utiliser de ressources processeur et de temps un type particulier de suite impaire. Par exemple, les exposants 6, 4, 2, 1 dénotent une suite plongeante : 2837, 133, 25, 19, 29, 11, 17, 13, 5, 1. Les valeurs suivantes sont 19221, 35605, 51989, 68373, ... Leur suite impaire respective présente la même caractéristique : il n'existe aucun $n_i>n_0$, sans que la raison en soit évidente (elles auraient très bien pu remonter après avoir plongé).
La forme générale de ces entiers impairs est
[size=medium]$n_0=2^{\sum u_i+1}\:(x-1)+n_{min}$[/size]
où $x$ est un entier $>0$. On est donc contraint de passer par un algorithme de recherche pour trouver $n_{min}$, à moins que quelqu'un ne découvre comment le calculer. -
Bonjour Wilfrid,
C'est moi qui ai souligné:Wilfrid a écrit:Ceci permet de trouver sans trop utiliser de ressources processeur et de temps un type particulier de suite impaire. Par exemple, les exposants 6, 4, 2, 1 dénotent une suite plongeante : 2837, 133, 25, 19, 29, 11, 17, 13, 5, 1. Les valeurs suivantes sont 19221, 35605, 51989, 68373, ... Leur suite impaire respective présente la même caractéristique : il n'existe aucun ni>n0, sans que la raison en soit évidente (elles auraient très bien pu remonter après avoir plongé).
Je me permets de te contredire: il existe une infinité de ni>n0 tels que la suite que tu leur associes ne présente pas la même caractéristique. Si je ne me trompe, tu confonds "j'ai regardé quelques i>0 et constaté que la suite correspondante était chaque fois plongeante (vers 1, je suppose que tu voulais dire, sinon je n'ai rien compris!) " et " il n'existe aucun ni>n0, sans que la raison en soit évidente (elles auraient très bien pu remonter après avoir plongé)".
Ton "sans que la raison en soit évidente" est donc inutile, puisqu'il est évident (je te laisse réfléchir à la preuve) que ce que tu dis est faux. Ton
"elles auraient très bien pu remonter après avoir plongé" traduit ton étonnement, et c'est bon signe!
Cordialement
Paul -
Je me permets de te contredire : il existe une infinité de ni>n0 tels que la suite que tu leur associes ne présente pas la même caractéristique.
Si tu ne situes pas $n_i$ et $n_0$ dans un contexte précis, dire qu'il existe des $n_i>n_0$ revient à dire qu'il existe des oiseaux qui volent !
Lorsque les $m$ premiers termes d'une suite impaire possèdent chacun un diviseur dont l'exposant est 1, cette suite est croissante sur les $m+1$ premiers termes, et on trouvera par définition un ou plusieurs $n_i>n_0$. Si ces exposants sont plus grands que 1, la suite est décroissante au moins sur les $m+1$ premiers termes, et il n'est pas certain qu'on trouvera un seul $n_i>n_0$. En effet, on ne peut pas prédire si elle remontera plus loin ou si elle continuera de descendre vers 1. Dans le premier cas son comportement n'aura rien de particulier ; dans le second cas on pourra être tenté d'associer la suite des $m$ premiers exposants au fait que la suite impaire continue de décroître, et en faire une caractéristique que pourraient éventuellement partager tous les $n_0$ qui possèdent la même suite de $m$ premiers exposants. Exemple :
La suite d'exposants de 8193, 16385, 24577, 32769, 40961, ... débute par 2, 2, 2, 2, 2, 2. Leur suite impaire respective est
8193, 6145, 4609, 3457, 2593, 1945, 1459, 2189, 821, 77, 29, 11, 17, 13, 5, 1
16385, 12289, 9217, 6913, 5185, 3889, 2917, 547, 821, idem
24577, 18433, 13825, 10369, 7777, 5833, 4375, 6563, 9845, 923, 1385, 1039, 1559, 2339, 3509, 329, 247, ...
32769, 24577, 18433, 13825, 10369, idem
40961, 30721, 23041, 17281, 12961, 9721, 7291, 10937, 8203, 12305, 9229, 3461, 649, 487, ...
Il n'existe de $n_i>n_0$ dans aucune d'entre elles. Mais je n'affirme pas pour autant que le concept de partage d'une caractéristique puisse être généralisé. D'ailleurs voici un contre-exemple, avec cette fois-ci 2, 2, 2, 2, 2 (cinq 2 au lieu de six) :
2049, 1537, 1153, 865, 649, 487, ..., 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1
4097, 3073, 2305, 1729, 1297, 973, 365, 137, 103,..., 2429, idem
6145, 4609, 3457, 2593, 1945, 1459, 2189, 821, 77, 29, 11, 17, 13, 5, 1
8193, 6145, 4609, 3457, 2593, 1945, 1459, 2189, 821, 77, 29, 11, 17, 13, 5, 1
10241, 7681, 5761, 4321, 3241, 2431, 3647, 5471, 8207, 12311, 18467, 27701, 2597, 487, ...
Il se peut que le partage en question résulte d'une configuration particulière des $m$ premiers exposants. -
Bonjour,
Si tu avais proprement défini ce que tu appelais "caractéristique" avant mon dernier message on aurait gagné du temps. Ton dernier message rétrécit le champ des interprétations possibles de ton "caractéristique" sans pourtant le définir. Aussi, pardon d'avance, si je redémontre qu'il y a des oiseaux qui volent. :-D.
Quelques résultats élémentaires connus depuis au moins 40 ans:
1)Toute suite finie $F$ d'entiers strictement positifs est une "caractéristique"( j'entends par là "suite finie d'exposants") . Le plus petit des entiers positifs qu'elle caractérise est inférieur à $2^{s+1}$ où $s$ est la somme des éléments de $F$. Si $N$ désigne ce plus petit entier positif, si $l$ est la longueur de $F$ et si $M$ est le $l+1$-ième terme de la suite de Collatz impaire d'origine $N$, alors les nombres caractérisés par $F$ sont les $N+k2^{s+1}$ ($k$ naturel, si l'on tient à se restreindre aux naturels). Pour tout $k$, le $l+1$-ième terme de la suite de Collatz impaire d'origine $N+k2^{s+1}$ est $M+2k3^l$.
2) Pour toute "caractéristique" et pour tout entier $A$, il existe un entier, et même une infinité d'entiers qui possède(nt) cette caractéristique et dont le(s) vol(s) dépasse(nt) $A$. Autant dire que la "caractéristique", si longue soit elle, ne sert strictement à rien, à elle seule, pour résoudre $3n+1$.
Paul -
Merci pour ces explications détaillées ! Je ne suis guère étonné d'apprendre que $N<2^{s+1}$ a déjà été trouvé il y a plus de 40 ans. Avec les moyens de calcul dont on disposait à l'époque c'était l'affaire de quelques heures.
Le fait de pouvoir quantifier le $l+1$-ième terme ne manque pas d'intérêt, mais on savait déjà sans faire le moindre calcul que le comportement de toutes les suites $N+k\:2^{s+1}$ est strictement identique sur les $l+1$ premiers termes (j'entends par là l'ordre de grandeur de chacun d'eux par rapport à son prédécesseur).Pour toute caractéristique et pour tout entier $A$, il existe un entier, et même une infinité d'entiers, qui possède(nt) cette caractéristique et dont le(s) vol(s) dépasse(nt) A.
C'est en effet un argument de poids.
Une petite question : le fait d'écrire $N<2^{s+1}$ indique que tu ne sais pas plus que moi calculer $N$. Faut-il en déduire que personne n'y est parvenu en 40 ans ? Existe-t-il cependant un moyen plus simple qu'un autre de calculer sa valeur ? -
Bonjour,
Calcul de $N$:
Notations-définitions;
$x$ est un naturel non nul;
$L$ est une liste finie, éventuellement vide, de naturel(s) non nul(s);
$xL$ est la liste dont le premier terme est $x$ et dont le reste est $L$;
$N_{xL}$ est le plus petit naturel caractérisé par $xL$;
$x_2$ est $0$ si $x$ est pair, $1$ sinon;
Si $L$ est non-vide,
$s_L$ est la somme de ses termes;
$N^*_L$ est celui des trois nombres $N_L, N_L+2^{s_L+1},N_L+2^{s_L+2}$ qui est congru à $(-1)^{x_2}$ modulo $6$.
Proposition:
$\displaystyle N_{xL}=\frac{5^{x_2}2^x-1}{3}$ si $L$ est vide, $\displaystyle \frac{N_L^*2^x-1}{3}$ sinon.
Sauf erreur, comme d'hab
Paul -
@depasse,
Prenons un exemple :
$xL=4,3,2,1$
$sL=6$
$x_2=0$
$(-1)^{x_2}$ modulo $6=1$
Ensuite j'ai supposé que $N_L$ était l'un des trois derniers termes de $xL$, soit 3, 2 et 1. Donc trois possibilités :
$N_L=3$
$3+2^{8}=259$, modulo 6 =1 :
$N_{xL}=\frac{1}{3} \left(259\times\ 2^4-1\right)=1381$
$N_L=2$
Aucun des trois nombres n'a de modulo 6 égal à 1.
$N_L=1$
1 modulo 6 = 1 :
$N_{xL}=\frac{1}{3} \left(1\times\ 2^4-1\right)=5$
J'ai certainement fait une erreur quelque part, ou mal interprété ton énoncé, parce qu'on devrait trouver $N_{xL}=581$. -
Si $L$ n'est pas vide, $N_L$ est, par définition, le plus petit entier caractérisé par $L$.
Exemple : $L=(3)$. $N_L=N_{(3)}=13$. $s_L+1=3+1=4$. Je dis que $L$, en l'occurence $(3)$, caractérise l'ensemble des entiers $\{N_L+k2^{s_L+1}, k \in \mathbb N\}$, en l'occurence $\{13+k2^4, k \in \mathbb N\}$.
Calcul de $N_{(4,3)}:=N_{xL}$ avec $x=4$ et $L=(3)$.
$L=(3)$ n'est pas vide; $x_2=4_2=0$; $(-1)^{ x_2 }=1$; les trois nombres $N_L, N_L+2^{s_L+1}, N_L+2^{s_L+2}$ sont $13, 13+2^4,13+2^5$.Celui des trois qui est congru à $(-1)^{ x_2 }=1$ modulo $6$ est $13$. Par conséquent, $N^*_L=13$ et donc, selon ma proposition
$\displaystyle N_{xL}=\frac{N^*_L2^x-1}{3}$ soit ici
$\displaystyle N_{(4,3)}=\frac{13*2^4-1}{3}=69$.
Wilfrid, tu as mal interprêté "les trois nombres $N_L, N_L+2^{s_L+1}, N_L+2^{s_L+2}$", même après tes Edit. A ce propos, quitte à ce que tu me trouves maniaque, je n'aime pas qu'on efface: quand on regrette ce qu'on a écrit: on barre et on corrige; en couleur c'est encore mieux!
Paul -
Ce que de mon côté j'aimerais bien, c'est que tu n'oublies pas avoir affaire à un non mathématicien. C'est comme si un compositeur se mettait en tête d'expliquer à un type qui ne connaît pas grand chose à la musique comment il a modifié son thème principal pour en faire celui du second mouvement de sa symphonie, ou pourquoi il a choisi telle autre tonalité. Dans tous les cas un peu de pédagogie est la bienvenue.
Si j'ai mal interprété $N_L$ c'est tout simplement parce que tu ne l'avais pas explicité. De mon point de vue ça sortait tout simplement de nulle part. Et tu fais la même chose avec $L=(3). N_L=N_{(3)}=13.\:s_L+1=3+1=4$. Comment déduis-tu de ces quelques égalités que le plus petit entier ayant pour diviseur $2^3$ est 13 ? Il a bien fallu que tu commences par le calculer d'une manière ou d'une autre, non ? Donc, toujours de mon point de vue, écrire d'entrée $N_{(3)}=13$ semble légèrement suspect.
EDIT : ne te fatigue pas à expliquer le reste, j'ai compris le concept. -
[suite]
Je vais éviter d'éditer une nouvelle fois mon précédent message. Tu prends l'exemple de $N_{(4,3)}$, donc $x=4$ et $L=(3)$. Entièrement d'accord. Mais avec la suite d'exposants 4, 3, 2, 1 de mon exemple précédent, à quoi correspond $L$ ? Quel terme parmi 3, 2 et 1 choisis-tu pour ton calcul ? Ta méthode de calcul ne fonctionnerait-elle qu'avec une suite d'exposants de 2 termes ? -
Je reconnais volontiers avoir omis, à mon grand tort, de dire que la fonction "$N$" n'était pas définie en la liste vide. Cela corrigé, il me semble que mes notatios-définitions définissent clairement ce que veut dire $N_L$ lorsque $L$ n'est pas la liste vide.
Par ailleurs, je n'ai nulle part prétendu faire preuve de pédagogie. Tu demandes une façon de calculer $N_L$. J'en donne une que je pense correcte et qui est peut-être débile! En tout cas elle fonctionne lorsque $L=(3)$ et lorsque $L=(4,3)$.
Le cas $(4,3)$ est prouvé (par mon dernier message) dès que le cas $(3)$ est admis, ce que j'ai fait. Au lieu de bêtement admettre ce cas $(3)$, je le prouve modulo ma proposition:
$N_{(3)}$ s'écrit encore $N_{3L}$ où $L$ est la liste vide. Ma proposition affirme qu'alors $\displaystyle N_{(3)}=\frac{5^{3_2}2^3-1}{3}=13$.
$69,208,104,52,26,13,40,20,10,5$ ne prouve pas ma proposition mais ne l'infirme pas. ;-).
Pour en revenir à la critique que tu me fais de manquer de pédagogie, elle ne me blesse pas. La pire des pédagogies, c'est la démagogie, autant dire le mépris. Je sais que je sais plus de maths que toi et ça ne prouve pas que ma formule est juste, moins encore que je suis un mathématicien! Si je n'ai pas donné de preuve de ma proposition, c'est pas seulement par flemme ou parce que j'en doute: c'est par pédagogie!
Cordialement
Paul -
Je te prie de m'excuser si je t'ai donné l'impression de vouloir te blesser ! Ce qui se passe en réalité est que j'ai moi-même mis au point une méthode de calcul de $N_{xL}$, que j'ai peaufinée ces derniers jours et qui par exemple permet à mon PC de calculer $N_{9,9,9,9,9,9,9,9,9,9}$, un nombre de 28 chiffres, en 110 millièmes de seconde. J'étais donc très intéressé de savoir si ta méthode permettait d'obtenir ce résultat, d'où mon énervement à buter sur quelques points obscurs quand mon travail était menacé de ruine ! :-D
Mais si j'ai bien compris tu ne peux pas aller au-delà d'une suite de deux termes exposants. Je n'irai pas jusqu'à dire que ça me réjouit, mais ça ne m'attriste pas non plus... -
Mieux vaut s'y croire un jour que jamais! Quand tu auras fini de jouir de ta méthode et de la puissance de ton PC, tu réfléchiras à ce que j'ai écrit, t'apercevras que ma caractéristique $L$ est de longueur arbitraire et que ma proposition est correcte, enfin je crois.
Le plus bourrin des algorithmes résolvant la question du jour est sûrement transformable en un programme tout aussi bourrin et le plus bourrin des PC va nous sortir la solution à la vitesse de la lumière ou presque. Soit! Et alors? -
hehe, Wilfrid....je me demandais combien de temps ton sujet tiendrait encore sans partir en c.... comme les autres fois.
Si tu ne lis pas (et n'essaies pas de comprendre) ce que les autres écrivent, et si tu rejetes systématiquement ceux qui viennent t'aider (et qui se demande pourquoi), tu ne vas pas aller très loin. Si tu avais pris la peine d'essayer l'algorithme de depasse sur un des cas ci-dessus (ex: 1,1,1,2,3,2 et 1711) tu aurrais pu constater qu'il fonctionne très bien, qu'on parte d'un $L$ vide ou pas.
depasse a raison: tes calculs sur PC n'ont que peu d'intérêt si 1) tu ne sais pas ce que tu fais, 2) ils ne te permettent pas de trouver ou d'en faire quelque chose. Et si en plus ils sont faux comme tu peux parfois le constater...à l'aide des autres.....
On sait que les logiciens ont des difficultés dans leur communication, mais il ne faudrait pas non plus en abuser. -
Au delà de l'aspect luminique de l'affaire, mon algorithme permet de comprendre certaines choses dans l'organisation des suites de Collatz, et selon moi c'est ce qui est le plus important. J'admets cependant que ton approche théorique l'est tout autant. Si tu parviens à la faire fonctionner avec une caractéristique de longueur arbitraire, alors on ne comptera plus en millièmes mais en millionièmes de secondes. En parlant de ça, je ne travaille pas dans un centre de calcul ; mon PC est équipé d'un simple Intel i5.
-
Voici une méthode de calcul de $n_{min}$ (nommé $N_{xL}$ ci-dessus) qui élimine toute nécessité de produire puis d'analyser des suites impaires.
Soit la suite d'exposants $u_1, u_2, ..., u_L$, $L$ sa longueur et $S$ la somme de ses termes. $n_{min}$ est le plus petit entier dont les $L$ premiers termes de la suite impaire possèdent comme diviseurs respectifs $2^{u_1}, 2^{u_2}, ..., 2^{u_L}$. Le $L+1$-ième terme de la suite de $n_{min}$ est
[size=large]$k=\frac{3^0}{2^{u_L}}+\frac{3^1}{2^{u_{L-1}+u_L}}+\frac{3^2}{2^{u_{L-2}+u_{L-1}+u_L}}+\text{...}+\frac{3^{L-1}\: \left(3\:n_{min}+1\right)}{2^{u_1+u_2+\text{...}+u_L}}$[/size]
[size=large]$=\sum\limits _{i=1}^{L-1} \frac{3^{i-1}}{d_i}+\frac{3^{L-1}\: \left(3\:n_{min}+1\right)}{d_L}=\sigma+\frac{3^{L-1}\: \left(3\:n_{min}+1\right)}{d_L}$[/size]
où $d$ est le carré de la somme cumulée de l'inverse de la suite d'exposants, et $d_i$ son terme d'indice $i$. Pour rendre les choses plus claires, si la suite d'exposants est 4, 3, 2, 1, son inverse est 1, 2, 3, 4, sa somme cumulée 1, 3, 6, 10, donc $d=2, 8, 64, 1024$. On déduit de la formule précédente que
[size=large]$n_{min}=\frac{2^S}{3^L}(k-\sigma)-\frac{1}{3}$[/size]
On connaît $S$, $L$ et $\sigma$, mais hormis le fait qu'il est le $L+1$-ième terme de la suite de $n_{min}$ on ne sait rien de $k$. La seule chose qu'on puisse faire à ce stade est de lui attribuer les valeurs successives 1, 3, 5, 7, ... jusqu'à tomber sur une valeur entière de $n_{min}$, qui sera donc la plus petite valeur possible de $n_0$ avec $S$ et $L$ donnés (j'en expliquerai la raison plus loin). Or, passer de $k$ à $k+2$ revient à incrémenter $n_{min}$ d'une valeur constante, puisque
[size=medium]$\left(\frac{2^S}{3^L}(k+2-\sigma)-\frac{1}{3}\right)-\left(\frac{2^S}{3^L}(k-\sigma)-\frac{1}{3}\right)=\frac{2^{S+1}}{3^L}$[/size]
On peut donc calculer $n_{min}$ par récurrence en commençant avec $k=1$ puis en ajoutant à chaque itération $\frac{2^{S+1}}{3^L}$ au résultat précédent, ceci jusqu'à obtention d'un entier. Voici cette fonction dans Mathematica :
Le format de NestWhile est expression, valeur initiale, condition de poursuite. Dans le cas présent on continue d'itérer aussi longtemps que expression n'est pas entier. Le nombre renvoyé par NestWhile est le premier qui ne satisfait pas à cette condition, donc un entier. J'expliquerai la raison de $k$ comme second argument à la fin de ce post.
Pour se représenter ce que signifie $\frac{2^{S+1}}{3^L}$ imaginons une règle de longueur $2^{S+1}$ unités divisée en $3^L$ parties égales, ou graduations. Imaginons d'autre part que nMin(), plutôt que de renvoyer le premier entier, affiche plusieurs milliers de ses résultats intermédiaires (ou valeurs calculées à chaque itération), rationnels et entiers. Si on écrit ces nombres horizontalement sur une longue feuille de papier et qu'on place la première graduation sur le premier d'entre eux, alors $n_{min}$ coïncidera avec l'une des graduations suivantes (mais on ne sait pas laquelle). Si ensuite on place la première graduation sur $n_{min}$, la dernière coïncidera avec l'entier impair suivant. Deux entiers consécutifs sont donc séparés de $2^{S+1}$ unités, mais on passe de l'un à l'autre en $3^L$ étapes (ou itérations). Et ça peut faire une différence considérable, comme on le constate avec l'exemple d'une suite d'exposants composée de quatorze 3 : avec la méthode des suites impaires il faudra un maximum de $2^{14\times3+1}/2=4\:398\:046\:511\:104$ de calcul et extraction des $L$ premiers diviseurs d'autant de suites impaires pour trouver $n_{min}$ ; avec la méthode par récurrence il ne faudra qu'un maximum de $3^{14}=4\:782\:969$ additions suivies chacune d'une comparaison, soit un nombre d'itérations divisé par 920 000 ! C'est pourquoi cet algorithme est très rapide.
Le nombre d'itérations pour trouver $n_{min}$ est bien entendu égal à son indice dans la liste des $3^L$ premiers termes intermédiaires. Par conséquent, que la suite d'exposants soit 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ou 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 on trouvera $n_{min}$ dans sensiblement le même laps de temps, qui sur mon PC est respectivement de 125 et 110 millièmes de seconde pour trouver 2047 et 2 227 805 650 266 028 156 792 922 965. La différence dans la durée du calcul vient du nombre d'itérations respectif : 59049 et 53133.
Le revers de la médaille est qu'avec un langage de programmation ou de script incapable de gérer les nombres rationnels, ajouter des nombres décimaux les uns aux autres un grand nombre de fois provoque une propagation et une aggravation de l'erreur d'arrondi, ce qui peut conduire l'algorithme à boucler indéfiniment sans trouver $n_{min}$. Dans ce cas il faudra utiliser
[size=medium]$n_k=\frac{2^S}{3^L}(k-\sigma)-\frac{1}{3}$[/size]
et boucler avec $k=1, 3, 5, 7, ...$ jusqu'à tomber sur un entier.
L'idéal serait cependant de pouvoir calculer le nombre d'itérations nécessaires pour trouver $n_{min}$, ce qui permettrait d'obtenir directement sa valeur.
[size=small]Quelques précisions à propos de $k$[/size]
Il n'est pas facile de comprendre le lien entre la valeur de $k$ et le fait qu'il soit le $L+1$-ième terme de la suite de $n_{min}$, puisqu'il a disparu du calcul. Mais comme il est impair, si $i$ est le nombre d'itérations nécessaires à nMin() pour trouver le premier entier, alors la valeur correspondante de $k$ serait $2\:i-1$ si on l'utilisait à la place de $\Delta$ pour calculer $n_{min}$. Exemple : nMin(1,2,1,2) = 123, dont la suite est 123, 185, 139, 209, 157, ... Si on affiche les $3^L$ premiers termes intermédiaires on constate que 123 est le 79ème. Donc $k=2\times79-1=157$, le cinquième terme de la suite de 123.
Le premier entier impair > 123 dont la suite possède les mêmes $L$ premiers exposants est 251, soit $123+2^{S+1}$. Dans la liste des termes intermédiaires il figure à l'indice 160, soit $79+3^L$, ce dont on déduit que le cinquième terme de la suite de 251 est $k=2\times160-1=319$. La suite de 251 est en effet 251, 377, 283, 425, 319, ... On pourrait continuer ainsi indéfiniment.
Le premier $k$ donnant un entier est donc nécessairement le $L+1$-ième terme de la suite de $n_{min}$. On pourrait dire également que puisque tous les entiers possédant la même suite de $L$ premiers exposants figurent les uns après les autres dans la liste de termes intermédiaires, ceci jusqu'à l'infini, le premier est nécessairement $n_{min}$.
[size=small]$k$ comme second argument de la fonction nMin()[/size]
Avec une suite d'exposants composée uniquement de 2, quelle que soit sa longueur, on obtient systématiquement $n_{min}=1$. C'est dû au fait que
[size=medium]$\frac{2^S}{3^L}(1-\sigma)$[/size] est dans ce cas toujours égal à $4/3$. Lorsque ensuite on soustrait $1/3$ le résultat est $1$.
On ne peut pas remplacer $1-\sigma$ par $3-\sigma$, car pour d'autres suites d'exposants il arrive que $n_{min}$ ne peut être trouvé qu'avec $k=1$ (donc une seule itération).
L'argument $k$ est par défaut égal à 1, et il est inutile de le mentionner. Lorsqu'on obtient $n_{min}=1$ il suffit de rappeler la fonction en ajoutant 3 comme second argument. Ça s'apparente à un pansement, mais pour régler la question il me faudra d'abord comprendre ce qui peut provoquer l'apparition de ce $4/3$, et ce n'est pas une mince affaire. J'ai testé de nombreuses suites d'exposants composées des mêmes nombres pairs sans que ça pose le moindre problème, mais ce n'est pas suffisant pour en conclure que seules les suites de 2 sont concernées. -
Je viens de réécrire un partie de mon précédent post afin non seulement d'éclaircir certains points et d'en ajouter un, mais surtout de remettre mes explication dans le bon ordre.
-
Me demande ce qui est le plus efficace.
Jusqu'à 5 Millions d'itérations sur des nombres rationnels haute précision, ou:
$N=\frac{5^{(\ell \mod 2)}\cdot 2^{\ell}-1}{3}$
$S=\ell$
et 13 itérations de
Input: next $\ell$
If $N \equiv 5^{(\ell \mod 2)} \pmod 6$ then $S=S+\ell$, return $N=\frac{N\cdot 2^{\ell}-1}{3}$
$N=N+2^{S+1}$
If $N \equiv 5^{(\ell \mod 2)} \pmod 6$ then $S=S+\ell$, return $N=\frac{N\cdot 2^{\ell}-1}{3}$
$N=N+2^{S+1}$
If $N \equiv 5^{(\ell \mod 2)} \pmod 6$ then $S=S+\ell$, return $N=\frac{N\cdot 2^{\ell}-1}{3}$
(code rouge non nécessaire)
Edit:
123, 185, 139, 209, 157
251, 377, 283, 425, 319
...
découle de $(n_i+k\cdot3^i)=\frac{3^i}{2^j}\cdot (n_0+k\cdot2^j)+\delta$
ou plus exactement $(157+k\cdot3^4)=\frac{3^4}{2^6}\cdot (123+k\cdot2^6)+\delta$ avec $k=0$ et $k=2$.
En prenant $k=1$, on peut trouver
187, 281, 211, 317, 238 qui sont aussi des entiers et utilisables, surtout pour le Glide (qui ne se limite pas qu'aux impairs). Dans ce cas on pourrait même partir de 59,....76 -
Wilfrid, je ne peux que t'inviter encore et encore à 1) lire 2) comprendre ce qu'on écrit ici.
Je n'ai fait que retranscrire l'algorithme de depasse qui détermine le $N_{xL}$, ou $N_{min}$ comme tu le soulignes toi-même en début de post.
Et bien que mon "edit" parle effectivement de $L+1$, ça n'est pas en raport avec cet algorithme, mais avec l'autre moitié de ton post qui parle, il me semble quand-même, de $L+1$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres