Les suites de Kuzrassi

[nodjim]

Puisque tu es intéressé par cette approche inverse, tu devrais être sensible à cette petite énigme que j'avais proposée il y a quelque temps.
Bon amusement

Les suites de Kuzrassi sont définies ainsi:
Soit u0, nombre initial impair non divisible par 3 qui n'a pas d'antécédent IMPAIR dans la suite.
u(n+1)= (un-1)/3 si un pair, si (un-1)/3 entier et si (un-1)/9 non entier. Sinon u(n+1)=2*un.

Les nombres initiaux de ces suites sont dits des Kuz.
1 est il un Kuz ?
Trouver des Kuz.
Trouver tous les Kuz.

2 suites Kuz(rassi) indépendantes peuvent elles avoir des nombres en commun ?

Les suites Kuz sont elles infinies ?

Les suites Kuz contiennent elles des multiples de 3 ?

Une suite Kuz peut elle tourner en boucle ?

Pour un nombre quelconque faisant partie d'une suite Kuz, quel est son devenir si on lui applique l'algorithme de Syracuse ?

[syrac]

Les suites de Kuzrassi sont définies ainsi:
Soit u0, nombre initial impair non divisible par 3 qui n'a pas d'antécédent IMPAIR dans la suite.
u(n+1)= (un-1)/3 si un pair, si (un-1)/3 entier et si (un-1)/9 non entier. Sinon u(n+1)=2*un.

Je suis probablement plus con que la moyenne parce que je ne comprends strictement rien à cette définition. Pourrais-tu stp la formuler plus "proprement" et donner l'exemple d'une suite de quelques termes ?

Je présume que tu as voulu écrire

u(n+1)= u(n-1)/3 si u(n) est pair, et si u(n-1)/9 est rationnel. Autrement u(n+1)=2*u(n)

- On part par exemple de u(0) = 11, impair non div. par 3 et aucun antécédent puisque 1er terme.
- si bien que u(1) = quoi ? Il n'existe pas encore de u(n-1) à ce stade, à part u(-1) qui n'est pas défini.

EDIT : je peux déjà répondre à la question finale : l'entier auquel tu appliqueras l'algorithme de Syracuse se comportera comme un entier normal. Je suppose en effet qu'aucune étiquette "kuz" ne lui sera accrochée, laquelle ferait qu'il ne serait pas vraiment l'entier qu'il est supposé être.

[syrac]

@nodjim

Je viens de lire le sujet consacré à cette énigme sur prise2tete.fr. Ce qui me rassure est que certains ont mis 2 jours ou plus avant de commencer à comprendre l'énoncé. Et ce qui m'étonne est qu'une recherche de Kuzrassi sur Google renvoie uniquement à ce forum. Le mot est-il correctement orthographié ?

[nodjim]

Le mot est inventé. Le lire en verlan, puisque c'est Syracuse pris à l'envers. Sinon l'énoncé est correct.

[Benjamin]

Je présume que tu as voulu écrire

u(n+1)= u(n-1)/3 si u(n) est pair, et si u(n-1)/9 est rationnel. Autrement u(n+1)=2*u(n)

Salut,

Je ne sais pas comment tu t'es débrouillé pour modifier les parenthèses et aboutir à une définition qui n'a pas de sens alors que celle de Nodjim ne pose pas de problèmes particuliers. Je vais te mettre les parenthèses correctement :
u(n+1) = (u(n) -1)/3 si u(n) est pair, et si (u(n)-1) est divisible par 3 mais pas par 9.
Sinon u(n+1) = 2*u(n).

Quant au site, les gens n'ont pas mis 2 jours à comprendre : il y avait une erreur d'énoncé que nodjim a corrigé. Il faut lire tous les messages.

[syrac]

u(n+1) = (u(n) -1)/3 si u(n) est pair, et si (u(n)-1) est divisible par 3 mais pas par 9.
Sinon u(n+1) = 2*u(n).

Merci d'avoir clarifié cet énoncé, qui du coup devient limpide !

