Les suites de Kuzrassi

[syrac]

Oui, à part que

24[4k/5]+5(1-[1-k/5+[k/5]])-11[1-k/5+[k/5]]

peut se simplifier en

24*[4k/5]-16*[1-k/5+[k/5]]+5

Je cherchais justement à me débarrasser de {-11, 5, 29, 53, 77}. :lol3:

EDIT : comme je déteste répéter plusieurs fois le même calcul, ce qui bouffe inutilement des ressources processeur, on peut également poser :

u = k/5
r = 24*[4u]-16*[1-u+[u]]+5

[nodjim]

Bien vu pour la simplifcation.

[syrac]

Il y a quand même une petite chose qui reste en suspend. Si on avait par exemple k = 5*r on en déduirait directement que r = k/5. Ce n'est malheureusement pas le cas ici, on ne peut pas déduire k de r ni r de k.

Au début il y avait un si..sinon, ensuite des sommes partielles, et maintenant une partie entière, en fait tout ce qui empêche de trouver une relation entre k et r.

Tu vas me dire que c'est bien pinailler, eh bien pas du tout, c'est juste pour la beauté de la chose.

On trouve dans la suite des kuz quelques curiosités étonnantes, comme le fait de pouvoir la construire à partir de 16, 24, 24, 24, 8. En voici une autre : si tu calcules le rang des kuz divisibles par un nombre premier à partir de 5, tu t'aperçois que leurs différences forment là aussi une suite répétitive de 5 nombres. Mais mieux encore, la somme de ces 5 nombres est toujours égale à 5 fois le nombre premier utilisé. Exemples :

Rang des kuz divisibles par 5 : 1, 5, 7, 13, 19, 26, 30, 32, 38, 44, 51, 55, ...
Différences : 4, 2, 6, 6, 7, ... -> somme = 5*5.

Rang des kuz divisibles par 7 : 4, 13, 22, 25, 31, 39, 48, 57, 60, 66, 74, 83, ...
Différences : 9, 9, 3, 6, 8, ... -> somme = 5*7.
...
Rang des kuz divisibles par 43 : 52, 70, 106, 159, 213, 267, 285, 321, 374, 428, 482, 500, ...
Différences : 18, 36, 53, 54, 54, ... -> somme = 5*43.

Je soupçonne que la suite des kuz possède une structure cachée, comme les suites de Collatz.

[syrac]

Voici une équation encore plus simple. Le kuz k est au rang

r = round((5k+39)/96)

Où round renvoie l'entier le plus proche de son argument.

[syrac]

On voit à quel point (5k+39)/96 colle au plus près du rang réel. Si on prend les 10 premiers kuz, donc de rang 1 à 10, et sans le round(), on obtient ceci :

0.666667, 1.91667, 3.16667, 4.41667, 4.83333, 5.66667, 6.91667, 8.16667, 9.41667, 9.83333

ou

0+2/3, 1+11/12, 3+1/6, 4+5/12, 4+5/6, 5+2/3, 6+11/12, 8+1/6, 9+5/12, 9+5/6, ...

La suite de valeurs décimales 2/3, 11/12, 1/6, 5/12, 5/6 se répète indéfiniment, si bien qu'il est impossible d'obtenir la moindre erreur dans le calcul de r à l'aide de cette formule.

En fait je l'ai calculée par la méthode des moindres carrés. La droite qui passe au plus près des kuz (calculée sur les 10.000 premiers) est d'équation y = 19.2 x - 7.8 = (96/5) x - 39/5 = 3*(32x-13)/5. Ce qui donne x = (5y+39)/96.

Si on a bien r = approx. (5k+39)/96, par contre on ne peut pas poser k = 3*(32r-13)/5.

[nodjim]

Pas mal, c'est bien simplifié.

[syrac]

Voici le graphe représentant la suite des 20 premiers kuz (en bleu) et la droite y=3*(32 x-13)/5 (en orange) :

[nodjim]

Bon le graphe ne me surprend pas. Sinon c'est chouette ce (5k+39)/96.

[syrac]

Il n'y a rien de surprenant, c'était simplement pour montrer avec quelle régularité la suite des kuz serpente autour de la droite.

[syrac]

Fonction kuz

Elle permet de produire les kuz des deux formes :

