Problème de Josephe avec paramètre $k=2$

En mathématiques et en informatique, le problème de Josephe (ou problème de Joséphus) est lié à certaines formules d'élimination. La formulation classique est :

« Des soldats juifs, cernés par des soldats romains, décident de former un cercle. Un premier soldat est choisi au hasard et est exécuté, le troisième à partir de sa gauche (ou droite) est ensuite exécuté. Tant qu'il y a des soldats, la sélection continue. Le but est de trouver à quel endroit doit se tenir un soldat pour être le dernier. »

On utilise la formulation suivante : on place $n$ personnes sur un cercle et on les numérote de 1 à $n$. On enlève alors du cercle une personne sur $k$ en refermant le cercle après chaque étape. Quel est le numéro $f(n)$ du dernier survivant ?

Question 1. On suppose, dans toute la suite, que $k=2$. Montrer que : $$f(2n)=2f(n)-1,f(2n+1)=2f(n)+1,f(1)=1.$$ Calculer $f(100)$ à partir de cette récurrence.

Question 2. Soit $2^m$ la plus grande puissance de 2 ne dépassant pas $n$. Montrer que : $$f(n)=2(n-2^m)+1.$$ Calculer alors $f(2021)$.

Question 3. Écrire $n$ en binaire et placer son premier chiffre à la fin, montrer que le nombre ainsi obtenu est égal à $f(n)$. Calculer alors $f(10^6)$.