[syrac]

Soit u0, nombre initial impair non divisible par 3 qui n'a pas d'antécédent IMPAIR dans la suite.

Ton énoncé se mord la queue. Si u0 est l'entier initial d'une suite il n'a par définition aucun antécédent dans cette suite, que ce soit pair ou impair.

Les suites Kuz sont elles infinies ?

Affirmatif. La fonction FixedPointList[expression, valeur initiale] de Mathematica, qui calcule l'expression de manière répétitive jusqu'à ce que la valeur produite se répète (comme dans une suite de Syracuse où elle finit toujours par devenir 2,2,2,2, ...), ne renvoie strictement rien. Au contraire elle plante mon PC, qui se met à manquer de mémoire (sur 8 Go). Ceci n'a rien d'une démonstration, bien sûr, c'est juste un constat.

Voici la fonction kuz pour Mathematica, et la fonction seqKuz, qui génère la suite :

kuz[n_]:=If[EvenQ[n],If[Mod[n-1,3]==0 && Mod[n-1,9]!=0,(n-1)/3,2*n],2*n]

seqKuz[n_]:=FixedPointList[kuz,n]

Je pense que tu as imaginé cet algorithme dans l'espoir de démontrer qu'un suite de Syracuse pouvait être infinie, ce qui infirmerait la conjecture. Il me semble que s'acharner de la sorte est inutile, puisque l'arborescence que j'ai mise à jour démontre que toutes les suites convergent vers 2, la racine.

[nodjim]

Ta réponse m'a fait bien rire (sans moquerie aucune) pour la démonstration de l'infini des suites kuz: plantage du PC en faisant tourner l'algorithme !

Non, en posant ce problème, je n'ai pas du tout ambitonner de démontrer la suite de Syracuse. C'était juste une énigme comme une autre avec une solution bien finie.

Je suis bien d'accord avec toi pour dire que ton arborescence converge à 2, puisque précisément tu pars de 2 pour remonter l'arbre. Le problème est que tu ne démontres pas que tous les entiers de N sont dans cet arbre, ce qui est assez embêtant.

[syrac]

Ta réponse m'a fait bien rire (sans moquerie aucune)

C'est vrai qu'elle était un peu tirée par les cheveux. :hum:

Voici la réponse à ta question : "Les suites Kuz contiennent elles des multiples de 3 ?"

Voici le début de la liste des entiers n pairs tels que n-1 est divisible par 3 mais pas par 9, c'est-à-dire qui satisfont à la règle 1 :

4, 16, 22, 34, 40, 52, 58, 70, 76, 88, 94, 106, 112, 124, 130, 142, 148, 160, 166, 178, 184, 196, ...

On voit qu'il y a deux suites imbriquées :

16, 34, 52, 70, 88, 106, ... et 4, 22, 40, 58, 76, 94, ...

soit les entiers de la forme 18 m - 2 et 18 m - 14, m > 0.

Tu appliques la règle 1 à ces entiers, ce qui donne les deux nombres

(18 m - 3) / 3 = 6 m - 1, et (18 m - 15) / 3 = 6 m - 5.

Aucun de ces nombres ne peut être divisible par 3, car seuls les entiers de la forme 6 m - 3 le sont. Ça signifie qu'à chaque fois que tu appliques la règle 1, l'entier produit ne peut pas être divisible par 3, et la règle 2 devra lui être appliquée. La conséquence de ceci est que tu ne trouveras jamais deux entiers impairs consécutifs dans la suite produite par ton algorithme.

Donc, tous les entiers de l'une ou l'autre de ces deux formes sont impairs, ils ne satisfont plus à la règle 1 et tu dois donc leur appliquer la règle 2, c'est-à-dire les multiplier par 2, ce qui fait qu'il ne seront toujours pas divisibles par 3 (il aurait fallu pour cela les multiplier par 3 ou un multiple de 3).

Par conséquent, ton algorithme, en supposant que le terme initial de la suite satisfasse à la condition 1, ne produira aucun entier divisible par 3.