Voici la même au format texte :
(2^(2 + (-1)^k) (18 k - 7 + 3 (-1)^k) - 1)/3

kuz uniques

Le concept de kuz unique vient d'un double constat :

I - De nombreux kuz sont des doublons, ils conduisent à la même valeur i2 de seqCollatz que d'autres kuz (rappel : seqCollatz(i1) = i1, p1, p2, ..., pk, i2, où i est impair et p pair). Voici un exemple :

seqCollatz(5) = 5, 16, 8, 4, 2, 1
seqCollatz(85) = 85, 256, 128, 64, 32, 16, 8, 4, 2, 1
seqCollatz(341) = 341, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1

II - La valeur de i2 peut être n'importe quel entier impair non divisible par 3.

J'ai donc conçu un algorithme qui permet de générer les kuz pour lesquels la valeur de i2 sera unique et égale à un entier impair non divisible par 3. Exemple avec les cinq premiers, 5, 53, 149, 29, 277 :

seqCollatz(5) = 5, 16, 8, 4, 2, 1
seqCollatz(53) = 53, 160, 80, 40, 20, 10, 5
seqCollatz(149) = 149, 448, 224, 112, 56, 28, 14, 7
seqCollatz(29) = 29, 88, 44, 22, 11
seqCollatz(277) = 277, 832, 416, 208, 104, 52, 26, 13

J'ai mis en ligne un fichier texte qui contient deux listes des 360 premiers kuz uniques, l'une non triée et l'autre triée. Elle s'ouvre dans un nouvel onglet, il suffit de faire un copier-coller.

La liste triée est semble-t-il ordonnée, par groupes de 18 sans doute, mais je n'arrive par à en dégager une ou des formes. Si quelqu'un veut bien se pencher sur le problème je le remercie d'avance.

[syrac]

J'ai modifié le fichier texte en ligne. Les kuz uniques triés présentaient un souci. Je m'excuse auprès de ceux qui se seraient déjà penchés dessus.

[syrac]

J'ai créé l'illustration ci-dessous, qui représente la suite de Collatz de 17557, pour répondre à deux interrogations : premièrement, est-ce qu'éliminer les kuz faisant "double usage" est une bonne idée, et deuxièmement, qu'est-ce qui ne colle pas entre l'algorithme de Collatz et celui de kuzrassi, et qui empêche l'inversion d'une suite générée par le premier ? Pour ce qui concerne le premier point, on voit que l'idée n'est pas très bonne, car cette suite montre clairement que tous les kuz qu'elle contient, marqués en gras, conduisent à 1. Éliminer les 7 premiers risquerait de poser quelques problèmes.

Pour ce qui est du second point, je dois d'abord expliquer à quoi correspondent les couleurs : les nombres bleus sont ceux qui satisfont à la règle 1 de l'algorithme de kuzrassi, et les rouges sont les entiers impairs différents d'un kuz. Quant aux flèches vertes, je prendrai un exemple pour expliquer leur signification :

Suite de Collatz : 17557, 52672, 26336, 13168, 6584, 3292, 1646, 823, 2470, 1235, ...
Suite de kuzrassi : 1235, 2470, 823, 1646, 3292, 1097, ...

Une flèche verte marque donc l'endroit où la suite de kuzrassi se sépare de la suite inverse de Collatz. Elle marque une bifurcation. [Suite après l'illustration]



On peut créer l'inverse d'une suite de Collatz à partir de n'importe quel entier rouge, ou d'un kuz ... jusqu'à la première bifurcation, créée par la règle 1 de kuzrassi. C'est d'ailleurs à cause d'elles que les kuz existent. Ce qui est compatible entre les deux algorithmes ce sont leur règle 1 respective : faire 3n+1 dans un sens revient à faire (n-1)/3 dans l'autre sens, ainsi que leur règle 2 respective : faire n/2 dans un sens revient à faire 2*n dans l'autre sens. Mais la règle 1 de l'algorithme de kuzrassi entre en conflit avec la règle 2 de l'algorithme de Collatz.

