Puissances de 3 en binaire

Bonjour gai requin,

Inspiré de ce qui est écrit à propos de la suite A020914, je pense qu'on a l'équivalent suivant \[{u_n} \sim \frac{{{{\log }_2}3}}{2}n\]

Si elle est vraie, je ne pense pas que ta conjecture soit démontrable avec des outils élémentaires... Il est déjà bien assez difficile de prouver que $u_n$ tend vers $+\infty$ !

Senge et Straus (voir cet article, qui n'a pas l'air consultable gratuitement sur le net) ont prouvé que si $g$ et $h$ sont deux entiers $>1$ tels que $\frac{\ln g}{\ln h} \not \in \mathbb{Q}$, alors $\displaystyle \lim_{n \rightarrow +\infty}S_g(h^n)=+\infty$ (où $S_g(h^n)$ désigne la somme des chiffres de l'écriture en base $g$ de $h^n$). En particulier pour $g=2$ et $h=3$, on trouve $\displaystyle \lim_{n \rightarrow +\infty}u_n=+\infty$.

Lorsque $\frac{\ln g}{\ln h} \in \mathbb{Q}$, il est parfois plus facile d'étudier le comportement de $S_g(h^n)$ (voir par exemple cette discussion).

Un bon exercice (résoluble, lui, avec des outils élémentaires) consiste à essayer de prouver que $\displaystyle \limsup_{n \rightarrow +\infty} u_n=\displaystyle \limsup_{n \rightarrow +\infty} v_n=+\infty$.

Une petite recherche sur le forum donne également cela : http://www.les-mathematiques.net/phorum/read.php?5,591252,591252#msg-591252

A mon sens le truc revient à dire que la probabilité qu'un bit de $3^n$ pris au hasard vaut $1$ est égale à $1/2$. On peut alors changer notre vision du problème en inversant l'écriture binaire de $3^n$ et en utilisant le fait que les résidus de puissances modulo d'autres puissances sont périodiques. Je m'explique. Si on écrit $3^n$ en binaire en introduisant des suites $\alpha_i(n)$:
$$3^n=...\alpha_3(n)\alpha_2(n)\alpha_1(n)\alpha_0(n)$$
Alors je crois qu'on peut montrer que les suites $\alpha_i(n)$ pour $i>1$ sont périodiques de période $2^{n-1}$ (chose connue il me semble en général, je n'ai pas trouver encore les références). Il faudrait alors montrer que chaque période contient "quasi" autant de $1$ que de $0$ (ils sont répartis en vrac dans la période). Pour illustrer ce que je dis en écrivant $3^n$ en binaire et à l'envers on obtient:

[1, 1]
[1, 0, 0, 1]
[1, 1, 0, 1, 1]
[1, 0, 0, 0, 1, 0, 1]
[1, 1, 0, 0, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1]
[1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1]
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1]
[1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1]
[1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1]

Et on observe bien que la colonne $m$ est une suite d'éléments périodiques de période $2^{m-2}$. Ainsi la colonne $5$ donne $11110001111000...$ une suite périodique de période $8$ et contenant autant de $0$ que de $1$. Donc la probabilité que $\alpha_4(n)=1$ lorsque $n$ tends vers l'infini est égal à $1/2$. Si en général on pouvait montrer:
$$P(\alpha_i(n)=1)=1/2+\epsilon(i)$$
avec $\lim_{i\rightarrow\infty}\epsilon(i)=0$ (en fait je pense que $\epsilon(i)=O(1/i)$) alors on ne serait pas loin. Ceci manque de rigueur bien évidemment mais l'idée est là.

Bien vu blaaang. La difficulté est effectivement de passer des colonnes aux lignes étant donné que la longueur des périodes rend impossible d'en déduire immédiatement quelque chose. Disons que ma façon de voir les choses explique intuitivement ce qui se cache derrière tout ça en regardant les premières colonnes. Si je n'ai pas d'argument très clair pour l'instant, il est évident selon moi qu'il y a quelque chose de probabiliste à considérer.

