From 22eb7dff95df44c039be489dc37a7d4c90863541 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 12 Apr 2016 15:52:58 +0200 Subject: Finish writing answer to last exercise. --- notes-mitro206.tex | 31 ++++++++++++++++++++++++++++++- 1 file changed, 30 insertions(+), 1 deletion(-) diff --git a/notes-mitro206.tex b/notes-mitro206.tex index eea7e7e..d4fe987 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -6935,7 +6935,36 @@ $n-1$ et/ou de $f_2(n)$, on constate expérimentalement que (A) les valeurs $f_2(n)$ pour $n>0$ ont un nombre impair de $1$ dans leur écriture binaire, et sont même exactement tous ces nombres rangés par ordre croissant, et (B) $f_2(n)$ vaut $2(n-1)$ ou $2(n-1)+1$ selon que -$n-1$ a un nombre impair ou pair de $1$ dans son écriture binaire. +$n-1$ a un nombre impair ou pair de $1$ dans son écriture binaire. Il +est facile de voir que ces affirmations sont équivalentes : les +nombres ayant un nombre impair de $1$ dans leur écriture binaire +s'obtiennent, dans l'ordre, en prenant les écritures binaires des +entiers (ici $n-1$) et en ajoutant le bit $0$ ou $1$ à la fin +(c'est-à-dire en calculant $2(n-1)$ ou $2(n-1)+1$) pour que le nombre +total de bits $1$ soit impair, ce qui donne l'équivalence entre +(A) et (B). + +(Note : certains appellent « odieux » — un jeu de mot sur « odd » en +anglais — les entiers naturels ayant un nombre impair de $1$ dans leur +écriture binaire : voir par exemple \url{http://oeis.org/A000069} +trouvé en entrant les premières valeurs de $f_2(n)$ dans l'OEIS.) + +Montrons les affirmations (A) et (B) conjecturées ci-dessus, en +procédant par récurrence sur $n$, autrement dit, montrons par +récurrence sur $n>0$ que $f_2(n)$ parcourt dans l'ordre tous les +nombres, dits « odieux », ayant un nombre impair de $1$ dans leur +écriture binaire. On a remarqué ci-dessus que $f_2(n)$ est le plus +petit entier naturel non nul qui n'est pas ni sous la forme $f_2(n')$ +pour $0