Puissance 3 en binaire

nodgim · April 2019

Bonjour @ tous.

Je viens de faire une curieuse observation sur les puissances de 3 écrites en binaire. En réalité, cette observation a été faite sur une suite de Collatz longue ( ! ), et s'avère identique avec les puissances de 3.

En binaire, les puissances de 3, poids fort à droite :
1
11
1001
11011
1000101
.....

En notant les augmentations successives du nombre de bits d'une puissance à l'autre :

121 212 212 122
121 212 212 122
121 212 212 122
121 212 212 122

121 221 212 122
121 221 212 122
121 221 212 122
121 221 212 122

121 221 212 212
121 221 212 212
121 221 212 212
121 221 212 212
121 221 212 212

122 121 212 212
......

On trouve une trame de cycle de longueur 12, corrigée régulièrement tous les 53 bits ( 4 * 12 + 5 ) : 12

>21.

Il y a précession d'un 2. Au bout de 12 précessions, on retrouve la trame initiale.

N'étant pas programmeur, je ne suis pas même allé jusqu'à vérifier que cette règle était correcte jusqu' à 1 cycle complet, qui permettrait de retrouver 121 212 212 122. Et, à fortiori, je n'ai pas pu observer si, au bout de ce très long cycle, ne se trouve pas une autre précession dans un cycle plus long.....

Quelqu'un connait-il ou aurait-il une explication ?

Cidrolin · April 2019

Dans ce problème on trouve parfois $\ln 3 /\ln 2$ : http://www.les-mathematiques.net/phorum/read.php?5,1248951,1254137#msg-1254137

nodgim · April 2019

Attention, Cidrolin : Je n'ai évoqué Collatz que comme circonstance. Je parle ici uniquement des puissances de 3 en base 2.

Maxtimax · April 2019

Si j'ai bien compris tu regardes, étant donné $n$, le plus grand entier $k_n$ tel que $2^{k_n}\leq 3^n$ et ta suite c'est $k_{n+1}-k_n$, n'est-ce pas ?

Si c'est bien ça, alors $k_n$ est aussi le plus grand entier tel que $k_n \leq n\log_2 (3)$, c'est-à-dire $k_n = \lfloor n\log_2(3) \rfloor$, ce qui explique déjà que ce que tu observes se situe entre $1$ et $2$ (regarder la valeur numérique de $\log_2(3)$). Je ne suis pas sûr de savoir expliquer la période par contre.

(on retrouve par contre le $\log_2(3)$ mentionné par Cidrolin)

lourrran · April 2019

Ce qu'on constate, c'est que $2^{19}=524288$ et $3^{12}=531441$ ; seulement 1,3% d'écart entre ces 2 nombres.
Donc quand on avance de 12 pas dans notre suite, on ajoute 19 bits à notre nombre. Sauf de temps en temps un petit décalage.
Et en plus, ceci explique la quasi périodicité.

depasse · April 2019

Bonjour,

Pour tout $n\in \mathbb N^*$, $2$ engendre $( \mathbb Z / 3^n \mathbb Z, \times)$ dont l'ordre est $2*3^{n-1}$.
On en déduit, je crois, la périodicité. Les gens n'ont cure de mes croyances et ils ont bien raison!
Amicalement
Paul
Edit de contrition

lourrran · April 2019

Ici, la périodicité constatée, c'est une période de 12. Et cette périodicité de 12 est directement liée à la proximité forte entre $2^{19}$ et $3^{12}$

$\ln_2(3^0)=0$ ; $\ln_2(3^{12})=19,01955$ ; $\ln_2(3^{24})=38,0391$
La partie décimale est quasiment la même. Et c'est cette partie décimale qui régit les éléments qui suivent. Même cause, mêmes conséquences.

nodgim · April 2019

Merci pour ces quelques réactions.

2^19 - 3^12 est effectivement un des jalons de "proximité" entre puissances de 2 et puissances de 3. Cependant, ce n'est pas le seul : 2^8 - 3^5, 2^65-3^41, 2^84-3^53, 2^485-3^306,.... en sont d'autres, qui n'ont pas de rapport apparent avec l'observation faite.

