ratio_to_recurring.py

from sympy.ntheory import factorint, multiplicity
import operator as op, functools, itertools, fractions


factorlist = lambda n: sum(([p] * k for p, k in factorint(n).items()), [])
totient_factors = lambda n: sum((factorlist(p-1) + [p]*(k-1)
    for p, k in factorint(n).items()), [])
divisors = lambda fs: [functools.reduce(op.mul, c, 1)
    for l in range(len(fs) + 1) for c in itertools.combinations(fs, l)]
leadzero = lambda n, l: str(n).zfill(l) if l else ""

def recurring(a, b):
    if b == 0: raise ZeroDivisionError("recurring({}, 0)".format(a))
    neg = a*b < 0; a, b = abs(a), abs(b)
    g = fractions.gcd(a, b); a //= g; b //= g
    int_part = a // b; a %= b
    if a == 0: return neg*"-" + str(int_part)
    p2 = multiplicity(2, b); p5 = multiplicity(5, b)
    bno25 = b // 2**p2 // 5**p5
    F = max(p2, p5); f = a * 10**F // b
    if bno25 == 1: return neg*"-" + str(int_part) + "." + leadzero(f, F)
    R = next(k for k in divisors(totient_factors(bno25)) if pow(10, k, bno25) == 1)
    r = ((10**R-1)*(10**F*a - b*f))//b
    return neg*"-" + str(int_part) + "." + leadzero(f, F) + "(" + leadzero(r, R) + ")"


# f = finite part (as an integer, e.g. 5243)
# r = recurring part (as an integer)
# F = finite part length (in # digits behind decimal point)
# R = recurring part length (in # digits)
# a/b - f/10^F = r/10^(F+R) + r/10^(F+R+R) + ...
# 10^R*(a/b - f/10^F) = 10^R*(r/10^(F+R) + r/10^(F+R+R) + ...)                    (multiply both sides by 10^R)
# 10^R*(a/b - f/10^F) = r/10^(F+R-R) + r/10^(F+R+R-R) + ...                       (distribute over infinite series)
# 10^R*(a/b - f/10^F) = r/10^F + r/10^(F+R) + r/10^(F+R+R) + ...                  (cancel R and extract 1 term from infinite series)
# 10^R*(a/b - f/10^F) = r/10^F                                                    (substitute equation 1)
# (10^R-1)*(a/b - f/10^F) = r/10^F                                                (subtract a/b - f/10^F)
# (10^R-1)*(10^Fa/b - f) = r                                                      (multiply 10^F)
# (10^R-1)*(10^Fa - b*f)/b = r                                                    (delay division by b)