Les suites de Kuzrassi

[syrac]

Le contraire ( c'est à dire une suite collatz qui ne passe par aucun kuz) qui reste à démontrer, ne doit pas exister (sauf pour 1,4,2 bien entendu).

Intéressant problème.

J'interviens pour expliquer pourquoi 53, par exemple, est un kuz.

Inutile de prendre autant de gants. :we:

53---> 160, 80, 40, 20, 10, 5 par l'algo collatz.
Si on applique à 5 l'algo kuz, on aboutit à 13, pas à 53.

kuzrassi(5) = 5, 10, 20, 40, 13, ...
collatz(53) = 53, 160, 80, 40, 20, 10, 5, ...

Dans la suite de kuzrassi, (40-1)/3 = 13, puisque 40 tombe sous le coup de la règle 1. Dans la suite de Collatz, 40 tombe sous le coup de la règle 1, qui dit pour sa part que tout entier pair doit être divisé par 2. Pour que la suite de kuzrassi soit l'inverse (le verlan) de la suite de Collatz, il aurait fallu énoncer une règle 1 qui permette à 40 de se poursuivre jusqu'à 160. Cette règle aurait dit que si n(i)-1 est divisible par 3, alors n(i+1) = (n(i) - 1)/3. Or c'est exactement ce qu'elle dit, le seul problème étant que 40 satisfait également à cette règle. Ce qui différencie la suite de kuzrassi de celle de Collatz, c'est que dans la première on rencontre 40 avant 160 (virtuellement), alors que dans la seconde on rencontre 160 avant 40. Si 40 avait pu se poursuivre jusqu'à 160, 53 aurait figuré dans kuzrassi(5) à la place de 13. Morale de l'histoire : tu ne peux pas inverser la suite de Collatz.

53 n'est donc pas accessible par l'algo kuz. Il n'a pas d'antécédent. C'est donc un kuz.

Ceci veut-il dire qu'un kuz est un entier impair qui ne peut pas (et non qui ne doit pas) figurer dans une suite de kuzrassi ailleurs qu'en première position, à l'instar d'une feuille de l'arbre des suites de Syracuse ?

[syrac]

Définition concise et claire du kuz :

----------------------------------------------------------------------
Exemple idéal d'inversion d'une suite de Collatz :

collatz(53) = 53, 160, 80, 40, 20, 10, 5, ...
kuzrassi(5) = 5, 10, 20, 40, 80, 160, 53, ...

Dans la vraie vie, cependant, kuzrassi(5) n'atteindra jamais 160, car l'opération (40-1)/3 = 13 sera effectuée avant l'opération (160-1)/3 = 53, si bien qu'on aura kuzrassi(5) = 5, 10, 20, 40, 13, ... De ce fait, 53 ne pourra jamais figurer dans une suite de kuzrassi autrement que comme premier terme. C'est donc un kuz.
----------------------------------------------------------------------

Pour dresser la liste des kuz il suffit d'écrire l'algorithme suivant :

- Appliquer l'algorithme de Collatz à un entier impair en le faisant s'arrêter dès qu'il rencontre un autre entier impair.
- Etant donné que le premier entier pair de cette séquence, qui succède à l'entier impair initial, satisfait toujours à la règle 1 de l'algorithme de kuzrassi, tester tous les entiers pairs de cette séquence à partir du second (donc du troisième terme de la séquence) afin de savoir s'il en existe au moins un qui soit divisible par 3 mais pas par 9 après qu'on l'ait décrémenté.
- Si c'est le cas alors l'entier impair initial est un kuz.

Par exemple, pour collatz(53) cet algorithme renvoie 40. Si 53 n'avait pas été un kuz il aurait renvoyé autre chose qu'un nombre, au choix du programmeur. Je (ou plutôt mon ordi) l'ai appliqué à tous les entiers impairs de 1 à 2999, et j'ai obtenu la liste suivante de kuz :

5, 21, 29, 53, 77, 85, 101, 117, 125, 149, 173, 181, 197, 213, 221, 245, 269, 277, 293, 309, 317, 341, 365, 373, 389, 405, 413, 437, 461, 469, 485, 501, 509, 533, 557, 565, 581, 597, 605, 629, 653, 661, 677, 693, 701, 725, 749, 757, 773, 789, 797, 821, 845, 853, 869, 885, 893, 917, 941, 949, 965, 981, 989, 1013, 1037, 1045, 1061, 1077, 1085, 1109, 1133, 1141, 1157, 1173, 1181, 1205, 1229, 1237, 1253, 1269, 1277, 1301, 1325, 1333, 1349, 1365, 1373, 1397, 1421, 1429, 1445, 1461, 1469, 1493, 1517, 1525, 1541, 1557, 1565, 1589, 1613, 1621, 1637, 1653, 1661, 1685, 1709, 1717, 1733, 1749, 1757, 1781, 1805, 1813, 1829, 1845, 1853, 1877, 1901, 1909, 1925, 1941, 1949, 1973, 1997, 2005, 2021, 2037, 2045, 2069, 2093, 2101, 2117, 2133, 2141, 2165, 2189, 2197, 2213, 2229, 2237, 2261, 2285, 2293, 2309, 2325, 2333, 2357, 2381, 2389, 2405, 2421, 2429, 2453, 2477, 2485, 2501, 2517, 2525, 2549, 2573, 2581, 2597, 2613, 2621, 2645, 2669, 2677, 2693, 2709, 2717, 2741, 2765, 2773, 2789, 2805, 2813, 2837, 2861, 2869, 2885, 2901, 2909, 2933, 2957, 2965, 2981, 2997, ...

La liste des différences entre deux termes successifs est

16, 8, 24, 24, 8, 16, 16, 8, 24, 24, 8, 16, 16, 8, 24, 24, 8, 16, ...

La séquence de 6 termes 16, 8, 24, 24, 8, 16 se répète constamment, ce qui signifie que les termes de chacune des suites imbriquées se trouvent toutes les 6 positions :

5, 101, 197, 293, 389, 485, ...
21, 117, 213, 309, 405, 501, ...
29, 125, 221, 317, 413, 509, ...
53, 149, 245, 341, 437, 533, ...
77, 173, 269, 365, 461, 557, ...
85, 181, 277, 373, 469, 565, ...

La différence entre deux termes est toujours 96.

Ces 6 suites sont de la forme 96m-11, 96m-19, 96m-43, 96m-67, 96m-75 et 96m-91, avec m > 0.

La chasse à une formulation plus simple et élégante de la liste de Schindl..., de kuz, est ouverte. Par exemple, est-il possible de remplacer ces 6 formes par un seule, ou par une formule ? Existe-t-il d'autres façons d'extraire de cette liste les suites imbriquées tout en préservant une certaine cohérence ?

[nodjim]

Salut,
il y a des erreurs da

[nodjim]

Ta liste est bonne, mais il faudrait ôter les multiples de 3. Ou les mettre tous. En effet, un multiple de 3 initial ne donnera par la suite kuz que des multiplications par 2. Tu peux les mettre si tu veux, mais ceux là n'ont vraiment pas d'intérêt. Si tu les ôtes, il ne restera normalement que des 24k+5 ou 96k+85.

[nodjim]

En fait non, tu ne peux pas les mettre, ceux là sont exclus dans l'énoncé.

[syrac]

En fait non, tu ne peux pas les mettre, ceux là sont exclus dans l'énoncé.

Pour supprimer les kuz divisibles par 3 il suffit de supprimer la forme 96m-75.

Il reste donc les formes 96m-11, 96m-19, 96m-43, 96m-67 et 96m-91, avec m > 0.

La suite 19, 43, 67, 91 est elle-même de la forme 24k-5, k > 0. 96m-11 fait figure d'intrus. Sans elle on pourrait poser qu'un kuz est de la forme 96m-(24k-5) = 24(4m-k)+5, avec m > 0 et 0 < k < 5.

Ce résultat bancal me déplait. Je vois trois éventualités : soit les entiers de la forme 96m-11 ne sont pas des kuz, soit les suites n'ont pas été extraires correctement de leur imbrication, soit la liste des kuz est incomplète.

[nodjim]

Si déja tu pouvais me présenter une nouvelle liste sans les multiples de 3, ce serait bien. Je pourrais voir si elle est conforme à ce que j'en attends.

[syrac]

Si déja tu pouvais me présenter une nouvelle liste sans les multiples de 3, ce serait bien. Je pourrais voir si elle est conforme à ce que j'en attends.

5, 29, 53, 77, 85, 101, 125, 149, 173, 181, 197, 221, 245, 269, 277, 293, 317, 341, 365, 373, 389, 413, 437, 461, 469, 485, 509, 533, 557, 565, 581, 605, 629, 653, 661, 677, 701, 725, 749, 757, 773, 797, 821, 845, 853, 869, 893, 917, 941, 949, 965, 989, 1013, 1037, 1045, 1061, 1085, 1109, 1133, 1141, 1157, 1181, 1205, 1229, 1237, 1253, 1277, 1301, 1325, 1333, 1349, 1373, 1397, 1421, 1429, 1445, 1469, 1493, 1517, 1525, 1541, 1565, 1589, 1613, 1621, 1637, 1661, 1685, 1709, 1717, 1733, 1757, 1781, 1805, 1813, 1829, 1853, 1877, 1901, 1909, 1925, 1949, 1973, 1997, 2005, 2021, 2045, 2069, 2093, 2101, 2117, 2141, 2165, 2189, 2197, 2213, 2237, 2261, 2285, 2293, 2309, 2333, 2357, 2381, 2389, 2405, 2429, 2453, 2477, 2485, 2501, 2525, 2549, 2573, 2581, 2597, 2621, 2645, 2669, 2677, 2693, 2717, 2741, 2765, 2773, 2789, 2813, 2837, 2861, 2869, 2885, 2909, 2933, 2957, 2965, 2981, ...

[nodjim]

Là on est d'accord.
Y a t' il dans cette liste des nombres différents de la forme 24k+5 ou 96k+85 ?
Parmi les nombres de la forme 24k+5 ou 96k+85 limités à 2981, y a t'il dans cette liste des nombres manquants ?

[syrac]

Il se pourrait que certains entiers possèdent une particularité qui les conduirait à figurer parmi la liste des kuz. En voici un exemple :

J'appelle séquence une suite d'entiers dont le premier et le dernier terme sont impairs.

seqCollatz(181) = 181, 544, 272, 136, 68, 34, 17
seqKuzras(17) = 17, 34, 11

D'où on déduit que 181 est un kuz. Mais l'exemple suivant, avec 87, qui n'est pas un kuz, est plus exotique :

seqCollatz(87) = 87, 262, 131
seqKuzras(131) = 131, 262, 524, 1048, 349

87 ne peut pas non plus être atteint. Cette fois-ci la raison est que 262 ne satisfait pas à la règle 1 de l'algorithme de kuzrassi, qui dit qu'un entier pair diminué de 1 doit être divisible par 3 mais pas par 9. Or, 262-1 = 261 est divisible à la fois par 3 et par 9 (87 et 29). Par conséquent, l'algorithme de kuzrassi applique la règle 2 et multiplie 262 par 2.

Ce constat devrait faire de 87 un kuz. Mais il est divisible par 3.

On peut trouver d'autres entiers de ce type, il suffit de chercher tous les entiers pairs p tels que p-1 soit divisible par 9 et que p ne soit divisible qu'une seule fois par 2, auquel cas la longueur de seqCollatz sera toujours 3. On aura donc la suite

seqCollatz(n) = n, 3n+1, (3n+1)/2

avec (3n+1) de la forme 36m-26, m > 0, => n = ((36m-26)-1)/3 = (36m-27)/3 = 12m-9. Dans l'exemple précédent on a bien 87 = 12*8-9. Le problème est que tous les entiers de la forme 12m-9 sont divisibles par 3.

[syrac]

Parmi les nombres de la forme 24k+5 ou 96k+85 limités à 2981, y a-t-il dans cette liste des nombres manquants ?

Non, ils y sont tous.

[syrac]

Lire "J'appelle séquence une suite d'entiers dont le premier et le dernier terme seulement sont impairs".

[syrac]

Pour en revenir au kuz exotique de mon précédent post, si on décide de choisir comme valeur de 3n+1 un entier pair divisible non pas une mais deux fois par 2, on obtient la séquence de quatre termes

seqCollatz(n) = n, 3n+1, (3n+1)/2, (3n+1)/4

La séquence de kuzrassi va donc débuter par (3n+1)/4, (3n+1)/2, ..., mais comme (3n+1)/2-1 n'est pas divisible par 3, l'algorithme va le multiplier par 2. Exemple :

seqCollatz(33) = 33, 100, 50, 25
seqKuzras(25) = 25, 50, 100, 200, 400, 133

Deux causes différentes, même effet. Il est possible qu'on ne sache pas tout ce qui pourrait transformer un nombre en kuz. Mais c'est juste une hypothèse.

EDIT : le seul moyen de le savoir c'est de tester seqCollatz puis seqKuzras pour tous les entiers impairs de 1 à 2999 par exemple.

[syrac]

Bon ! Le test dont je parlais à la fin de mon précédent post renvoie exactement la même liste de kuz. L'algorithme utilisé est celui :

Soit seqCollatz(i1) = i1, p1, p2, p3, i2 et seqKuzras(i2) = i2, p3, p2, p1, i1

Vérifier pour tout entier i1 impair et non divisible par 3 compris entre 1 et 2999, si le dernier terme de seqKuzras(i2) est égal ou non (condition pour un kuz) à i1.

Sous Mathematica j'ai utilisé cette fonction :

If[Last[seqKuzras[Last[seqCollatz[#]]]] != #, #, False] & /@ Select[Range[2999], OddQ[#] && ! Divisible[#, 3] &]

Elle garantit la validité du résultat. Comme tous les entiers potentiellement des kuz ont été testés, la dernière liste que j'ai postée ci-dessus contient définitivement tous les kuz de 1 à 2999. Inutile de dire que je suis très déçu, car ce résultat empêche de trouver une forme unifiée pour tous les kuz.

[syrac]

Y a t' il dans cette liste des nombres différents de la forme 24k+5 ou 96k+85 ?
Parmi les nombres de la forme 24k+5 ou 96k+85 limités à 2981, y a-t'il dans cette liste des nombres manquants ?

Il en manque même énormément ! Lorsque plus haut je t'ai répondu qu'il ne manquait aucun kuz dans la liste renvoyée par 24m+5 et 96m+85, je n'avais vérifié que les premières dizaines de termes. Cette fois-ci j'ai appliqué la fonction Mathematica ci-dessus à tous les entiers impairs non divisibles par 3 jusqu'à 9700. J'obtiens ceci :

5,29,53,77,85,101,125,149,173,181,197,221,245,269,277,293,317,341,365,373,389,413,437,461,469,485,509,533,557,565,581,605,629,653,661,677,701,725,749,757,773,797,821,845,853,869,893,917,941,949,965,989,1013,1037,1045,1061,1085,1109,1133,1141,1157,1181,1205,1229,1237,1253,1277,1301,1325,1333,1349,1373,1397,1421,1429,1445,1469,1493,1517,1525,1541,1565,1589,1613,1621,1637,1661,1685,1709,1717,1733,1757,1781,1805,1813,1829,1853,1877,1901,1909,1925,1949,1973,1997,2005,2021,2045,2069,2093,2101,2117,2141,2165,2189,2197,2213,2237,2261,2285,2293,2309,2333,2357,2381,2389,2405,2429,2453,2477,2485,2501,2525,2549,2573,2581,2597,2621,2645,2669,2677,2693,2717,2741,2765,2773,2789,2813,2837,2861,2869,2885,2909,2933,2957,2965,2981,3005,3029,3053,3061,3077,3101,3125,3149,3157,3173,3197,3221,3245,3253,3269,3293,3317,3341,3349,3365,3389,3413,3437,3445,3461,3485,3509,3533,3541,3557,3581,3605,3629,3637,3653,3677,3701,3725,3733,3749,3773,3797,3821,3829,3845,3869,3893,3917,3925,3941,3965,3989,4013,4021,4037,4061,4085,4109,4117,4133,4157,4181,4205,4213,4229,4253,4277,4301,4309,4325,4349,4373,4397,4405,4421,4445,4469,4493,4501,4517,4541,4565,4589,4597,4613,4637,4661,4685,4693,4709,4733,4757,4781,4789,4805,4829,4853,4877,4885,4901,4925,4949,4973,4981,4997,5021,5045,5069,5077,5093,5117,5141,5165,5173,5189,5213,5237,5261,5269,5285,5309,5333,5357,5365,5381,5405,5429,5453,5461,5477,5501,5525,5549,5557,5573,5597,5621,5645,5653,5669,5693,5717,5741,5749,5765,5789,5813,5837,5845,5861,5885,5909,5933,5941,5957,5981,6005,6029,6037,6053,6077,6101,6125,6133,6149,6173,6197,6221,6229,6245,6269,6293,6317,6325,6341,6365,6389,6413,6421,6437,6461,6485,6509,6517,6533,6557,6581,6605,6613,6629,6653,6677,6701,6709,6725,6749,6773,6797,6805,6821,6845,6869,6893,6901,6917,6941,6965,6989,6997,7013,7037,7061,7085,7093,7109,7133,7157,7181,7189,7205,7229,7253,7277,7285,7301,7325,7349,7373,7381,7397,7421,7445,7469,7477,7493,7517,7541,7565,7573,7589,7613,7637,7661,7669,7685,7709,7733,7757,7765,7781,7805,7829,7853,7861,7877,7901,7925,7949,7957,7973,7997,8021,8045,8053,8069,8093,8117,8141,8149,8165,8189,8213,8237,8245,8261,8285,8309,8333,8341,8357,8381,8405,8429,8437,8453,8477,8501,8525,8533,8549,8573,8597,8621,8629,8645,8669,8693,8717,8725,8741,8765,8789,8813,8821,8837,8861,8885,8909,8917,8933,8957,8981,9005,9013,9029,9053,9077,9101,9109,9125,9149,9173,9197,9205,9221,9245,9269,9293,9301,9317,9341,9365,9389,9397,9413,9437,9461,9485,9493,9509,9533,9557,9581,9589,9605,9629,9653,9677,9685

Voici maintenant la liste créée par 24m+5 et 96m+85 :

5,29,53,77,85,101,125,149,173,181,197,221,245,269,277,293,317,341,365,373,389,413,437,461,469,485,509,533,557,565,581,605,629,653,661,677,701,725,749,757,773,797,821,845,853,869,893,917,941,949,965,989,1013,1037,1045,1061,1085,1109,1133,1141,1157,1181,1205,1229,1237,1253,1277,1301,1325,1333,1349,1373,1397,1421,1429,1445,1469,1493,1517,1525,1541,1565,1589,1613,1621,1637,1661,1685,1709,1717,1733,1757,1781,1805,1813,1829,1853,1877,1901,1909,1925,1949,1973,1997,2005,2021,2045,2069,2093,2101,2117,2141,2165,2189,2197,2213,2237,2261,2285,2293,2309,2333,2357,2381,2389,2405,2485,2581,2677,2773,2869,2965,3061,3157,3253,3349,3445,3541,3637,3733,3829,3925,4021,4117,4213,4309,4405,4501,4597,4693,4789,4885,4981,5077,5173,5269,5365,5461,5557,5653,5749,5845,5941,6037,6133,6229,6325,6421,6517,6613,6709,6805,6901,6997,7093,7189,7285,7381,7477,7573,7669,7765,7861,7957,8053,8149,8245,8341,8437,8533,8629,8725,8821,8917,9013,9109,9205,9301,9397,9493,9589,9685

Toutes deux se terminent par 9685, mais il est clair que la seconde est moins longue que la première. Voici en fait les termes de la première liste qui ne figurent pas dans la seconde :

2429,2453,2477,2501,2525,2549,2573,2597,2621,2645,2669,2693,2717,2741,2765,2789,2813,2837,2861,2885,2909,2933,2957,2981,3005,3029,3053,3077,3101,3125,3149,3173,3197,3221,3245,3269,3293,3317,3341,3365,3389,3413,3437,3461,3485,3509,3533,3557,3581,3605,3629,3653,3677,3701,3725,3749,3773,3797,3821,3845,3869,3893,3917,3941,3965,3989,4013,4037,4061,4085,4109,4133,4157,4181,4205,4229,4253,4277,4301,4325,4349,4373,4397,4421,4445,4469,4493,4517,4541,4565,4589,4613,4637,4661,4685,4709,4733,4757,4781,4805,4829,4853,4877,4901,4925,4949,4973,4997,5021,5045,5069,5093,5117,5141,5165,5189,5213,5237,5261,5285,5309,5333,5357,5381,5405,5429,5453,5477,5501,5525,5549,5573,5597,5621,5645,5669,5693,5717,5741,5765,5789,5813,5837,5861,5885,5909,5933,5957,5981,6005,6029,6053,6077,6101,6125,6149,6173,6197,6221,6245,6269,6293,6317,6341,6365,6389,6413,6437,6461,6485,6509,6533,6557,6581,6605,6629,6653,6677,6701,6725,6749,6773,6797,6821,6845,6869,6893,6917,6941,6965,6989,7013,7037,7061,7085,7109,7133,7157,7181,7205,7229,7253,7277,7301,7325,7349,7373,7397,7421,7445,7469,7493,7517,7541,7565,7589,7613,7637,7661,7685,7709,7733,7757,7781,7805,7829,7853,7877,7901,7925,7949,7973,7997,8021,8045,8069,8093,8117,8141,8165,8189,8213,8237,8261,8285,8309,8333,8357,8381,8405,8429,8453,8477,8501,8525,8549,8573,8597,8621,8645,8669,8693,8717,8741,8765,8789,8813,8837,8861,8885,8909,8933,8957,8981,9005,9029,9053,9077,9101,9125,9149,9173,9197,9221,9245,9269,9293,9317,9341,9365,9389,9413,9437,9461,9485,9509,9533,9557,9581,9605,9629,9653,9677

Par conséquent, 24m+5 et 96m+85 ne permettent pas de générer tous les kuz.

[syrac]

Par contre, 96m-11, 96m-19, 96m-43, 96m-67 et 96m-91, avec m > 0, les produisent tous.

[syrac]

En partant de la forme 24m+5 il te manque 24m+2405, 24m+4805, 24m+7205, 24m+9605. Ensemble on obtient la forme unifiée 24m+2400k-2395, m >= 0, 0 < k < 6.

Là encore on se retrouve avec une intruse, 96m+85.

C'est moins compliqué avec 96m-11 et 96m-24k+5, m > 0 et 0 < k < 5.

Notes en passant qu'on peut écrire : 96m-(24k-5), m > 0 et 0 < k < 5 ou k = 2/3.

[nodjim]

Je n'ai pas regardé tout ce que tu as écrit, mais les trous que tu cites n'en sont pas:

"En partant de la forme 24m+5 il te manque 24m+2405, 24m+4805, 24m+7205, 24m+9605"

En effet, les 4 formes supplémentaires que tu cites sont bien des 24m+5. D'une manière plus générale, pour une forme an+b, b doit tjs être inférieur à a. C'est ce qu'on appelle des congruences. Ou bien encore les restes modulo a.

[syrac]

Je n'ai pas regardé tout ce que tu as écrit, mais les trous que tu cites n'en sont pas.

Reste néanmoins que tes deux formes conduisent à ce qu'il manque toujours 2/5ème des kuz. Comment les produis-tu ?

[nodjim]

Je n'ai pas regardé tout ce que tu as écrit, mais les trous que tu cites n'en sont pas:

"En partant de la forme 24m+5 il te manque 24m+2405, 24m+4805, 24m+7205, 24m+9605"

En effet, les 4 formes supplémentaires que tu cites sont bien des 24m+5. D'une manière plus générale, pour une forme an+b, b doit tjs être inférieur à a. C'est ce qu'on appelle des congruences. Ou bien encore les restes modulo a.