Montrer que tout entier peut s'écrire comme la somme de puissances de 2 distinctes

Salut à tous (ça fait longtemps ),

l’objet de ce topic tient sur une question d’un exercice de spé maths (terminale S) que je n’arrive pas à traiter.

Voici la question en cause :

Établir un algorithme décomposant un entier N non nul en une somme de puissances de 2 distinctes. Justifier que cet algorithme s’arrête.

Pour ce qui est de l’algorithme : aucun problème, le voici en langage naturel (je l’ai programmé et testé sur ma calculette) :

Demander N

1 -> K
Tant que N ≥ K
    2*K -> K
Fin Tant que

Tant que N ≠ 0
    K/2 -> K
    Si K ≤ N alors
        N-K -> N
        Afficher K
    Fin Si
Fin Tant que

Le problème réside dans le fait de montrer que ce programme s’arrête, et plus particulièrement la seconde boucle.

En effet, pour la première on sait que $\lim_{x\to+\infty}2^x=+\infty$ et donc par définition il existe $K\in\mathbb{N}$ tel que $2^K>N$.

Pour la seconde, cela revient à montrer que tout entier (naturel) peut être exprimé comme une somme de puissances de 2 distinctes. Et pour cela je galère pas mal. À mon avis il faut quelque part utiliser le fait que :

$\forall n \in\mathbb{N}, 2^n+2^n = 2\times 2^n = 2^{n+1}$

j’ai aussi pensé utiliser une preuve par récurrence mais je n’arrive pas à faire aboutir l’hérédité et je pense que mon plus gros problème est que je ne sais pas vraiment comment écrire la somme de puissances de 2 distinctes mathématiquement.

Merci d’avance pour votre aide.

Tu peux aussi te demander ce qu’une écriture binaire d’un nombre entier signifie

Oui, c’est l’objectif final de l’exo, l’idée que par exemple :

$1010011_2 = 1×2^6 + 0×2^5 + 1×2^4 + 0×2^3 + 0×2^2 + 1×2^1 + 1×2^0$

Pas besoin de raisonner finement sur la décomposition pour montrer que la seconde boucle termine, il suffit de montrer une quantité qui décroit strictement à chaque étape, et qui ne peut pas décroire strictement pendant un temps infini. Ici, je proposerais de remarquer que N décroit strictement à certaines étapes de la boucle (donc il va forcément finir par devenir nul ou négatif; écrire N > 0 comme condition de boucle rend le raisonnement plus simple), et de réfléchir à la répartition des tours de boucles où N ne décroit pas strictement (tu as un problème s’il peut y en avoir un nombre infini, sans étape strictement décroissante au milieu).

Édit : ce message correspond à une réponse à la remarque d’Holosmos, @gasche, je réflichis sur ton message

J’arrive à quelque chose en utilisant une récurrence forte.

Initialisation : On a $n = 1 = 2^0$ qui s’écrit bien comme une somme de puissances de deux distinctes.

Hérédité : On fixe $n \in \mathbb{N}$, supposons que tout $k < n$ s’écrit comme une somme de puissances de deux distinctes et montrons que cette propriété s’applique aussi à $n$.

Soit $m\in\mathbb{N}$, le plus grand entier tel que $2^m \le n$.

On a $(n,2^m)\in\mathbb{N^2}$ donc par la division euclidienne :

$\exists! (q,r)\in\mathbb{N}^2 / n = q\times 2^m + r \, \text{avec } 0 \le r < 2^m$

Montrons maintenant que $q=1$.

Supposons par l’absurde que $q\ge 2$, alors :

$n = q\times 2^m +r = (q-2+2)\times 2^m +r = 2^{m+1} + (q-2)\times2^m + r$

ce qui implique $k \ge 2^{m+1}$ car $(q-2)\times2^m + r \ge 0$.

Donc par définition de $m$, on aboutit à $m \ge m+1$, ce qui est absurde.

Notre hypothèse de départ est fausse, donc $q=1$.

Ainsi, on a :

$n = 1\times 2^m + r \text{ avec } 0 \le r < 2^m$

Or $r<2^m\le n$ donc par hypothèse, $r$ s’écrit comme une somme de puissance de 2 distinctes.

De plus $r<2^m$, donc $n$ s’écrit comme une somme de puissance de 2 distinctes.

Conclusion : par principe de récurrence, tout entier naturel s’écrit comme une somme de puissances de 2 distinctes.

Pour répondre à la remarque de @gasche.

J’avais pensé vite fais à remplacer $N≠0$ par $N<0$ mais en fait ça ne simplifie pas vraiment le problème puisqu’on vérifie que $K\le N$ avant de retrancher $K$ à $N$. Toutefois on peut le faire, les deux algorithmes sont équivalents.

En effet, si on met comme condition d’arrêt $N<0$ alors la boucle s’arrête ssi $N\le 0$.

Or $N-K \to N$ ssi $K \le N \iff 0 \le K -N$

La valeur finale de $N$ vérifie donc $0\le N \le 0$, ie. $N=0$.

Pour montrer qu’on arrivera toujours à une boucle telle que la valeur de $N$ va décroître strictement, on peut remarquer que $K$ prend les valeurs successives de $f: \mathbb{Z \to R}$ avec $f(x) = 2^x$, quand $x$ tend vers moins l’infini.¹

Or $\lim_{x\to-\infty} f(x) = 0$ donc par définition de la limite, si $ε = N > 0$ :

$\exists K \in \mathbb{Z} / 2^K \le N$

Ainsi, tant que $N>0$ il y aura une boucle telle que $N$ décroît strictement. (ça me parait un peu bancal comme démonstration :/ )

Oui, j’y ai pensé mais on a pas encore vu les logarithmes en cours donc bon…

Par contre je savais pas que l’exécution est plus rapide ainsi, merci