# -*- coding: utf-8 -*-
"""
Created on Fri Jan 23 14:29:29 2015

@author: gb
"""

"""
Développement d'un entier naturel en base d en partant des unités
"""
def calcul(C, d): # opération inverse
    """
    Prend une chaîne de chiffres C, teste sa validité et renvoie sa valeur en base d
    """
    S, p = 0, 1
    for chiffre in C[:: - 1]:
        c = int(chiffre)
        if c not in range(d):
            return False
        S += c * p
        p *= d
    return S

def developpement(n, d): # développement de l'entier n en base d, version itérative
    C = ''
    while n != 0:
        q, r = divmod(n, d)
        C = str(r) + C
        n = q
    return C
    
def dev_rec(n, d): # même chose récursivement
    if n == 0:
        return ''
    else:
        q, r = divmod(n, d)
        return dev_rec(q, d) + str(r)

assert calcul('110110', 2) == 54 and calcul('101', 3) == 10 and calcul('21', 2) == False
assert dev_rec(54, 2) == developpement(54, 2) == '110110'


"""
Développement d'un entier naturel en base d en partant du chiffre le plus 
significatif (méthode gloutonne)
"""        
def exposant_max(n, d): # calcule max {m ; n <= d**m} = int(ln(n) / ln(d)) 
    m, p = 0, d
    while n >= p:
        m += 1
        p *= d
    return m
        
assert exposant_max(15, 2) == 3 and exposant_max(16, 2) == 4


def developpement_glouton(n, d):
    C = ''
    m = exposant_max(n, d)
    p = d**m
    while p != 0:        
        e = n // p
        C += str(e)
        n -= e * p 
        p //= d
    return C

def developpement_glouton_2(n, d): # en sautant les étapes donnant des 0
    C = ''
    m1 = exposant_max(n, d)
    while n != 0:
        p = d**m1
        e = n//p
        n -= e * p
        if n != 0:
            m2 = exposant_max(n, d)
        else:
            m2 = -1
        C += str(e) + '0' * (m1 - m2 - 1)
        m1 = m2
    return C
        
     
def dev_glouton_rec(n, d, *args): # un peu acrobatique, pas indispensable...
    if args and n == args[0] == 0:
            return ''
    m = exposant_max(n, d)
    if not args:
        args = m + 1
    else:
        args = args[0]  
    p = d**m
    e = n//p
    n -= e*p
    return '0' * (args - m - 1) + str(e) + dev_glouton_rec(n, d, m)


""" 
Prépériode et période d'un nombre rationnel strictement positif en base 10
"""
def eps(p, q, d):
    """
    Pour des entiers 0 <= p < q, calcule la premiere decimale de p/q
    """
    return (d * p) // q
    

def recherche(L, x):
    """
    Renvoie l'indice de la première occurrence de x dans la liste L et la caractère
    'F' si x n'est pas présent dans L.
    """
    i = 0
    while i < len(L) and L[i] != x:
        i += 1
    if i == len(L):
        return 'F'
    return i 


def decimal(p, q, d): 
    """
    renvoie la partie entière, la prépériode et la période de la partie 
    décimale de p/q en base d >= 2, p et q entiers naturels, q non nul.
    """
    r = p//q # calcule la partie entière de p/q
    p -= r*q # désormais, 0 <= p/q < 1
    L = [] # L rassemble les decimales
    K = [p] # K est la suite des numérateurs des iterees de la fonction T
    controle = True
    while controle:
        chiffre = eps(p, q, d)
        L.append(chiffre)
        p = d * p - q * chiffre # calcule le numérateur de T(p/q) (sans simplifier la fraction)
        indice = recherche(K, p)
        if isinstance(indice, int): # si on a déjà vu ce numérateur, on sort du while
            controle = False
        else:
            K.append(p)  
    return(r, L[: indice], L[indice:])