#!/usr/bin/env python3

def genere(n):
    u = 79
    t = [u % 7]
    for i in range(1, n):
        u = (u * 15487) % 67203
        t.append(u % 7)
    return t

print(genere(10_000))

def nombre_indice(n):
    t = genere(n)
    s = 0
    for i, b in enumerate(t):
        if b == 1:
            s += 1
            if s == 500:
                i0 = i
    return s, i0

print(nombre_indice(10_000))


def fp(g, x):
    h = 1e-8
    return (g(x + h) - g(x)) / h

print(fp(lambda x: x**3 - 3*x**2 + 1, 1))

def newton(f, x, n):
    while abs(f(x)) > 10 ** (-n):
        x -= f(x) / fp(f, x)
    return x

print(newton(lambda x: x**3 - 3*x**2 + 1, 1, 12))

int_to_gray = lambda L, i: L[i]

print(int_to_gray(["01", "10", "00", "11"], 2))

def gray_to_int(L, s):
    for i in range(len(L)):
        if s == L[i]:
            return i

print(gray_to_int(["01", "10", "00", "11"], "11"))

code_suivant = lambda L: [f"0{el}" for el in L] + [f"1{el}" for el in L[::-1]]

print(code_suivant(["01", "10", "00", "11"]))

def get_gray1(n):
    L = list("01")
    for _ in range(1, n):
        L = code_suivant(L)
    return L

print(get_gray1(7))

def flip(s, j):
    return s[:j] + ("0" if s[j] == "1" else "1") + s[j + 1 :]

print(flip("1001", 2))

def get_gray2(n):
    L = ["0" * n]
    for _ in range(1, 2 ** n):
        for i in range(n - 1, -1, -1):
            res = flip(L[-1], i)
            if res not in L:
                L.append(res)
    return L

print(get_gray2(7))

def indice_dernier_un(s):
    for i in range(len(s) - 1, -1, -1):
        if s[i] == "1":
            return i

print(indice_dernier_un("1101010011"))

def get_gray3(n):
    L = ["0" * n]
    for i in range(1, 2 ** n):
        L.append(flip(L[-1], len(L[-1]) - 1))
    else:
        L.append(flip(L[-1], indice_dernier_un(L[-1]) - 1))
    return L

print(get_gray3(7))

def int_to_bin(n0):
    n = n0
    if n == 0:
        return "0"
    res = ""
    while n > 0:
        res = str(n % 2) + res
        n //= 2
    return res

print(int_to_bin(12))

def XOR(b1, b2):
    if b1 == b2:
        return "0"
    return "1"

print(XOR("101", "010"))

def XOR_bit_a_bit(s1, s2):
    d = len(s1) - len(s2)
    res = s1[:d]
    for i in range(len(s2)):
        res += XOR(s1[d + i], s2[i])
    return res

print(XOR_bit_a_bit("101", "010"))

def get_gray4(n):
    L = []
    for i in range(2 ** n):
        s1 = int_to_bin(i)
        s2 = s1[:-1]
        code = XOR_bit_a_bit(s1, s2)
        L.append("0" * (n - len(code)) + code)
    return L

print(get_gray4(7))

def get_prochain_mort(dernier_mort, m, L):
    nb_vivants_vus = 0
    res = dernier_mort
    while nb_vivants_vus < m:
        res = (res + 1) % len(L)
        if L[res]:
            nb_vivants_vus += 1
    return res

print(get_prochain_mort(2, 3, [True] * 8))

def dernier_mort(n, m):
    L = [True] * n
    prochain_mort = (m - 1) % n
    for nb_morts in range(n - 1):
        L[prochain_mort] = False
        prochain_mort = get_prochain_mort(prochain_mort, m, L)
    return prochain_mort

print(dernier_mort(n=8, m=3))