Il apparait qu'il y a dans la période de la colonne $j$ de longueur $2^{j-2}$ exactement autant de $1$ que de $0$ (à prouver!). Chaque colonne $j$ est donc comme une roulette avec $2^{j-3}$ $0$ et autant de $1$ mélangés. Donc en regardant les choses "verticalement" et heuristiquement, pour $n$ grand, on peut imaginer que $\displaystyle P(\alpha_i(n)=1)=1/2+\epsilon(i)$ pour $i$ de l'ordre de $\log(n)$. Ce qui n'est pas suffisant pour en déduire que la conjecture de Ed Pegg-Gairequin-XX soit vraie sur toute la ligne de longueur de l'ordre de $n$. Il faudrait que ce soit vrai pour $i<<n$ et qu'il y ait une certaine indépendance entre les suites $\alpha_i$.

Bref il y a une double probalilité, celle de la roulette des colonnes et celle se trouvant dans chaque période et dont la contribution est en fait plus importante. Il faudrait donc maintenant s'atteler à l'étude de la répartition des $1$ et $0$ dans nos périodes de longueur $2^{j-2}$.
Le fait qu'apparemment il y a exactement autant de $1$ que de $0$ dans chaque période rend à première vue la tâche plus aisée. Je veux dire que l'étude des colonnes est a priori plus abordable que l'étude des lignes.

En espérant être audible!

En appelant la période de la colonne $j$ par $P(j)$, un vecteur de longueur $2^{j-2}$, j'essaye actuellement de voir comment les $2^{j-3}$ zéros et les $2^{j-3}$ uns se répartissent. Il faudrait qu'un certain hasard gouverne cette répartition pour aller plus loin avec cette idée. Mais le fait de probabiliser la question montre peut être aussi une certaine indécidabilité du problème, ce qui rejoint le genre de question que les chercheurs se posent sur le problème "$3x+1$".

Oui il y a une régularité dans ce désordre ambiant. Quelques expériences confirme aussi mon intuition sur le fait que dans chacune des période il y a exactement autant de 1 que de 0. Ce serait en soi un joli résultat d'arithmétique. Malheureusement il est difficile de dire quelque chose sur la répartition géographique des 1 et des 0 dans ces périodes P(j). Voilà par exemple P(10) où les termes sont regroupés par paquets de 32:

11111100111000111100111111000000 (19 uns)
11100001111111111001001010111111 (22 uns)
10100001100010001000011111111011 (16 uns)
11110100110110011100011111101110 (21 uns)
00000011000111000011000000111111 (13 uns)
00011110000000000110110101000000 (10 uns)
01011110011101110111100000000100 (16 uns)
00001011001001100011100000010001 (11 uns)

On voit ô miracle qu'il y a 128 uns mais de là à dire qu'il sont répartis selon une règle il y a un pas que je ne franchis pas... En résumé les colonnes sont périodiques et contiennent donc autant de 1 que de zéros en moyenne. Au sein de chaque période ces 1 et 0 semblent répartis "au hasard". Cela suggère donc que si on pioche une case au hasard dans notre triangle de 0 et 1 on a intuitivement 1 chance sur 2 pour que ce soit un un.

Je doute que l'on puisse rigoureusement le montrer. Ceci dit le fait que $\frac{b(3^{n})-\left(\frac{\log3}{\log2}\right)\frac{n}{2}}{\log n}$ semble borné voire converge vers une limite indique que la répartition obéit à une loi assez précise.

Mais oui, Sylvain, il semble bien que tu aies raison ! La deuxième moitié de la période d'une colonne semble se déduire de la première en échangeant 1 et 0 !

Je suis le fil également, de mon côté contrairement à la base 2, j'ai voulu observer ce qui se passe dans la base 10 au niveau de la longueur de la périodicité de la j-ième décimale de la suite t définie par t(n)=3^n , n>=1.
j'y ai observé des règles, en notant d_j(n) j-ième décimale de t(n) et P(h) la périodicité d'une suite.
d_1(n)=3,9,7,1,3,9,7,1,3,9,7,1,...
P(d_1)=4
d_2(n)=2,8,4,2,8,6,8,4,4,4,2,6,0,2,6,8,6,0,0,0,2,8,4,2,8,6,8,4,4,4,2,6,0,2,6,8,6,0,0,0,2,8,4,... (partie périodique se termine avec 3 zéros)
(on commence n par 3, car c'est à partir de n=3 qu'on voit apparaître les chiffres des centaines)
P(d_2)=20
d_3(n)=2,7,1,5,6,....,0,0,0,0,0,2,7,1,5,6,.... (partie périodique se termine avec 5 zéros)
P(d_3)=100
J'ai ensuite calculé que : P(d_4)=500, P(d_5)=5000, P(d_6)=50000. J'avais pensé que P(d_n)/P(d_(n-1))=5, mais quand j'ai calculé P(d_5) j'ai vu 5000 et non 2500. Ceci dit je pense quand même qu'il y a une règle.

