"""
Rationnal root theorem
Stéphane Pasquet - 8/02/2023
https://mathweb.fr/euclide/2022/03/08/le-theoreme-de-la-racine-rationnelle
"""
from fractions import Fraction
from itertools import product

# retourne la liste des diviseurs d'un nombre n

def diviseurs(n):
    D = [];
    for i in range(1 , n+1):
        if n % i == 0:
            D.append(i)

    return D

#

def rational_root(*P): # P = a_nX^n + ... a_0. ex: (4,4,5,-4) pour 4X^3+4X^2+5X-4
    n = len(P)-1 # degré du polynôme
    racines = []
    exposant = n
    for coef in P:
        if exposant == 0:
            monome = ''
        elif exposant == 1:
            monome = 'X'
        else:
            monome = f'X^{exposant}'
            
        if coef > 0 and exposant == n:
            if coef == 1:
                P_text = f'{monome}'
            else:
                P_text = f'{coef}{monome}'
        elif coef > 0 and exposant != n:
            if coef == 1:
                P_text += f' +{monome}'
            else:
                P_text += f' +{coef}{monome}'
        elif coef < 0:
            if coef == -1 and exposant != 0:
                P_text += f' -{monome}'
            elif coef == -1 and exposant == 0:
                P_text += f' -1'
            else:
                P_text += f' {coef}{monome}'
        exposant -= 1
    
    print(f'Liste des racines rationnelles du polynôme {P_text}:')

    L = product( diviseurs(abs(P[-1])) ,  diviseurs(abs(P[0])) )
    
    for e in L:
        R = [ Fraction(e[0],e[1]), Fraction(-e[0],e[1]) ] # racines à tester
        for r in R:
            s = 0
            exposant = n
            for coef in P:
                s += coef*(r.numerator**exposant)*(r.denominator**(n-exposant))
                exposant -= 1
            
            if s == 0 and r.__str__() not in racines:
                racines.append(r.__str__())
                
    return racines
    
print( rational_root(4,4,5,-4) )
print( rational_root(1,0,-1) )
print( rational_root(1,1,-1) )