from string import translate, maketrans
flip = maketrans('aA','Aa')
class fraction:
def __init__(self, num, den):
self.num, self.den = num, den
def numerator(self):
return self.num
def denominator(self):
return self.den
def __eq__(self, other):
return ( self.numerator() == other.numerator() and
self.denominator() == other.denominator() )
def __repr__(self):
return '%d/%d'%(self.num, self.den)
oo = fraction(1,0)
_oo = fraction(-1,0)
_0 = fraction(0,-1)
def E(farey):
"""
Given a Farey fraction p/q (including oo=1/0), return a primitive
element of the rank 2 free group in the conjugacy class determined
by the fraction, expressed either as a palindrome (if pq is even
for p/q reduced) or as a product of two palindromes. The
primitive elements are only defined up to taking inverses so, by
convention, the result is either a word in the letters a and B, or
A and B.
Usage example:
sage: %attach palindromes.py
sage: E(0)
'a'
sage: E(oo)
'B'
sage: E(1)
'aB'
sage: E(-1)
'B.A'
sage: E(2/3)
'aBaBa'
sage: E(4/6)
'aBaBa'
sage: E(3/5)
'aBa.aBaBa'
sage: E(19/11)
'BaBBaBaBBaBBaBaBBaB.BaBBaBaBBaB'
sage: E(-19/11)
'BABBABABBAB.BABBABABBABBABABBAB'
sage: E(24/7)
'BBaBBBaBBBBaBBBaBBBaBBBBaBBBaBB
"""
if oo == farey:
return 'B'
elif _oo == farey:
return 'B'
elif _0 == farey:
return 'A'
elif 0 == farey:
return 'a'
p, q = farey.numerator(), farey.denominator()
x = p/q
p, q = x.numerator(), x.denominator()
if q == 1:
if p > 0:
smaller, larger = (p-1)/1, oo
else:
smaller, larger = _oo, (p+1)/1
else:
cf_list = list(continued_fraction(x))
front = continued_fraction(cf_list[:-1])
cf_list[-1] -= 1
back = continued_fraction(cf_list)
neighbors = [front.value(), back.value()]
neighbors.sort()
smaller, larger = neighbors
if larger.numerator() == 0:
larger = _0
if p*q % 2 == 0:
return E(larger).replace('.','') + '*'+ E(smaller).replace('.','')
else:
return E(smaller).replace('.','') + '*'+E(larger).replace('.','')