En appliquant la règle 2 tu produis un entier de la forme

2 * (6 m - 1) = 12 m - 2, ou 2 * (6 m - 5) = 12 m - 10

Cet entier est nécessairement pair. Mais satisfait-il à la condition 1 ? Il faudrait pour cela que l'entier de la forme 12 m - 2 - 1, soit 12 m -3, soit divisible par 3, ce qui est le cas puisque (12 m - 3)/3 = 4 m - 1. Par contre, l'entier de la forme 12 m - 10 - 1 = 12 m - 11 n'est pas divisible par 3. Comme aucun de ces entiers n'est pair, dans les deux cas on va devoir appliquer la règle 2, donc multiplier par 2.

La question à laquelle il reste à répondre est maintenant celle-ci : combien de fois va-t-il falloir multiplier un entier de l'une des formes 6 m -1 ou 6 m -5 par 2 pour obtenir un entier pair qui satisfasse à la condition 1 ?

[EDIT] je dois revoir certains points de mon raisonnement. J'ai en effet omis de décrémenter 6 m - 1 et 6 m - 5 avant de voir s'ils étaient divisibles par 3.

[syrac]

Je suis bien d'accord avec toi pour dire que ton arborescence converge à 2, puisque précisément tu pars de 2 pour remonter l'arbre. Le problème est que tu ne démontres pas que tous les entiers de N sont dans cet arbre, ce qui est assez embêtant.

Je crois que tu le fais exprès pour me contrarier. Combien de processus produisant une arborescence as-tu contestés au cours de ta vie ? Juste le mien sans doute...

Non, je ne suis pas parti de 2 pour remonter dans les branches de l'arbre, une vie n'y aurait pas suffi. Je te suggère de lire mon papier, ou si tu l'as déjà lu, de le relire avec un peu plus d'attention.

[syrac]

Les suites Kuz contiennent elles des multiples de 3 ?

Je reprends ma démonstration précédente en la simplifiant.

Voici le début de la liste des entiers n pairs tels que n-1 est divisible par 3 mais pas par 9, c'est-à-dire qui satisfont à la règle 1 :

4, 16, 22, 34, 40, 52, 58, 70, 76, 88, 94, 106, 112, 124, 130, 142, 148, 160, 166, 178, 184, 196, ...

On voit qu'il y a deux suites imbriquées :

16, 34, 52, 70, 88, 106, ... et 4, 22, 40, 58, 76, 94, ...

soit les entiers de la forme 18 m - 2 et 18 m - 14, m > 0.

Puisque la règle 1 leur est appliquée, ça signifie qu'ils sont le dernier terme d'une suite d'entiers auxquels on a appliqué la règle 2 une ou plusieurs fois. Ils sont donc égaux à 2^k * p, k > 0 et p premier ou produit de nombres premiers. Leur successeur dans la suite est de ce fait égal à (2^k * p - 1) / 3, nombre impair auquel on va ensuite appliquer la règle 2 une ou plusieurs fois.

Il existe donc un entier impair n tel que n = (2^k * p - 1) / 3, soit 3 n + 1 = 2^k * p.

n peut prendre l'une des valeurs 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, ..., soit un entier de la forme 6 m - 1 ou 6 m - 5. On le vérifie en posant que les entiers pairs auxquels sera appliquée la règle 1 sont égaux à 3 * (6 m - 1) + 1 = 18 m - 2, ou à 3 * (6 m - 5) + 1 = 18 m - 14, ce qu'on savait déjà.

Comme 6 m - 1 et 6 m - 5 ne sont pas divisibles par 3, ils ne le deviendront pas lorsqu'on les multipliera par 2 une ou plusieurs fois.

Ceci démontre qu'il n'existe aucun multiple de 3 dans une suite produite par cet algorithme.

On pourrait également poser que tout entier auquel on applique la règle 1 est égal à (6 m - 1) * 2^k ou à (6 m - 5) * 2^k. Reste à déterminer quelle peut être la valeur de k.