Et puis, j'ai dit qu'au bout de 12 précessions, on aura un cycle long. Or, pas question de cycles entre logarithmes, n'oublions pas : irrationalité. Celle-ci est peut être caractérisée par une autre précession régulière d'un 2 qui va engendrer un autre cycle plus long, etc.....

Cidrolin · April 2019

Les quinze premières réduites de $\ln 3/\ln2$ : 86112

lourrran · April 2019

Si je réécris la série précédente, en faisant des lignes de 41 éléments, on obtient :

121 212 212 122 121 212 212 122 121 212 212 122 121 21
221 212 212 122 121 212 212 122 121 212 212 122 121 21
221 212 212 121 221 212 212 122 121 212 212 122 121 21
221 212 212 121 221 212 212 121 221 212 212 122 121 21
221 2

Donc à part quelques petits incidents (inversion entre 12 et 21 par exemple), on retrouve cette périodicité. Et c'était complètement prévisible.

nodgim · April 2019

Oui, en effet. J'ai aussi les chiffres que tu as donnés, il faut bien réécrire le tableau avec des lignes de longueur correspondante à la nouvelle apparition d'un 2 à la place d'un 1, et ça se comprend complètement !

Cidrolin · April 2019

La suite de $1$ et $2$ que vous observez est liée aux réduites indiquées ci-dessus (Markov 1882).

Cidrolin · April 2019

Le développement en fraction continue de $\frac{\ln3}{\ln2}$ est $\{1,1,1,2,2,3,1,5,2,\dots\}=\{a_0,a_1,a_2\dots\}$.

Au lieu de $1$, on va écrire $c$, et $d$ à la place de $2$.
On construit une suite en posant: $c_0=c\,;\quad c_1=(c)^{a_1-1}d\quad$ et $\, c_{j+1}=(c_j)^{a_{j+1}-1}c_{j-1}c_j$.

Ici $(x)^n$ signifie la concaténation $xxxx...x\quad$($n$ fois)

Nous obtenons :
$c_0=1$
$c_1=(c)^0d=2$
$c_2=(c_1)^0c_0c_1=12$
$c_3=(c_2)^1c_1c_2=12212$
$c_4=(c_3)^1c_2c_3=122121212212$
$c_5=$ un mot de longueur $41$

En concaténant les $c_j$ on obtient la suite cherchée.

nodgim · April 2019

OK Cidrolin. Quoique, utiliser les fractions continues pour trouver cette suite me semble être un détour pas forcément efficace..... Il y a bien plus rapide !

Cidrolin · April 2019

J'ai utilisé ce [size=large]pdf[/size] de R. Nillsen, K. Tognetti et G. Winley. La méthode est décrite page 12.

nodgim · April 2019

OK Cidrolin, merci.

De mon coté, je n'arrive pas à justifier cette histoire de " précession du 2 " tous les 53 bits, puis sans doute, tous les 665 bits, mais bon c'est peut être faux.....

lourrran · April 2019

Qu'appelles-tu 'Précession du 2 tous les 53 bits' ?
La suite que tu as définie est 'quasiment périodique', de période 12, ou 41, ou 53, ou 306, ou 665 ... L'expression 'quasiment périodique' est floue. Quasiment n'est pas un terme mathématique. Mais on peut la reformuler :

Pour environ 99% des entiers $U_{n+41} = U_n$
La proportion peut même être plus élevée : pour 99.8% des entiers, $U_{n+53} = U_n$

C'est cette propriété là que tu veux démontrer ? ou bien ceci est acquis, et c'est autre chose qui te bloque ?

Cidrolin · April 2019

En utilisant le vocabulaire de C. Kimberling je propose le terme : "périodicité sournoise" ou "devious periodicity".

nodgim · April 2019

@ Cidrolin : quelque chose ne va pas dans la suite que tu as amorcée : ce n'est pas 122...mais 121....
Et pourtant, tu n'as pas fait d'erreur en appliquant ton algorithme. Sans doute une correction à faire dans celui-ci ?