################################################################################
#           TP 4 d'informatique - MPSI - Boucles while - 03/11/2026            #
#                                  Correction                                  #
################################################################################

###########################################
# Exercice 1. Fonctions mystères
###########################################

################
### Question 1
################

def g():
    a = 1
    while a < 100:
        a = 67 + (-1)**a * (a//2)
    return a

# Voici les valeurs de a a la fin de chaque tour de boucle:
# Fin 1er tour: a = 67
# Fin 2eme tour: a = 34
# Fin 3eme tour: a = 84
# Fin 4eme tour: a = 109
# Donc g() vaut 109

### Tests:

# print(g())

################
### Question 2
################

def h():
    a = 1
    while a < 100:
        a = 4 + (-1)**a * (a//2)
    return a

# Voici les valeurs de a a la fin de chaque tour de boucle:
# Fin 1er tour: a = 4
# Fin 2eme tour: a = 6
# Fin 3eme tour: a = 7
# Fin 4eme tour: a = 1
# Fin 5eme tour: a = 4
# On retombe sur la meme valeur, on a donc une boucle infinie et la
# fonction ne termine jamais.

### Tests:

# print(h())

###########################################
# Exercice 2.
###########################################

def f(n):
    s = 0
    m = 0
    while s < n:
        m = m + 1
        s = s + m**4
    return m

###########################################
# Exercice 3. Préfixes, facteurs et sous-mots
###########################################

################
### Question 1
################

def est_prefixe(s1, s2):
    i = 0
    while i < len(s1) and i < len(s2) and s1[i] == s2[i]:
        i = i+1
    return i == len(s1)

################
### Question 2
################

# t représente la taille de la chaîne de caractères s3 évoquée dans l'énoncé.
def est_facteur(s1, s2):
    t = 0
    while t <= len(s2) and not est_prefixe(s1, s2[t:]):
        t = t+1
    return t <= len(s2)

################
### Question 3
################

def est_sous_mot(s1, s2):
    i1 = 0
    i2 = 0
    while i1 < len(s1) and i2 < len(s2):
        if s1[i1] == s2[i2]:
            i1 = i1 + 1
        i2 = i2 + 1
    return i1 == len(s1)

###########################################
# Exercice 4. Persistance multiplicative
###########################################

################
### Question 1
################

def prod_chiffres(n):
    assert n >= 0
    if n == 0:
        return 0
    p = 1
    while n > 0:
        p = p * (n % 10)
        n = n//10
    return p

### Tests:

# print(prod_chiffres(0))
# print(prod_chiffres(1))
# print(prod_chiffres(6))
# print(prod_chiffres(473))
# print(prod_chiffres(678))
# print(prod_chiffres(720))
# print(prod_chiffres(15638))

################
### Question 2.a
################

# La persistance multiplicative de 678 est 4:
# 678 -> 336 -> 54 -> 20 -> 0

################
### Question 2.b
################

def pers_mult(n):
    assert n >= 0
    res = 0
    while n >= 10:
        n = prod_chiffres(n)
        res += 1
    return res

### Tests:

# print(pers_mult(0))
# print(pers_mult(1))
# print(pers_mult(6))
# print(pers_mult(473))
# print(pers_mult(678))
# print(pers_mult(720))
# print(pers_mult(15638))

################
### Question 3.a
################

# On a N_2 = 25 et N_3 = 39.
# Pour le montrer, calculons les persistances mutiplicatives de tout les n >= 10
# jusqu'à obtenir N_2 et N_3:
# 10 -> 0
# 11 -> 1
# 12 -> 2
# 13 -> 3
# 14 -> 4
# 15 -> 5
# 16 -> 6
# 17 -> 7
# 18 -> 8
# 19 -> 9
# 20 -> 0
# 21 -> 2
# 22 -> 4
# 23 -> 6
# 24 -> 8
# 25 -> 10 -> 0
# 26 -> 12 -> 2
# 27 -> 14 -> 4
# 28 -> 16 -> 6
# 29 -> 18 -> 8
# 30 -> 0
# 31 -> 3
# 32 -> 6
# 33 -> 9
# 34 -> 12 -> 2
# 35 -> 15 -> 5
# 36 -> 18 -> 8
# 37 -> 21 -> 2
# 38 -> 24 -> 8
# 39 -> 27 -> 14 -> 4

################
### Question 3.b
################

def get_Nk(k):
    n = 0
    while pers_mult(n) != k:
        n += 1
    return n

### Tests:

# for k in range(10):
#     print(k, get_Nk(k))

###########################################
# Exercice 5. Conjecture de Syracuse
###########################################

################
### Question 1
################

def suivant(un):
    """suivant(un: int) -> int"""
    assert un > 0
    if un % 2:
        return 3*un + 1
    else:
        return un//2

### Tests:

# print(suivant(0))
# print(suivant(15))
# print(suivant(82))

################
### Question 2
################

def temps_vol(N):
    """temps_vol(N: int) -> int"""
    assert N > 0
    n = 0
    un = N
    while(un != 1):
        n += 1
        un = suivant(un)
    return n

### Tests:

# print(temps_vol(-5))
# print(temps_vol(1))
# print(temps_vol(2))
# print(temps_vol(15))
# print(temps_vol(27))

################
### Question 3
################

def temps_vol_altitude(N):
    """temps_vol_altitude(N: int) -> int"""
    assert N > 1
    n = 0
    un = N
    while(un >= N):
        n += 1
        un = suivant(un)
    return n-1

### Tests:

# print(temps_vol_altitude(1))
# print(temps_vol_altitude(2))
# print(temps_vol_altitude(19))
# print(temps_vol_altitude(31))

################
### Question 4
################

def altitude_max(N):
    """altitude_max(N: int) -> int"""
    assert N > 0
    maxi = N
    un = N
    while (un != 4):
        un = suivant(un)
        if (maxi < un):
            maxi = un
    return maxi

### Tests:

# print(altitude_max(0))
# print(altitude_max(1))
# print(altitude_max(21))
# print(altitude_max(83))

###########################################
# Exercice 6. Persistance multiplicative - bis
###########################################

# Pour l'instant, on fixe un entier k >= 3, on note L(N_k) la liste des chiffres
# de N_k.
# ----------------
# On remarque que la liste L(N_k) a les propriétés suivantes:
# (*) L(N_k) ne contient pas de 0.
#     En effet, si c'était le cas, le produit des chiffres de N_k serait 0 ce
#     qui contredit le fait que la persistance multiplicative de N_k est égale à
#     k qui est >= 3.
# (*) L(N_k) ne contient pas de 1.
#     En effet, sinon on pourrait supprimer ce 1 de l'écriture de N_k. Si on
#     note n le nombre obtenu, on a n < N_k et n a la même persistance
#     multiplicative que N_k. Cela contredit la minimalité de N_k.
# (*) L(N_k) est triée par ordre croissant.
#     En effet, sinon on pourrait trier les chiffres de N_k par ordre
#     croissant. Si on note n le nombre obtenu, on obtient la même contradiction
#     que dans le cas précédent.
# (*) L(N_k) ne peut pas contenir plusieurs fois le chiffre 2. Idem pour 3, 4, 6
#     Si N_k contient deux fois le chiffre 2, on pourrait les remplacer par un
#     seul 4. Si on note n le nombre obtenu, on obtient la même contradiction
#     que dans le cas précédent.
#     De même, on peut remplacer deux 3 par un 9, deux 4 par un 2 et un 8, deux
#     6 par un 4 et un 9.
# (*) L(N_k) ne peut pas contenir à la fois un chiffre pair et 5.
#     Sinon, soit n le produit des chiffres de N_k, alors le dernier chiffre de
#     n est un 0 et donc le produit des chiffres de n est 0, ce qui contredit le
#     fait que la persistance multiplicative de N_k est k >= 3.
# ----------------
# Dans la suite pour un chiffre c, on utilisera la notation c* pour indiquer
# qu’il existe un entier l >= 0 tel que le chiffre c se répète l fois. Par
# exemple, on dira que "n1 est de la forme 29*" si le chiffre de poids fort de
# n1 est 2 et que tous ses autres chiffres sont des 9 ; c’est à dire si n1
# appartient à {2; 29; 299; 2999; 29999; ...}
# De même, "n2 est de la forme 9*" et "n3 est de la forme 57*9*" signifient que:
# n2 appartient à {9; 99; 999; 9999; ...}
# n3 appartient à {5; 57; 577; 5777; 57777; ...} ou
#                 {59; 579; 5779; 57779; 577779; ...} ou
#                 {599; 5799; 57799; 577799; 5777799; ...} ou
#                 ...
# ----------------
# On suppose que le chiffre de poids fort de N_k est un 2, montrons que N_k est
# de la forme 267*8*9* ou 27*8*9*:
# Par ce qui précède, on sait que L(N_k) est triée par ordre croissant, ne peut
# pas contenir d’autre 2 et ne peut pas contenir de 5.  Si le 2ème chiffre de
# poids fort de N_k était un 3 (resp. 4), alors on pourrait remplacer les deux
# chiffres de poids fort par 6 (resp. 8) pour obtenir un nombre strictement plus
# petit avec la même persistance multiplicative ; ce qui constitue une
# contradiction.  Ainsi, le 2ème chiffre de poids fort de N_k est 6, 7, 8 ou
# 9. Comme L(N_k) est triée et que 6 y apparaît au plus une fois, Nk est de la
# forme 267*8*9* ou 27*8*9*.
# ----------------
# Avec le même raisonnement, on peut montrer que N_k est nécessairement de l’une
# des huit formes suivantes :
# 267*8*9*, 27*8*9*, 355*7*9*, 37*8*9*
# 47*8*9*, 55*7*9*, 67*8*9*, 7*8*9*
# ----------------
# Pour calculer N_k, on génère tous les entiers de l'une des huit formes
# ci-dessus jusqu'à trouver N_k.

# Cette fonction renvoie une liste contenant tous les entiers ayant m chiffres
# et dont les chiffres sont dans L (si i < j, le chiffre L[i] ne peut pas
# apparaître après L[j] dans les nombres obtenus).
# Par exemple, generer([1,2,3], 4) s'évalue en:
# [1111, 1112, 1113, 1122, 1123, 1133, 1222,
#  1223, 1233, 1333, 2222, 2223, 2233, 2333, 3333]
def generer(L, m):
    M = [(0, L[:])]
    for _ in range(m):
        M_nv = []
        for (n, L2) in M:
            for i in range(len(L2)):
                t = (10*n + L2[i], L2[i:])
                M_nv.append(t)
        M = M_nv
    return [n for n,_ in M]

# Cette fonction concatène les entiers n et m.
# Par exemple, avec n = 12 et m = 34, on obtient 1234.
def concat(n, m):
    return int(str(n) + str(m))

def get_Nk_bis(k):
    if k == 0:
        return 0
    elif k == 1:
        return 10
    elif k == 2:
        return 25
    m = 2
    L = []
    while len(L) == 0:
        L = L + [concat(26, n) for n in generer([7,8,9], m-2)]
        L = L + [concat(2,  n) for n in generer([7,8,9], m-1)]
        L = L + [concat(35, n) for n in generer([5,7,9], m-2)]
        L = L + [concat(3,  n) for n in generer([7,8,9], m-1)]
        L = L + [concat(4,  n) for n in generer([7,8,9], m-1)]
        L = L + [concat(5,  n) for n in generer([5,7,9], m-1)]
        L = L + [concat(6,  n) for n in generer([7,8,9], m-1)]
        L = L + [n             for n in generer([7,8,9], m)]
        L = [n for n in L if pers_mult(n) == k]
        m += 1
    return L[0]

### Tests:

# for k in range(12):
#     print(k, get_Nk_bis(k))