# exercice 1
def recherche(n):
    L = []
    for p in range(2,n+1):
        x = (2 ** (p-1) - 1) % (p * p)
        if x == 0:
            L.append(p)
    return L

# exercice 2
def carres(n):
    p = 0
    C = []
    while p * p <= n:
        C.append(p * p)
        p = p + 1
    return C

def triangles(n):
    p = 0
    C = []
    while p * (p + 1) // 2 <= n:
        C.append(p * (p + 1) // 2)
        p = p + 1
    return C

def inter(L,M):
    n = len(L)
    N = []
    for i in range(n):
        if L[i] in M:
            N.append(L[i])
    return N

def carrestriangles(n):
    return inter(carres(n), triangles(n))

# exercice 3
def retourne(n):
    s = str(n)
    p = len(s)
    t = ""
    for k in range(p):
        t = t + s[p-1-k]
    return int(t)

def palindrome(n):
    return (n == retourne(n))

def palindromes(n):
    L = []
    for k in range(n+1):
        if palindrome(k):
            L.append(k)
    return L

def paldiv(n,p):
    L = []
    for k in range(n+1):
        if palindrome(k) and k % p == 0:
            L.append(k)
    return L


# exercice 4
def pgs(L):
    n = len(L)
    g = 0
    d = -1
    s = 0
    for i in range(n):
        for j in range(i,n):
            t = sum(L[i:(j+1)])
            if t > s:
                s = t
                g = i
                d = j
    return [L[g:(d+1)],s]



# exercice 5
def liste(n):
    L = [0] * n
    L[0] = 1
    L[-1] = 1
    return L

def f(L):
    n = len(L)
    M = [0] * n
    for i in range(n):
        M[i] = abs(L[i] - L[(i+1) % n])
    return M

def position(x,L):
    n = len(L)
    i = 0
    while i < n and L[i] != x:
        i = i + 1
    if i == n:
        return -1
    else:
        return i

def entiers(L):
    Ls = [L]
    M = f(L)
    i = 0
    while not(M in Ls):
        Ls.append(M)
        M = f(M)
        i = i + 1
    k = position(M,Ls)
    p = i - k + 1
    return [k, p]

def maxper(n2):
    m = 0
    for i in range(3,n2+1):
        L = liste(i)
        r = entiers(L)
        p = r[1]
        if p > m:
            m = p
    return m

# test : maxper(18) = 819, maxper(20) = 9709