from typing import Iterator
from random import random

# Exercice 2


def ldp(n: int) -> int:
    if n < 0:
        raise ValueError("n not in NN")
    sum_proper_divisors = 0
    for candidate in range(1, n):
        if n % candidate == 0:
            sum_proper_divisors += candidate
    return sum_proper_divisors


def parfaits(K: int) -> Iterator[int]:
    for candidate in range(1, K + 1):
        if ldp(candidate) == candidate:
            yield candidate


def amicaux(K: int) -> Iterator[tuple[int, int]]:
    for p in range(1, K + 1):
        for q in range(1, p):
            if {ldp(p), ldp(q)} == {p, q}:
                yield (p, q)


# Exercice 2


def m(k: int) -> int:
    power = 0
    while k % 2 == 0:
        k //= 2
        power += 1
    return 2 ** power


c_1 = lambda n: (1 + n // m(n)) // 2


def c_2(n):
    if n in {1, 2}:
        return 1
    if n % 2 == 0:
        return c_2(n // 2)
    return n // 2 + 1


print(list(map(c_1, range(1, 16))))


def c_3(n):
    base_2_n = []  # écrite "à l'envers"
    current = n
    while current != 0:
        base_2_n.append(current % 2)
        current //= 2

    print(f"binary \t{list(reversed(base_2_n))}")
    # on enlève les 0s à droite (donc à gauche de la liste)
    while base_2_n[0] == 0:
        base_2_n.pop(0)

    print(f"nozeroes \t{list(reversed(base_2_n))}")
    # on ajoute 1 (b
    switched_idx = 0
    while base_2_n[switched_idx] == 1:
        base_2_n[switched_idx] = 0
        switched_idx += 1
    # était: base_2_n[switched_idx + 1] = 1
    base_2_n[switched_idx] = 1

    print(f"add 1 \t{list(reversed(base_2_n))}")
    base_2_n.append(0)  # guard against overflow
    # on enlève encore les zéros
    while base_2_n[0] == 0:
        base_2_n.pop(0)

    print(f"nozeroes \t{list(reversed(base_2_n))}")
    # remettre en base 10
    result = 0
    for two_power in range(0, len(base_2_n)):
        result += 2 ** two_power * base_2_n[two_power]

    print(f"dec {result}")
    return result


def tirer(n: int) -> list[int]:
    return [int(random() < 0.5) for _ in range(n)]


# def T(seq: list[int]) -> int:
def T(seq):
    pool = tirer(1000)
    for start in range(len(pool)):
        if pool[start : start + len(seq)] == seq:
            return (
                start + len(seq) + 1
            )  # on demande l'indice de fin, basé en 1 et pas 0
    return 0


apparitions_sum = 0
for _ in range(1000):
    apparitions_sum += T([1, 0, 1, 1])
print(apparitions_sum / 1000)