C'est correct pour moi ta démo Blaang (mais ce n'était pas une conjecture, juste un exercice;)). On avance, on avance... Cette équiprobabilité $P(\alpha_i(n)=1)=1/2$ marche donc pour tout $i$ fixé et $n$ tendant vers $\infty$. Il reste quand même encore à voir si la distribution des zéros et des uns dans la première demi-période est asymptotiquement la même pour $i$ fixé et de l'ordre de $n$ et si pour $n$ grand on peut considérer les suites $\alpha_i(n)$ indépendantes pour $i=3,4,5,...$ dans un sens à préciser. J'ai l'impression qu'à un moment on va tourner en rond :S. Mais ne soyons pas pessimistes, une petite étude statistique s'impose avant d'abdiquer.

Et si gai requin suit le fil qu'il a lancé : peut-il nous dire d'où il tient cette question ??

Je ne dénigre pas ce résultat blaang. C'est très joli d'avoir mis en évidence et démontré le phénomène "Thue-Morse" dans les périodes. Toujours en procédant par étape, d'un point de vue purement probabiliste, il serait peut être intéressant de répondre à cette question:

Soit $\alpha_i(n)$ des suites de $0$ et $1$ périodiques de période de longueur $2^{i-2}$. En supposant que chaque période contient exactement le même nombre de $1$ que de $0$, quelle est la probabilité lorsque $n$ tend vers l'infini pour que $\alpha_3(n),\alpha_4(n),...,\alpha_m(n)$ soient à moitié égaux à $1$? Autrement dit la question importante est de savoir lorsque $n$ tend vers l'infini à quelles conditions sur les périodes ces valeurs peuvent être considérées comme indépendantes?

Par exemple si $\alpha_4(n)=[0,1,1,0,....]$ et $\alpha_5(n)=[1,1,1,0,0,0,0,1,....]$ que vaut:
$P(\alpha_5(n))=1-\alpha_4(n)$? Ici c'est simple car il faut regarder combien de valeurs ne coincident pas en doublant la période de $\alpha_4(n)$ et en la comparant à celle de $\alpha_5(n)$ (on suppose qu'on a synchronisé les périodes). Dans ce cas la proba c'est $3/8$.

On voit alors que le problème dans le cas général peut rapidement devenir compliqué... Je crois que nos résultats permettent finalement juste d'avoir l'intuition que la conjecture initiale est vraie.

Il y a un lien tout bête entre les lignes et les colonnes. Du moins entre la somme des $1$ dans les lignes et nos périodes dans les colonnes. En notant $b_1(n)$ le nombre de $1$ dans l'écriture binaire de $n$ alors en définissant la suite $c_i(n)$ par:
$$c_{i}(n)=b_{1}\left(\left\lfloor \frac{3^{n}}{2^{i}}\right\rfloor \right)-b_{1}\left(\left\lfloor \frac{3^{n}}{2^{i+1}}\right\rfloor \right)$$
Alors on a : $$c_i(n)=\alpha_i(n)$$
où les $\alpha_i(n)$ sont nos suites périodiques dans les colonnes définies plus haut. On a donc en particulier pour $n>0$ :
$$b_{1}\left(3^{n}\right)=1+b_{1}\left(\left\lfloor \frac{3^{n}}{2}\right\rfloor \right)$$
Mais plus généralement vu le théorème de blaang (et un peu de réflexion) on peut dire que :
$$b_{1}\left(3^{n}\right)-b_{1}\left(\left\lfloor \frac{3^{n}}{2^i}\right\rfloor \right)$$
est une suite périodique de période de longueur $2^{i-2}$ et dont la moyenne des termes de la période vaut tout simplement $i/2$. On peut ensuite utiliser cette formule jusqu'à $i$ à peu près égal à $\log(3^n)/\log(2)$ .... Et puis c'est tout pour l'instant...

Si ça t'intéresse blaang tu as cet article ou quelques résultats de suites non triviales modulo 3 ont été démontrés après avoir été suggérés par l'expérimentation Motzkin mod3.