Puissance 2 ou 3
dans Arithmétique
Chaleureux bonsoir à tous .
Une petite question apparemment simple .
La suite $u_n$ est définie par l'ensemble des puissances de $2$ ou $3$ rangés en ordre croissant : $1,2,3,4,8,9,16,27,32,64,81,128,...$
Peut-on écrire tout entier relatif sous la forme $\sum\limits_{n=0}^k\pm u_n$ ?
Merci d'avance ;-)
Domi
PS : pourquoi mon sigma est-il si moche ?
[La commande $\LaTeX$ est \sum et pas \Sigma. ;-) AD]
Une petite question apparemment simple .
La suite $u_n$ est définie par l'ensemble des puissances de $2$ ou $3$ rangés en ordre croissant : $1,2,3,4,8,9,16,27,32,64,81,128,...$
Peut-on écrire tout entier relatif sous la forme $\sum\limits_{n=0}^k\pm u_n$ ?
Merci d'avance ;-)
Domi
PS : pourquoi mon sigma est-il si moche ?
[La commande $\LaTeX$ est \sum et pas \Sigma. ;-) AD]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Domi
-- Schnoebelen, Philippe
[1,3,9,27] On peut écrire tout les nombre entre 1 et 40 (pour le voir il suffit de constater que avec les nombre 1,3 et 9 on peux fair tout les nombre entre 1 et 13 :1=1,2=3-1 3=3,4=1+3,5=9-3-1,6=9-3,7=3-1+9,8=9-1,9=9,10=9+1,11=3-1+9,12=9+3,13=1+3+9 puis comme 27=2*13+1 alor on peux construire tout les nombre entre 1 et 40!) et du coups [1,3,.....,3^n] on poura écrire tout les nombre entre 1 et 1+3+...+3^n ( il suffit de voir que 1+3+..+3^n=2*(1+3+...+3^n-1)+1 et une récurrence..)
@ Side et Sheshe , il faut lire la question :-D
Domi
-- Schnoebelen, Philippe
Je note : $ \forall n \in \N, \:\: \mathcal E_n = \left\{ \displaystyle \sum _{k=0}^n \varepsilon_k u_k \:\mid\: (\varepsilon_ k)_{0\leqslant k \leqslant n} \in \{ -1,1 \}^{n+1} \right\}\:\:\text{et} \:\:\:\displaystyle S_n = \sum_{k=0}^n u_k.$
Avec la relation $\displaystyle \sum_{k=0} ^m 2^k =2^{m+1}-1, \:\:$ on s'assure que : $\forall n \in \N,\:\: u_{n+1} \leqslant S_n.\quad (\star)$
On prouve alors par récurrence que: $\:\forall n \in \N, \quad \mathcal E_n =\Big \{ S_n-2k \:\:|\: \:\:k\in \N,\:\:0\leqslant k\leqslant S_n \Big\}.$
La chose est claire pour $n=0$ car $\mathcal E_0 =\{-1,1\}.$ $\:\:\:\mathcal E_{n+1} = \{-u_{n+1} , u_{n+1} \} + \mathcal E_n\:\:$ et l'inégalité $\:(\star)$, conjuguée à l'hypothèse de récurrence, entraine bien que: $\mathcal E_{n+1} = \Big\{ S_{n+1} -2k\:\mid\: k\in \N,\:\:0\leqslant k \leqslant S_{n+1} \Big \}.$
De cette caractérisation de $\mathcal E_n$, il découle que $\:\:\Z = \displaystyle \bigcup_{n=0}^{+\infty } \mathcal E_n, \:$ et qu'ainsi, tout entier s'écrit sous la forme requise par l'énoncé.
Domi
-- Schnoebelen, Philippe
@ Nicolas Patrois: comment écrirais-tu 2019 ?
@ nodgim et nicolas.patrois
l'algorithme existe depuis une éternité avec les balances à fléaux
on prends les poids en $3^p$ pour p pas trop grand et on fait une division euclidienne avec en base 3
EDIT oups: on ne peut pas prendre 0 comme coeff[ (je viens de lire la question en entier) /color]
Etape 1 : Déterminer le plus grand nombre qu'on va utiliser. Dans la suite $u_n$, on recherche le plus grand n tel que $u_n < X$.
Compter le nombre de puissances de 3 entre $u_0$ et $u_n$ ; si la parité convient, on utilisera n, sinon, on augmente n, pour avoir une puissance de 3 en plus.
Etape 2 : Le plus grand de nos nombres on lui donne le coefficient 1, et on remonte la suite 'à l'envers' (=du plus grand au plus petit). A chaque élément, on lui attribue un coefficient 1 ou -1, selon que la somme actuelle obtenue est supérieure ou inférieure à X.
C'est fini.
Pour 2020, la suite obtenue sera 2187-2048+1024+729+512-256-243+128-81+64+32-27-16+9+8-4+3-2+1
Cela n'a pas l'air facile :-S
Domi
Edit : la suite dont je parle est la somme partielle du premier message .
Pour établir une telle suite qui comporte tous les entiers relatifs, la stratégie consiste à chercher dans l'ordre les plus proches de 0.
uo = 0
u1= u0 + 1 = +1
u2 = u1 - 2 = -1
u3 = u2 + 3 = + 2
u4 = u3 -4 = -2
Pour les autres: soit u(k-1) la dernière valeur utilisée. Soit uj la 1ère puissance de 2 libre, uk la 1ère puissance de 3 libre, et X la valeur qu'on veut obtenir.
On démontre facilement ( il faut chercher un peu tout de même) qu'une série S3 de puissances de 3 consécutives (somme totale dont chaque puissance est affectée d'un + ou d'un - ) autorise l'obtention de n'importe quel entier modulo une puissance de 2 donnée.
On cherche alors la valeur X + uj modulo 2*uj avec cette série S3 à partir de uk. Ensuite, il suffit d'additionner à S3 la série S2 des puissances de 2 consécutives depuis uk et intercalées entre les éléments de S3 et dont la somme vaut -S3+X. La plus forte puissance de 2 de S2 est celle qui est placée immédiatement après la plus forte puissance de S3 ( ou parfois la suivante, si nécessaire et s'il existe 2 puissances de 2 consécutives).
On a l'assurance que X < uj parce que les valeurs cherchées croissent arithmétiquement, alors que uj croît exponentiellement.
Bien entendu, cette stratégie-là fabrique des entiers intermédiaires non désirés ( plusieurs valeurs créées dont la plus petite sera souvent celle qu'on cherche). Aussi, la bijection n'est pas assurée.