Algorithmes et histoire des mathématiques

Un procédé inspiré de calculs babyloniens anciens consiste à doubler une valeur et à lui ajouter $1$, ceci plusieurs fois de suite. On traduit ce procédé par le programme Python suivant :

x = a
for i in range(3):
    x = 2 * x + 1

À la fin de l'exécution de ce programme, la variable x vaut $47$.

En remontant les étapes du calcul une à une, déterminer la valeur initiale introduite dans la variable a.

Saisir la valeur initiale a :

On considère le programme Python ci-dessous, inspiré de la méthode historique de multiplication par duplication (dite « multiplication égyptienne ») :

a = ...
b = 6
p = 0
while b > 0:
    if b % 2 == 1:
        p = p + a
    a = a * 2
    b = b // 2

On cherche à retrouver la valeur initiale attribuée à la variable a au début du programme.

Pour cela, suivre les étapes suivantes :

1. Dresser le tableau d'exécution du programme étape par étape en exprimant la valeur de la variable p en fonction de la valeur initiale de a.
2. En déduire la valeur initiale de a sachant qu'à la fin de l'exécution, la variable p contient la valeur $48$.

Saisir la valeur initiale de la variable a.

Un texte mathématique de l'Égypte antique (conservé sur le papyrus Rhind) décrit une méthode pour effectuer des calculs en utilisant uniquement des divisions par $2$ (médiations) et des multiplications par $2$ (duplications).

Le programme Python suivant traduit cette méthode historique :

a = 13
b = 11
p = 0
while a > 0:
    if a % 2 == 1:
        p = p + b
    a = a // 2
    b = b * 2

Saisir la valeur de la variable p à la fin de l'exécution du programme.

Au I^er siècle, le mathématicien Théon de Smyrne étudie des algorithmes arithmétiques basés sur la mise à jour simultanée de deux grandeurs entières pour calculer des approximations de racines carrées.

On considère le programme Python ci-dessous, qui reproduit l'une de ces méthodes historiques pour approcher $\sqrt{3}$ :

a = 1
b = 1
n = 0
while a <= 300:
    temp_a = a
    a = a + b
    b = 3 * temp_a + b
    n = n + 1

Saisir la valeur de la variable n à la fin de l'exécution de cet algorithme.