Pour que la suite de kuzrassi ne bifurque pas à cet endroit il faudrait qu'elle soit capable d'anticiper la valeur de son prochain terme, c'est-à-dire savoir si la suite de Collatz a placé à cet endroit-là un entier pair ou impair. C'est impossible, bien sûr. Toujours est-il que pour inverser une suite quelconque de Collatz il faudrait que les deux algorithmes soient compatibles entre eux.

Enfin, voici la répartition des kuz dans la suite des entiers impairs non divisibles par 3. Tous les nombres grisés peuvent donner lieu à une séquence de kuzrassi exactement inverse d'une séquence de Collatz :

[nodjim]

Beau travail.
Tiens, pour les kuz, je me faisais une réflexion sur un paradoxe: à chaque nombre impair (<>0 mod3) et ses multiples de 2 associés, il n'y a qu'un nombre impair non kuz, tous les autres impairs <>0 mod 3 sont des kuz. Par exemple: 11,22,44,88,176,352, 704, 1408, 2816.. : 7 est non kuz (3*7+1=22), 29 (3*29+1=88), 469,...sont des kuz.

Comment se fait il qu'au final il y ait plus de non-kuz que de kuz ?

[syrac]

Je pense que la première des deux illustrations ci-dessus apporte un début de réponse à ta question : si on considère la suite de kuzrassi de 1619 (qui se trouve à deux rangs sur la gauche du kuz 2429) on a :

1619, 3238, 1079, 2158, 719, ..., 322, 107, 214, 71, 142, 47, 94, 31, 62, 124, 41, ...

Cette suite bifurque en atteignant 124, si bien qu'elle n'atteindra jamais le prochain entier impair, 661, qui du coup se voit propulsé au rang de kuz et affiché en noir gras au lieu de l'être en rouge comme n'importe quel entier impair. Une suite de kuzrassi ne peut donc par définition contenir aucun kuz, car, pour reprendre notre exemple, si la suite de kuzrassi de 1619 contenait 661, alors il ne serait plus un kuz ! D'autre part, il ne peut exister, là encore par définition, qu'une seule bifurcation entre deux kuz. Il est donc tout-à-fait normal de rencontrer moins de kuz que de non-kuz.

Dans la suite de Collatz de 17557 il y a 50 entiers impairs, dont seulement 8 sont des kuz pour la seule raison qu'il y a 8 bifurcations.

[syrac]

Par exemple: 11,22,44,88,176,352, 704, 1408, 2816.. : 7 est non kuz (3*7+1=22), 29 (3*29+1=88), 469,...sont des kuz.

L'exemple que tu cites est particulier, en ce sens que tous les termes de cette suite sont le double de leur prédécesseur. Dans l'image suivante j'ai représenté sur fond bleu tous les entiers qui satisfont à la règle 1 de l'algorithme de kuzrassi, et le kuz correspondant sur fond orange :

Voici la suite de Collatz de 30037 :

A la place de 30037 comme terme initial j'aurais pu aussi bien prendre 1877, 469 ou 29. Dans tous les cas, à cause de la bifurcation en 22 aucun de ces entiers bleus ne pourrait de toute façon être atteint par l'algorithme de kuzrassi, qui autrement leur aurait appliqué sa règle 1 comme il le fait à 22. C'est pourquoi les nombres impairs cités sont tous des kuz. Voici la suite de kuzrassi de 5, qui vaut pour tout terme initial compris entre 5 et 22 :

5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 7, ...

[nodjim]

Oui, en fait la suite géométrique que j'ai présentée monte très vite ! Il n'y a beau avoir qu'un seul non kuz, ce non kuz est le plus proche du début de la suite. C'était juste pour mettre en évidence le fait qu'une présentation donnée pouvait conduire, si on n'y regarde pas de près, à un raisonnement erroné.

[syrac]

@nodjim,

Voici une petite chose sur laquelle tu vas pouvoir te pencher. L'illustration ci-dessous représente les deux suites de Collatz originelle et compressée, c'est-à-dire 3n+1 et (3n+1)/2. On voit que dans la seconde il n'existe plus aucune valeur en bleu (qui satisfont à la règle 1 de l'algorithme de kuzrassi). Il ne reste que les valeurs en orange, qui sont les mêmes mais qui marquent une bifurcation (en remplacement des petites flèches vertes).

Par exemple, pour passer de 1235 à 823 (première ligne), l'algorithme de kuzrassi doit faire (2*1235-1)/3. Il se heurtera néanmoins toujours aux bifurcations.