Une suite Kuz peut elle tourner en boucle ?

Oui, la suite kuz(1) = 1, 2, 4, 1, 2, 4, 1, 2, 4, ..., ou la suite kuz(4) = 4, 1, 2, 4, 1, 2, 4, 1, 2, ...

Je ne pense pas qu'il en existe d'autre, mais plutôt que ces suites croissent indéfiniment.

[syrac]

On peut faire beaucoup plus simple.

Voici le début de la liste des entiers n pairs tels que n-1 est divisible par 3 mais pas par 9, c'est-à-dire qui satisfont à la règle 1 :

4, 16, 22, 34, 40, 52, 58, 70, 76, 88, 94, 106, 112, 124, 130, 142, 148, 160, 166, 178, 184, 196, ...

Ils sont de la forme 18 m - 2 et 18 m - 14.

Le successeur de chacun d'eux sera de l'une des deux formes

((18 m - 2) - 1) / 3 = 6 m - 1

((18 m - 14) - 1) / 3 = 6 m - 5

soit l'un des entiers

1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, ...

Comme ils sont impairs, la règle 2 leur sera appliquée. On devra les multiplier par 2 successivement jusqu'à ce qu'ils atteignent la valeur d'un entier satisfaisant à la règle 1. Ils auront alors pour valeur (6 m - 1) * 2^k ou (6 m - 5) * 2^k. Et puisque 6 m - {1 ou 5} n'est pas divisible par 3, sa valeur finale, après un nombre quelconque de multiplications par 2, ne le sera pas non plus.

D'où on déduit qu'une suite de kuzrassi est entièrement constituée d'entiers égaux à (6 m - 1) * 2^k ou (6 m - 5) * 2^k, avec m > 0 et k >= 0, aucun de ses termes ne pouvant être un multiple de 3.

CQFD

[syrac]

[Suite de mon précédent post]

Prenons l'exemple d'une suite débutant par 22, qui satisfait à la règle 1 :

22 = (6 * 2 - 1) * 2^1

Son successeur est égal à ((6 * 2 - 1) * 2^1 - 1) / 3 = 7, que l'on peut écrire sous la forme (6 * 2 - 5) * 2^0. Maintenant on modifie simplement l'exposant de 2 pour obtenir un entier qui satisfait à la règle 1, ce qu'on obtient avec 2^4. La quatrième multiplication par 2 de 7 donne (6 * 2 - 5) * 2^4 = 112, qui a pour successeur ((6 * 2 - 5) * 2^4 - 1) / 3 = 37, que l'on peut écrire sous la forme (6 * 7 - 5) * 2^0.

On observe que lors des multiplications successives par 2 de 7, pour ne prendre que cet exemple, on obtient 14, 28, 56 et 112. Or, 14, 28 et 56 ne figurent pas parmi les entiers qui satisfont à la règle 1. Il a donc fallu effectuer une multiplication supplémentaire par 2 pour obtenir 112, qui satisfait enfin à cette règle.

On se retrouve maintenant avec le problème suivant :

Soit une suite composée d'entiers de la forme (6 m - c) * 2^k, avec m > 0, c = 1 ou 5, k >= 0. Le terme initial est (6 m - c) * 2^0. Combien de fois faudra-t-il incrémenter k avant de tomber sur un entier tel que (6 m - c) * 2^k - 1 soit divisible par 3, sachant qu'après la division on obtiendra de nouveau un entier égal à (6 m - c) * 2^0, bien que les valeurs de m et c puissent avoir changé ?

[Benjamin]

Heureusement que dans l'énoncé on dit que les Kuz (ie u0) sont impairs. Faudra que tu m'expliques pourquoi tu fais commencer la suite par des nombres pairs également.
Quand aux entiers de la forme 6m-1 ou 6m+1, ce sont justement les Kuz !

[syrac]

Heureusement que dans l'énoncé on dit que les Kuz (ie u0) sont impairs. Faudra que tu m'expliques pourquoi tu fais commencer la suite par des nombres pairs également.
Quand aux entiers de la forme 6m-1 ou 6m+1, ce sont justement les Kuz !

