Bob s'amuse

[nodjim]

Bonsoir à tous. Petite enigme gentille.
Bob vient de découvrir à l'école le calcul en base 2. Passionné par le sujet, il se pose une question sur la possibilité d'obtenir une suite finie de 1 par effacement progressif des zéros d'un nombre impair donné. Par exemple, il écrit 13 en base 2: 1011 (poids faible à gauche). Pour supprimer le zéro, il ajoute le nombre 01011, c'est à dire 13*2=26. ce qui donne 111001. Il reste encore 2 zéros, pour supprimer le 1er, il ajoute 0001011 (13*8) et obtient 11110001. Et ainsi de suite jusqu'à obtenir 111 111 111 111.
Content de lui, il se demande si ça marche toujours, c'est à dire si son algorithme a une fin avec n'importe quel nombre impair.
Peut on l'aider ? Peut on donner une idée sur la longueur de la suite finie pour les nombres dont on est sûr qu'elle l'est ?

[Finrod]

Pourquoi écris-tu tes nombres binaires de droite à gauche au lieu de les écrire de gauche à droite ? C'est une convention ?

[Doraki]

C'est plus facile de faire les calculs dans notepad si on les écrit comme ça.

Je pense que dès que n est impair, ça se termine, et que la longueur de la suite est <= n - log2 n + O(1)

[Finrod]

Merci Doraki.

En gros tu cherches un multiple de 13 qui soit une somme de puissance de 2. IL faut donc que 13 divise cette somme.

Les solutions ont donc l'air d'être les diviseurs des

[nodjim]

Pourquoi écris-tu tes nombres binaires de droite à gauche au lieu de les écrire de gauche à droite ? C'est une convention ?

Si tu fais des calculs manuels en binaire, nos habitudes d'occidentaux nous faisant écrire de gauche à droite, comme le calcul se fait en commençant par le poids faible (addition, multiplication), le prolongement se fait plus naturellement vers la droite.

[nodjim]

C'est plus facile de faire les calculs dans notepad si on les écrit comme ça.

Je pense que dès que n est impair, ça se termine, et que la longueur de la suite est <= n - log2 n + O(1)

Peut être oui. En séparant les nombres (impairs) en certaines catégories, ne peut on donner quelque chose de plus précis ?

[Doraki]

Ben phi(n) - log2(n), c'est déjà un peu mieux.

Mais j'ai pas d'idée pour faire des catégories là =|

[Ben314]

Ben, visiblement, j'en suis au même point que Doraki :
Si k est l'ordre de 2 modulo n alors le nombre d'étapes est le nombre de 1 dans l'écriture en base 2 de (2^k-1)/n, mais je sais pas dire grand chose de mieux...

[Doraki]

Ah j'ai aussi que le nombre d'étapes est un diviseur de (n-1)/2.

Par conséquent, si n=2p+1 avec p premier,
- si p est de la forme 2^k-1, alors n aussi, et il n'y a qu'une seule étape
- si p n'est pas de cette forme, il y a plus que 1 étape donc il y a p étapes.

[Ben314]

Ah j'ai aussi que le nombre d'étapes est un diviseur de (n-1)/2.

Ca ne serait pas plutôt phi(n)/2 (où phi est l'indicatrice d'euler) ?

Edit : en fait c'est... ni l'un ni l'autre...

[Doraki]

Désolé, j'me suis gourré, j'peux pas dire que c'est un diviseur (en plus c'était faux avec n=9).
juste <= (n-1)/2.
Ce qui invalide ce que j'ai dit avec mon 2p+1 (par exemple pour n=23 y'a 4 étapes)

Ce qui divise phi(n), c'est le k dans la recherche de n * p = 2^k - 1.
D'où le nombre de 1 dans p doit être <= k - log2 n, avec k qui divise phi(n).

Quant à phi(n)/2, nan c'est faux pour n=23.

[Ben314]

En cherchant, il y a deux cas que je sais faire :
1) 2 est un générateur de (Z/nZ)* ssi le nombre d'étape est phi(n)/2
2) Si 2 et d'ordre k dans (Z/nZ)*, que k est pair et que 2^(k/2)=-1 [mod n] alors le nombre d'étapes est k/2.

Edit : En fait, l'algo le plus simple que j'ai pour calculer le nombre d'étapes, c'est d'écrire les représentants (entre -(n-1)/2 et +(n-1)/2) des différentes puissances de 2 modulo n et de compter combien il y en a de négatifs...
Exemple avec 23 => représentants entre -11 et 11
1, 2, 4, 8, (16=)-7 , (-14=)9, (18=)-5, -10, (-20)=3, 6, (12=)-11, (-22=)1
donc 4 étapes.

Au niveau majoration, le mieux que j'ai, c'est phi(n)/2.

[nodjim]

phi(n) c'est le nombre d'or ? Si c'est ça, je crois que ça n'a rien à voir.

[Ben314]

Non, danc ce contexte, la fonction phi (minuscule), c'est l'indicatrice d'euler qui à un entier n associe le nombre d'élément inversible de l'anneau Z/nZ, c'est à dire le nombre d'entiers de {0..n-1} qui sont premiers avec n.
On peut la calculer trés simplement si on connait la décomposition en nombres premier de n :
Si alors

Tu peut vérifier que le nombre d'étapes est toujours inférieur à avec égalité dans un certain nombre de cas...

[nodjim]

Non, danc ce contexte, la fonction phi (minuscule), c'est l'indicatrice d'euler qui à un entier n associe le nombre d'élément inversible de l'anneau Z/nZ, c'est à dire le nombre d'entiers de {0..n-1} qui sont premiers avec n.
On peut la calculer trés simplement si on connait la décomposition en nombres premier de n :
Si alors

Tu peut vérifier que le nombre d'étapes est toujours inférieur à avec égalité dans un certain nombre de cas...

Je suis d'accord. La question que je voulais poser ensuite était celle ci: Pour N=p1*p2, produit de 2 premiers, à quel rang trouve t on toujours un 1 dans la suite des puissances successives de 2 ?

[Ben314]

La "généralisation" du petit théorème de fermat te dit que, pour tout entier premier avec , on a (c'est en particulier à ça que sert l'indicatrice d'Euler...)

Si avec et premiers impairs distincts alors et, comme est bien premier avec , tu est sûr d'avoir .

Par contre, il est tout à fait possible (et même trés fréquent) que tu ait aussi pour un tel que est appelé l'ordre (multiplicatif) de a modulo n et c'est forcément un diviseur de .

En fait, dans ce contexte, on peut légèrement "améliorer" le , par exemple, si ( premiers impairs distincts) on a pour tout premier avec .

Exemple : si n=247=13x19 alors ppcm(12,18)=36 donc tu est sûr que (en fait, il s'avère que 2 est bien d'ordre 36, c'est à dire qu'aucune puissance plus petite que 36 ne donne 1, mais c'est un peu "de la chance"...)

[nodjim]

Très bien, tu as tout dit. Et comme pour un produit de 2 premiers p1 et p2 distincts le PPCM de p1-1 et p2-1 est au minimum la moitié du produit, car p1-1 et p2-1 sont pairs, on peut écrire:
il existe un a tel que 2^a=1 modulo N et (N+1)/2-(p1+p2)/2=a