EDIT : j'ai ajouté la suite de Syracuse (avec l'algorithme à une règle). Il n'y a plus trace de bleu ni d'orange.

[syrac]

Dans ce qui suit je vais montrer comment calculer ce que j’appelle le facteur d’un kuz, c’est-à-dire l’entier à son origine. Je vais montrer en même temps que la suite alternée des kuz représente leur ordre naturel, et que leur classement par valeurs croissantes est une erreur. J’essaierai d’être concis, donc de ne pas entrer dans les détails.

Voici tout d’abord la forme simplifiée de la fonction kuz, qui annule celle que j'ai postée plus haut :

Ce qui donne, avec r = 1, 2, 3, 4, 5, ... : 5, 85, 29, 181, 53, 277, 77, 373, 101, 469, 125, 565, 149, 661, 173, 757, 197, 853, 221, 949, …

On ne peut pas déduire de fkuz le rang du kuz k donné. Ce rang est donné par l’expression (k+7)/12 ou (k+11)/48 dont le résultat est entier. Si aucun ne l’est c’est que k n’est pas un kuz.

Voici maintenant les deux suites d’entiers nPair et nImpair :

[syrac]

Dans ce qui suit je vais montrer comment calculer ce que j’appelle le facteur d’un kuz, c’est-à-dire l’entier à son origine. Je vais montrer en même temps que la suite alternée des kuz représente leur ordre naturel, et que leur classement par valeurs croissantes est une erreur. J’essaierai d’être concis, donc de ne pas entrer dans les détails.

Voici tout d’abord la forme simplifiée de la fonction kuz, qui annule celle que j'ai postée plus haut :

Ou au format texte : fkuz(r) = 3 (2^((-1)^r+3) r-3)-2 (-1)^r

Ce qui donne, avec r = 1, 2, 3, 4, 5, ... : 5, 85, 29, 181, 53, 277, 77, 373, 101, 469, 125, 565, 149, 661, 173, 757, 197, 853, 221, 949, …

On ne peut pas déduire de fkuz le rang d'un kuz k donné. Ce rang est donné par l’expression (k+7)/12 ou (k+11)/48 dont le résultat est entier. Si aucun ne l’est c’est que k n’est pas un kuz.

Voici maintenant les deux suites d’entiers nPair et nImpair :

nPair représente l'ensemble des entiers pairs n tels que n-1 est divisible par 3 mais pas par 9. Pour tout élément de nPair de même rang r qu'un élément de nImpair, on a la relation (nPair(r) – 1)/3 = nImpair(r), et inversement, 3*nImpair(r)+1 = nPair(r). Voici comment calculer nPair(r) et nImpair(r) :

En dehors de ces entiers-là, une suite de Collatz peut contenir des entiers pairs résultant de divisions successives par 2 d’un terme de nPair : on a un terme de nImpair auquel on applique la règle 3*nImpair+1, puis on le divise par 2 successivement jusqu’à obtenir un entier impair. Mais tous les entiers pairs figurant dans cette progression géométrique de raison 1/2 n’appartiennent pas à nPair. Par exemple, dans 160, 80, 40, 20, 10, seuls 160 et 40 appartiennent à nPair.

Dans une suite de kuzrassi on aura l’inverse, 10, 20, 40, 80, 160. C’est précisément pourquoi l’entier impair (160-1)/3 = 53 est un kuz : l’algorithme de kuzrassi applique sa règle 1 à 40 parce qu’il appartient à nPair, si bien que 160 ne sera jamais atteint. Pour généraliser, un kuz apparaît dans les circonstances suivantes :


Dans une progression de ce type, si deux des termes appartiennent à nPair (en bleu dans l’exemple), alors (le plus grand – 1)/3 est un kuz et le plus petit est son facteur, parce qu’il marque ce que j’ai appelé plus haut une bifurcation de la suite. Dans l’illustration ci-dessous on voit qu’en allant de la droite vers la gauche, chaque bifurcation (orange gras) provoque l’apparition d’un kuz en amont (noir gras) :