Que le terme initial soit pair ou impair ne change strictement rien à l'affaire, puisque tu finiras toujours par tomber sur un terme impair égal à celui que tu aurais pu choisir. Ce qui m'intéresse est de trouver une formule qui renvoie tous les termes successifs d'une suite, et pour ça il faut un énoncé qui décrive tous les termes sans distinction de parité et d'imparité, comme le fait (6m-c)*2^k, avec k >= 0.

Tu as raison sur le principe de remplacer 6m-5 par 6m+1. Le problème est le changement de signe. Il est moins complexe de traiter des entiers égaux à 6m - {1 ou 5} que s'ils étaient égaux à 6m {+1 ou -1}.

[syrac]

Quand aux entiers de la forme 6m-1 ou 6m+1, ce sont justement les Kuz !

Une chose vient de me traverser l'esprit. Peut-on remplacer 6m-5 par 6m+1 dans la suite 1, 7, 13, 19, 25, 31, 37, 43, 49, 55, 61, ... ?

Non, car 1 = 6*1-5 = 6*0+1. Utiliser 6m+1 obligerait donc à poser m >= 0 juste pour le cas particulier que représente 1, ce qui aboutirait à une définition du genre : un kuz est égal à 6m-1 avec m > 0, ou à 6m+1 avec m >= 0. Si on ne fait pas cette distinction on devra prétendre, par souci de cohérence, que 6*0-1 = -1 peut figurer dans une suite de kuzrassi.

On pourrait également omettre le premier terme respectif des deux suites impaire et paire, c'est-à-dire 1 et 4, puisque 1 = (4 - 1) / 3, c'est-à-dire prétendre qu'ils ne peuvent pas figurer dans une suite de kuzrassi.

PS : existe-t-il une raison particulière de nommer kuz les nombres impairs ?

[nodjim]

Bonsoir.
Un kuz est par défintion un nombre qui n'a pas d'antécédent impair. 1 a un antécédent impair: lui même, ce n'est donc pas un kuz.
Une suite kuz est construite de telle sorte qu'il n'existe qu'un seul antécédent. Comme le nombre kuz initial n'a pas d'antécédent par définition, une suite kuz ne peut se reboucler sur elle même. Comme à partir d'un kuz k donné le cardinal des nombres inférieurs à k est limité, et comme une suite kuz est illimitée (on peut toujours trouver un suivant), alors la suite kuz a toujours pour limite l'infini.

[nodjim]

Les kuz sont de la forme 24k+1 ou 96k+85. Tous les autres nombres d'une suite kuz ont un antécédent, ce ne sont pas des kuz.

[syrac]

Un kuz est par défintion un nombre qui n'a pas d'antécédent impair. 1 a un antécédent impair: lui même, ce n'est donc pas un kuz.

Merci pour cette réponse. Mais tout ceci n'est pas très limpide. Par exemple, comment 1 peut-il être son propre antécédent ? Le mot antécédent ne désigne-t-il pas tout simplement le prédécesseur d'un entier dans une suite ? La terminologie est essentielle dans la compréhension d'un concept.

Pourrais-tu donner quelques exemples numériques de ce que tu appelles un kuz, et suite kuz ?

[nodjim]

Appliquons à l'algorithme proposé le nombre 1:
1---->2
2-1 non divisible par 3, alors on multiplie 2 par 2=4
4-1 est divisible par 3 et pas par 9----->3/3=1

Maintenant, si on prolonge la multiplication par 2 de 4, au lieu d'appliquer l'algo kuz:
4---->8----->16, et 16-1=15 divisible par 3 et pas par 9, 15/3=5
5 est un kuz car il n'a pas d'antécédent impair.
Si on prolonge 16:
16---->32---->64 (mais 63 divisible par 9, on continue) 64--->128--->256
255 divisible par 3 et pas par 9: 255/3=85
85 est un kuz car il n'a pas d'antécédent impair.
Etc...