Les termes appartenant à nPair sont en bleu ou en orange gras. On a bien la progression géométrique 823, 1646, 3292, 6584, 13168, 26336 et 52672, dans laquelle seuls 3292 et 52672 appartiennent à nPair. Le plus petit, 3292, est donc le facteur du kuz (52672-1)/3 = 17557, c’est-à-dire sa cause. Sans entrer dans un long développement, la valeur du kuz k dépend du rang de son facteur, je veux dire pair ou impair :

C’est là qu’entre en scène la suite des kuz alternée, car en effet, cette disposition est telle qu’on n’a pas besoin d’effectuer le moindre calcul. Pour une valeur donnée de r

nPair(r) est le facteur de fkuz(r)

Dans l’illustration ci-dessus, on calcule que nPair(366) = 3292 est le facteur de fkuz(366) = 17557, ou encore, que nPair(155) = 1390 est le facteur de fkuz(155) = 1853. Selon que r est pair ou impair, la bifurcation nPair(r) précède 3*fkuz(r)+1 de 4 ou 2 rangs, puisque les facteurs 2^2 et 2^4 interviennent dans le calcul.

La suite alternée des kuz représente donc leur ordre naturel. Elle permet de faire le lien entre un kuz et son facteur. Le classement des kuz par valeurs croissantes brise ce lien et retire toute espèce de sens à leur succession.

That’s all folks !

[syrac]

[Suite du monologue]

EDIT : je reprends ce post, qui s'étendait inutilement sur certaines choses.

De l’utilité des suites de kuzrassi

Ces suites permettent d'obtenir un résultat auquel les suites de Collatz (ou de Syracuse, mais pour moi ce sont deux entités distinctes) ne permettent pas d'aboutir : le calcul de deux entiers impairs partageant la même suite.

En effet, puisque le successeur d'une bifurcation est (nPair(r)-1)/3 = nImpair(r), pour tout entier positif r les deux entiers fkuz(r) et nImpair(r) conduisent à la même suite aux 3 ou 5 premiers termes près. Dans l'illustration ci-dessous on voit que l’entier impair partageant la suite de Collatz avec nImpair(14) = 41, successeur de nPair(14) = 124 dans une suite de kuzrassi (ou prédécesseur dans une suite de Collatz), est tout simplement le kuz fkuz(14) = 661 :



Il ne peut en exister d’autre, car les entiers qui séparent un kuz de son facteur ((1984-1)/3 = 661 de 124 par exemple) n’appartiennent par définition pas à nPair, si bien qu’aucun entier impair n ne peut les produire par 3n+1.

Tout ceci signifie que, grosso modo et pour faire court, une moitié des entiers impairs partage une suite de Collatz avec l’autre moitié.

Mais ce n’est pas tout. Si 41 précède 124 dans une suite de Collatz, il appartient lui-même à une autre suite dans laquelle il est précédé de 82, 27, 54, 108, etc., si bien que 27 partage la même suite de Collatz que 41 et 661. Mais on ne peut pas calculer la valeur de 27 par une formule simple, il faudrait commencer par appliquer l’algorithme de kuzrassi à 41, puis pendant qu'on y est le pousser jusqu’à la prochaine bifurcation pour voir où tout cela va nous mener, etc. etc. Ce serait infernal et sans fin. Par ailleurs, dans l’illustration ci-dessus tous les termes pairs représentés en bleu appartiennent à nPair et possèdent donc chacun un prédécesseur impair qui lui-même partage une partie de cette suite. Mais eux non plus ne sont pas calculables facilement, et on ne peut plus parler de partage complet.

Au final, cette organisation ressemble à s’y méprendre à une arborescence, ce qui démontre que contrairement à la croyance très répandue, aucune suite de Collatz n’est unique, si bien que parler de la durée et du temps de vol d’une suite isolée de son contexte est totalement irréaliste, pour ne pas utiliser un adjectif moins agréable.

Mais parler d’arborescence est un abus de langage. Un terme plus approprié serait celui de réseau. Les suites de Collatz forment réellement un réseau inextricable de nombres, dans lequel chacun emprunte un chemin déjà tracé par d’autres, mais impossible à modéliser à cause de sa complexité. Pour parvenir à une véritable arborescence il faut commencer par simplifier l’algorithme de Collatz, ce que j’ai fait dans mon papier sur l'arbre des suites de Syracuse.