<s> """<STR_LIT>""" <EOL> from __future__ import print_function , division <EOL> from sympy . core . add import Add <EOL> from sympy . core . compatibility import iterable , is_sequence , SYMPY_INTS , range <EOL> from sympy . core . mul import Mul , _keep_coeff <EOL> from sympy . core . power import Pow <EOL> from sympy . core . basic import Basic , preorder_traversal <EOL> from sympy . core . expr import Expr <EOL> from sympy . core . sympify import sympify <EOL> from sympy . core . numbers import Rational , Integer , Number , I <EOL> from sympy . core . singleton import S <EOL> from sympy . core . symbol import Dummy <EOL> from sympy . core . coreerrors import NonCommutativeExpression <EOL> from sympy . core . containers import Tuple , Dict <EOL> from sympy . utilities import default_sort_key <EOL> from sympy . utilities . iterables import ( common_prefix , common_suffix , <EOL> variations , ordered ) <EOL> from collections import defaultdict <EOL> _eps = Dummy ( positive = True ) <EOL> def _isnumber ( i ) : <EOL> return isinstance ( i , ( SYMPY_INTS , float ) ) or i . is_Number <EOL> def _monotonic_sign ( self ) : <EOL> """<STR_LIT>""" <EOL> if not self . is_real : <EOL> return <EOL> if ( - self ) . is_Symbol : <EOL> rv = _monotonic_sign ( - self ) <EOL> return rv if rv is None else - rv <EOL> if not self . is_Add and self . as_numer_denom ( ) [ <NUM_LIT:1> ] . is_number : <EOL> s = self <EOL> if s . is_prime : <EOL> if s . is_odd : <EOL> return S ( <NUM_LIT:3> ) <EOL> else : <EOL> return S ( <NUM_LIT:2> ) <EOL> elif s . is_positive : <EOL> if s . is_even : <EOL> return S ( <NUM_LIT:2> ) <EOL> elif s . is_integer : <EOL> return S . One <EOL> else : <EOL> return _eps <EOL> elif s . is_negative : <EOL> if s . is_even : <EOL> return S ( - <NUM_LIT:2> ) <EOL> elif s . is_integer : <EOL> return S . NegativeOne <EOL> else : <EOL> return - _eps <EOL> if s . is_zero or s . is_nonpositive or s . is_nonnegative : <EOL> return S . Zero <EOL> return None <EOL> free = self . free_symbols <EOL> if len ( free ) == <NUM_LIT:1> : <EOL> if self . is_polynomial ( ) : <EOL> from sympy . polys . polytools import real_roots <EOL> from sympy . polys . polyroots import roots <EOL> from sympy . polys . polyerrors import PolynomialError <EOL> x = free . pop ( ) <EOL> x0 = _monotonic_sign ( x ) <EOL> if x0 == _eps or x0 == - _eps : <EOL> x0 = S . Zero <EOL> if x0 is not None : <EOL> d = self . diff ( x ) <EOL> if d . is_number : <EOL> roots = [ ] <EOL> else : <EOL> try : <EOL> roots = real_roots ( d ) <EOL> except ( PolynomialError , NotImplementedError ) : <EOL> roots = [ r for r in roots ( d , x ) if r . is_real ] <EOL> y = self . subs ( x , x0 ) <EOL> if x . is_nonnegative and all ( r <= x0 for r in roots ) : <EOL> if y . is_nonnegative and d . is_positive : <EOL> if y : <EOL> return y if y . is_positive else Dummy ( '<STR_LIT>' , positive = True ) <EOL> else : <EOL> return Dummy ( '<STR_LIT>' , nonnegative = True ) <EOL> if y . is_nonpositive and d . is_negative : <EOL> if y : <EOL> return y if y . is_negative else Dummy ( '<STR_LIT>' , negative = True ) <EOL> else : <EOL> return Dummy ( '<STR_LIT>' , nonpositive = True ) <EOL> elif x . is_nonpositive and all ( r >= x0 for r in roots ) : <EOL> if y . is_nonnegative and d . is_negative : <EOL> if y : <EOL> return Dummy ( '<STR_LIT>' , positive = True ) <EOL> else : <EOL> return Dummy ( '<STR_LIT>' , nonnegative = True ) <EOL> if y . is_nonpositive and d . is_positive : <EOL> if y : <EOL> return Dummy ( '<STR_LIT>' , negative = True ) <EOL> else : <EOL> return Dummy ( '<STR_LIT>' , nonpositive = True ) <EOL> else : <EOL> n , d = self . as_numer_denom ( ) <EOL> den = None <EOL> if n . is_number : <EOL> den = _monotonic_sign ( d ) <EOL> elif not d . is_number : <EOL> if _monotonic_sign ( n ) is not None : <EOL> den = _monotonic_sign ( d ) <EOL> if den is not None and ( den . is_positive or den . is_negative ) : <EOL> v = n * den <EOL> if v . is_positive : <EOL> return Dummy ( '<STR_LIT>' , positive = True ) <EOL> elif v . is_nonnegative : <EOL> return Dummy ( '<STR_LIT>' , nonnegative = True ) <EOL> elif v . is_negative : <EOL> return Dummy ( '<STR_LIT>' , negative = True ) <EOL> elif v . is_nonpositive : <EOL> return Dummy ( '<STR_LIT>' , nonpositive = True ) <EOL> return None <EOL> c , a = self . as_coeff_Add ( ) <EOL> v = None <EOL> if not a . is_polynomial ( ) : <EOL> n , d = a . as_numer_denom ( ) <EOL> if not ( n . is_number or d . is_number ) : <EOL> return <EOL> if ( <EOL> a . is_Mul or a . is_Pow ) and a . is_rational and all ( p . exp . is_Integer for p in a . atoms ( Pow ) if p . is_Pow ) and ( a . is_positive or a . is_negative ) : <EOL> v = S ( <NUM_LIT:1> ) <EOL> for ai in Mul . make_args ( a ) : <EOL> if ai . is_number : <EOL> v *= ai <EOL> continue <EOL> reps = { } <EOL> for x in ai . free_symbols : <EOL> reps [ x ] = _monotonic_sign ( x ) <EOL> if reps [ x ] is None : <EOL> return <EOL> v *= ai . subs ( reps ) <EOL> elif c : <EOL> if not any ( p for p in a . atoms ( Pow ) if not p . is_number ) and ( a . is_nonpositive or a . is_nonnegative ) : <EOL> free = list ( a . free_symbols ) <EOL> p = { } <EOL> for i in free : <EOL> v = _monotonic_sign ( i ) <EOL> if v is None : <EOL> return <EOL> p [ i ] = v or ( _eps if i . is_nonnegative else - _eps ) <EOL> v = a . xreplace ( p ) <EOL> if v is not None : <EOL> rv = v + c <EOL> if v . is_nonnegative and rv . is_positive : <EOL> return rv . subs ( _eps , <NUM_LIT:0> ) <EOL> if v . is_nonpositive and rv . is_negative : <EOL> return rv . subs ( _eps , <NUM_LIT:0> ) <EOL> def decompose_power ( expr ) : <EOL> """<STR_LIT>""" <EOL> base , exp = expr . as_base_exp ( ) <EOL> if exp . is_Number : <EOL> if exp . is_Rational : <EOL> if not exp . is_Integer : <EOL> base = Pow ( base , Rational ( <NUM_LIT:1> , exp . q ) ) <EOL> exp = exp . p <EOL> else : <EOL> base , exp = expr , <NUM_LIT:1> <EOL> else : <EOL> exp , tail = exp . as_coeff_Mul ( rational = True ) <EOL> if exp is S . NegativeOne : <EOL> base , exp = Pow ( base , tail ) , - <NUM_LIT:1> <EOL> elif exp is not S . One : <EOL> tail = _keep_coeff ( Rational ( <NUM_LIT:1> , exp . q ) , tail ) <EOL> base , exp = Pow ( base , tail ) , exp . p <EOL> else : <EOL> base , exp = expr , <NUM_LIT:1> <EOL> return base , exp <EOL> def decompose_power_rat ( expr ) : <EOL> """<STR_LIT>""" <EOL> base , exp = expr . as_base_exp ( ) <EOL> if exp . is_Number : <EOL> if not exp . is_Rational : <EOL> base , exp = expr , <NUM_LIT:1> <EOL> else : <EOL> exp , tail = exp . as_coeff_Mul ( rational = True ) <EOL> if exp is S . NegativeOne : <EOL> base , exp = Pow ( base , tail ) , - <NUM_LIT:1> <EOL> elif exp is not S . One : <EOL> tail = _keep_coeff ( Rational ( <NUM_LIT:1> , exp . q ) , tail ) <EOL> base , exp = Pow ( base , tail ) , exp . p <EOL> else : <EOL> base , exp = expr , <NUM_LIT:1> <EOL> return base , exp <EOL> class Factors ( object ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = [ '<STR_LIT>' , '<STR_LIT>' ] <EOL> def __init__ ( self , factors = None ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( factors , ( SYMPY_INTS , float ) ) : <EOL> factors = S ( factors ) <EOL> if isinstance ( factors , Factors ) : <EOL> factors = factors . factors . copy ( ) <EOL> elif factors is None or factors is S . One : <EOL> factors = { } <EOL> elif factors is S . Zero or factors == <NUM_LIT:0> : <EOL> factors = { S . Zero : S . One } <EOL> elif isinstance ( factors , Number ) : <EOL> n = factors <EOL> factors = { } <EOL> if n < <NUM_LIT:0> : <EOL> factors [ S . NegativeOne ] = S . One <EOL> n = - n <EOL> if n is not S . One : <EOL> if n . is_Float or n . is_Integer or n is S . Infinity : <EOL> factors [ n ] = S . One <EOL> elif n . is_Rational : <EOL> if n . p != <NUM_LIT:1> : <EOL> factors [ Integer ( n . p ) ] = S . One <EOL> factors [ Integer ( n . q ) ] = S . NegativeOne <EOL> else : <EOL> raise ValueError ( '<STR_LIT>' % n ) <EOL> elif isinstance ( factors , Basic ) and not factors . args : <EOL> factors = { factors : S . One } <EOL> elif isinstance ( factors , Expr ) : <EOL> c , nc = factors . args_cnc ( ) <EOL> i = c . count ( I ) <EOL> for _ in range ( i ) : <EOL> c . remove ( I ) <EOL> factors = dict ( Mul . _from_args ( c ) . as_powers_dict ( ) ) <EOL> if i : <EOL> factors [ I ] = S . One * i <EOL> if nc : <EOL> factors [ Mul ( * nc , evaluate = False ) ] = S . One <EOL> else : <EOL> factors = factors . copy ( ) <EOL> handle = [ ] <EOL> for k in factors : <EOL> if k is I or k in ( - <NUM_LIT:1> , <NUM_LIT:1> ) : <EOL> handle . append ( k ) <EOL> if handle : <EOL> i1 = S . One <EOL> for k in handle : <EOL> if not _isnumber ( factors [ k ] ) : <EOL> continue <EOL> i1 *= k ** factors . pop ( k ) <EOL> if i1 is not S . One : <EOL> for a in i1 . args if i1 . is_Mul else [ i1 ] : <EOL> if a is S . NegativeOne : <EOL> factors [ a ] = S . One <EOL> elif a is I : <EOL> factors [ I ] = S . One <EOL> elif a . is_Pow : <EOL> if S . NegativeOne not in factors : <EOL> factors [ S . NegativeOne ] = S . Zero <EOL> factors [ S . NegativeOne ] += a . exp <EOL> elif a == <NUM_LIT:1> : <EOL> factors [ a ] = S . One <EOL> elif a == - <NUM_LIT:1> : <EOL> factors [ - a ] = S . One <EOL> factors [ S . NegativeOne ] = S . One <EOL> else : <EOL> raise ValueError ( '<STR_LIT>' % a ) <EOL> self . factors = factors <EOL> try : <EOL> self . gens = frozenset ( factors . keys ( ) ) <EOL> except AttributeError : <EOL> raise TypeError ( '<STR_LIT>' ) <EOL> def __hash__ ( self ) : <EOL> keys = tuple ( ordered ( self . factors . keys ( ) ) ) <EOL> values = [ self . factors [ k ] for k in keys ] <EOL> return hash ( ( keys , values ) ) <EOL> def __repr__ ( self ) : <EOL> return "<STR_LIT>" % '<STR_LIT:U+002CU+0020>' . join ( <EOL> [ '<STR_LIT>' % ( k , v ) for k , v in ordered ( self . factors . items ( ) ) ] ) <EOL> @ property <EOL> def is_zero ( self ) : <EOL> """<STR_LIT>""" <EOL> f = self . factors <EOL> return len ( f ) == <NUM_LIT:1> and S . Zero in f <EOL> @ property <EOL> def is_one ( self ) : <EOL> """<STR_LIT>""" <EOL> return not self . factors <EOL> def as_expr ( self ) : <EOL> """<STR_LIT>""" <EOL> args = [ ] <EOL> for factor , exp in self . factors . items ( ) : <EOL> if exp != <NUM_LIT:1> : <EOL> b , e = factor . as_base_exp ( ) <EOL> if isinstance ( exp , int ) : <EOL> e = _keep_coeff ( Integer ( exp ) , e ) <EOL> elif isinstance ( exp , Rational ) : <EOL> e = _keep_coeff ( exp , e ) <EOL> else : <EOL> e *= exp <EOL> args . append ( b ** e ) <EOL> else : <EOL> args . append ( factor ) <EOL> return Mul ( * args ) <EOL> def mul ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , Factors ) : <EOL> other = Factors ( other ) <EOL> if any ( f . is_zero for f in ( self , other ) ) : <EOL> return Factors ( S . Zero ) <EOL> factors = dict ( self . factors ) <EOL> for factor , exp in other . factors . items ( ) : <EOL> if factor in factors : <EOL> exp = factors [ factor ] + exp <EOL> if not exp : <EOL> del factors [ factor ] <EOL> continue <EOL> factors [ factor ] = exp <EOL> return Factors ( factors ) <EOL> def normal ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , Factors ) : <EOL> other = Factors ( other ) <EOL> if other . is_zero : <EOL> return ( Factors ( ) , Factors ( S . Zero ) ) <EOL> if self . is_zero : <EOL> return ( Factors ( S . Zero ) , Factors ( ) ) <EOL> self_factors = dict ( self . factors ) <EOL> other_factors = dict ( other . factors ) <EOL> for factor , self_exp in self . factors . items ( ) : <EOL> try : <EOL> other_exp = other . factors [ factor ] <EOL> except KeyError : <EOL> continue <EOL> exp = self_exp - other_exp <EOL> if not exp : <EOL> del self_factors [ factor ] <EOL> del other_factors [ factor ] <EOL> elif _isnumber ( exp ) : <EOL> if exp > <NUM_LIT:0> : <EOL> self_factors [ factor ] = exp <EOL> del other_factors [ factor ] <EOL> else : <EOL> del self_factors [ factor ] <EOL> other_factors [ factor ] = - exp <EOL> else : <EOL> r = self_exp . extract_additively ( other_exp ) <EOL> if r is not None : <EOL> if r : <EOL> self_factors [ factor ] = r <EOL> del other_factors [ factor ] <EOL> else : <EOL> del self_factors [ factor ] <EOL> del other_factors [ factor ] <EOL> else : <EOL> sc , sa = self_exp . as_coeff_Add ( ) <EOL> if sc : <EOL> oc , oa = other_exp . as_coeff_Add ( ) <EOL> diff = sc - oc <EOL> if diff > <NUM_LIT:0> : <EOL> self_factors [ factor ] -= oc <EOL> other_exp = oa <EOL> elif diff < <NUM_LIT:0> : <EOL> self_factors [ factor ] -= sc <EOL> other_factors [ factor ] -= sc <EOL> other_exp = oa - diff <EOL> else : <EOL> self_factors [ factor ] = sa <EOL> other_exp = oa <EOL> if other_exp : <EOL> other_factors [ factor ] = other_exp <EOL> else : <EOL> del other_factors [ factor ] <EOL> return Factors ( self_factors ) , Factors ( other_factors ) <EOL> def div ( self , other ) : <EOL> """<STR_LIT>""" <EOL> quo , rem = dict ( self . factors ) , { } <EOL> if not isinstance ( other , Factors ) : <EOL> other = Factors ( other ) <EOL> if other . is_zero : <EOL> raise ZeroDivisionError <EOL> if self . is_zero : <EOL> return ( Factors ( S . Zero ) , Factors ( ) ) <EOL> for factor , exp in other . factors . items ( ) : <EOL> if factor in quo : <EOL> d = quo [ factor ] - exp <EOL> if _isnumber ( d ) : <EOL> if d <= <NUM_LIT:0> : <EOL> del quo [ factor ] <EOL> if d >= <NUM_LIT:0> : <EOL> if d : <EOL> quo [ factor ] = d <EOL> continue <EOL> exp = - d <EOL> else : <EOL> r = quo [ factor ] . extract_additively ( exp ) <EOL> if r is not None : <EOL> if r : <EOL> quo [ factor ] = r <EOL> else : <EOL> del quo [ factor ] <EOL> else : <EOL> other_exp = exp <EOL> sc , sa = quo [ factor ] . as_coeff_Add ( ) <EOL> if sc : <EOL> oc , oa = other_exp . as_coeff_Add ( ) <EOL> diff = sc - oc <EOL> if diff > <NUM_LIT:0> : <EOL> quo [ factor ] -= oc <EOL> other_exp = oa <EOL> elif diff < <NUM_LIT:0> : <EOL> quo [ factor ] -= sc <EOL> other_exp = oa - diff <EOL> else : <EOL> quo [ factor ] = sa <EOL> other_exp = oa <EOL> if other_exp : <EOL> rem [ factor ] = other_exp <EOL> else : <EOL> assert factor not in rem <EOL> continue <EOL> rem [ factor ] = exp <EOL> return Factors ( quo ) , Factors ( rem ) <EOL> def quo ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self . div ( other ) [ <NUM_LIT:0> ] <EOL> def rem ( self , other ) : <EOL> """<STR_LIT>""" <EOL> return self . div ( other ) [ <NUM_LIT:1> ] <EOL> def pow ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( other , Factors ) : <EOL> other = other . as_expr ( ) <EOL> if other . is_Integer : <EOL> other = int ( other ) <EOL> if isinstance ( other , SYMPY_INTS ) and other >= <NUM_LIT:0> : <EOL> factors = { } <EOL> if other : <EOL> for factor , exp in self . factors . items ( ) : <EOL> factors [ factor ] = exp * other <EOL> return Factors ( factors ) <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" % other ) <EOL> def gcd ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , Factors ) : <EOL> other = Factors ( other ) <EOL> if other . is_zero : <EOL> return Factors ( self . factors ) <EOL> factors = { } <EOL> for factor , exp in self . factors . items ( ) : <EOL> factor , exp = sympify ( factor ) , sympify ( exp ) <EOL> if factor in other . factors : <EOL> lt = ( exp - other . factors [ factor ] ) . is_negative <EOL> if lt == True : <EOL> factors [ factor ] = exp <EOL> elif lt == False : <EOL> factors [ factor ] = other . factors [ factor ] <EOL> return Factors ( factors ) <EOL> def lcm ( self , other ) : <EOL> """<STR_LIT>""" <EOL> if not isinstance ( other , Factors ) : <EOL> other = Factors ( other ) <EOL> if any ( f . is_zero for f in ( self , other ) ) : <EOL> return Factors ( S . Zero ) <EOL> factors = dict ( self . factors ) <EOL> for factor , exp in other . factors . items ( ) : <EOL> if factor in factors : <EOL> exp = max ( exp , factors [ factor ] ) <EOL> factors [ factor ] = exp <EOL> return Factors ( factors ) <EOL> def __mul__ ( self , other ) : <EOL> return self . mul ( other ) <EOL> def __divmod__ ( self , other ) : <EOL> return self . div ( other ) <EOL> def __div__ ( self , other ) : <EOL> return self . quo ( other ) <EOL> __truediv__ = __div__ <EOL> def __mod__ ( self , other ) : <EOL> return self . rem ( other ) <EOL> def __pow__ ( self , other ) : <EOL> return self . pow ( other ) <EOL> def __eq__ ( self , other ) : <EOL> if not isinstance ( other , Factors ) : <EOL> other = Factors ( other ) <EOL> return self . factors == other . factors <EOL> def __ne__ ( self , other ) : <EOL> return not self . __eq__ ( other ) <EOL> class Term ( object ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> def __init__ ( self , term , numer = None , denom = None ) : <EOL> if numer is None and denom is None : <EOL> if not term . is_commutative : <EOL> raise NonCommutativeExpression ( <EOL> '<STR_LIT>' ) <EOL> coeff , factors = term . as_coeff_mul ( ) <EOL> numer , denom = defaultdict ( int ) , defaultdict ( int ) <EOL> for factor in factors : <EOL> base , exp = decompose_power ( factor ) <EOL> if base . is_Add : <EOL> cont , base = base . primitive ( ) <EOL> coeff *= cont ** exp <EOL> if exp > <NUM_LIT:0> : <EOL> numer [ base ] += exp <EOL> else : <EOL> denom [ base ] += - exp <EOL> numer = Factors ( numer ) <EOL> denom = Factors ( denom ) <EOL> else : <EOL> coeff = term <EOL> if numer is None : <EOL> numer = Factors ( ) <EOL> if denom is None : <EOL> denom = Factors ( ) <EOL> self . coeff = coeff <EOL> self . numer = numer <EOL> self . denom = denom <EOL> def __hash__ ( self ) : <EOL> return hash ( ( self . coeff , self . numer , self . denom ) ) <EOL> def __repr__ ( self ) : <EOL> return "<STR_LIT>" % ( self . coeff , self . numer , self . denom ) <EOL> def as_expr ( self ) : <EOL> return self . coeff * ( self . numer . as_expr ( ) / self . denom . as_expr ( ) ) <EOL> def mul ( self , other ) : <EOL> coeff = self . coeff * other . coeff <EOL> numer = self . numer . mul ( other . numer ) <EOL> denom = self . denom . mul ( other . denom ) <EOL> numer , denom = numer . normal ( denom ) <EOL> return Term ( coeff , numer , denom ) <EOL> def inv ( self ) : <EOL> return Term ( <NUM_LIT:1> / self . coeff , self . denom , self . numer ) <EOL> def quo ( self , other ) : <EOL> return self . mul ( other . inv ( ) ) <EOL> def pow ( self , other ) : <EOL> if other < <NUM_LIT:0> : <EOL> return self . inv ( ) . pow ( - other ) <EOL> else : <EOL> return Term ( self . coeff ** other , <EOL> self . numer . pow ( other ) , <EOL> self . denom . pow ( other ) ) <EOL> def gcd ( self , other ) : <EOL> return Term ( self . coeff . gcd ( other . coeff ) , <EOL> self . numer . gcd ( other . numer ) , <EOL> self . denom . gcd ( other . denom ) ) <EOL> def lcm ( self , other ) : <EOL> return Term ( self . coeff . lcm ( other . coeff ) , <EOL> self . numer . lcm ( other . numer ) , <EOL> self . denom . lcm ( other . denom ) ) <EOL> def __mul__ ( self , other ) : <EOL> if isinstance ( other , Term ) : <EOL> return self . mul ( other ) <EOL> else : <EOL> return NotImplemented <EOL> def __div__ ( self , other ) : <EOL> if isinstance ( other , Term ) : <EOL> return self . quo ( other ) <EOL> else : <EOL> return NotImplemented <EOL> __truediv__ = __div__ <EOL> def __pow__ ( self , other ) : <EOL> if isinstance ( other , SYMPY_INTS ) : <EOL> return self . pow ( other ) <EOL> else : <EOL> return NotImplemented <EOL> def __eq__ ( self , other ) : <EOL> return ( self . coeff == other . coeff and <EOL> self . numer == other . numer and <EOL> self . denom == other . denom ) <EOL> def __ne__ ( self , other ) : <EOL> return not self . __eq__ ( other ) <EOL> def _gcd_terms ( terms , isprimitive = False , fraction = True ) : <EOL> """<STR_LIT>""" <EOL> if isinstance ( terms , Basic ) and not isinstance ( terms , Tuple ) : <EOL> terms = Add . make_args ( terms ) <EOL> terms = list ( map ( Term , [ t for t in terms if t ] ) ) <EOL> if len ( terms ) == <NUM_LIT:0> : <EOL> return S . Zero , S . Zero , S . One <EOL> if len ( terms ) == <NUM_LIT:1> : <EOL> cont = terms [ <NUM_LIT:0> ] . coeff <EOL> numer = terms [ <NUM_LIT:0> ] . numer . as_expr ( ) <EOL> denom = terms [ <NUM_LIT:0> ] . denom . as_expr ( ) <EOL> else : <EOL> cont = terms [ <NUM_LIT:0> ] <EOL> for term in terms [ <NUM_LIT:1> : ] : <EOL> cont = cont . gcd ( term ) <EOL> for i , term in enumerate ( terms ) : <EOL> terms [ i ] = term . quo ( cont ) <EOL> if fraction : <EOL> denom = terms [ <NUM_LIT:0> ] . denom <EOL> for term in terms [ <NUM_LIT:1> : ] : <EOL> denom = denom . lcm ( term . denom ) <EOL> numers = [ ] <EOL> for term in terms : <EOL> numer = term . numer . mul ( denom . quo ( term . denom ) ) <EOL> numers . append ( term . coeff * numer . as_expr ( ) ) <EOL> else : <EOL> numers = [ t . as_expr ( ) for t in terms ] <EOL> denom = Term ( S ( <NUM_LIT:1> ) ) . numer <EOL> cont = cont . as_expr ( ) <EOL> numer = Add ( * numers ) <EOL> denom = denom . as_expr ( ) <EOL> if not isprimitive and numer . is_Add : <EOL> _cont , numer = numer . primitive ( ) <EOL> cont *= _cont <EOL> return cont , numer , denom <EOL> def gcd_terms ( terms , isprimitive = False , clear = True , fraction = True ) : <EOL> """<STR_LIT>""" <EOL> def mask ( terms ) : <EOL> """<STR_LIT>""" <EOL> args = [ ( a , [ ] ) if a . is_commutative else a . args_cnc ( ) for a in terms ] <EOL> reps = [ ] <EOL> for i , ( c , nc ) in enumerate ( args ) : <EOL> if nc : <EOL> nc = Mul . _from_args ( nc ) <EOL> d = Dummy ( ) <EOL> reps . append ( ( d , nc ) ) <EOL> c . append ( d ) <EOL> args [ i ] = Mul . _from_args ( c ) <EOL> else : <EOL> args [ i ] = c <EOL> return args , dict ( reps ) <EOL> isadd = isinstance ( terms , Add ) <EOL> addlike = isadd or not isinstance ( terms , Basic ) and is_sequence ( terms , include = set ) and not isinstance ( terms , Dict ) <EOL> if addlike : <EOL> if isadd : <EOL> terms = list ( terms . args ) <EOL> else : <EOL> terms = sympify ( terms ) <EOL> terms , reps = mask ( terms ) <EOL> cont , numer , denom = _gcd_terms ( terms , isprimitive , fraction ) <EOL> numer = numer . xreplace ( reps ) <EOL> coeff , factors = cont . as_coeff_Mul ( ) <EOL> if not clear : <EOL> c , _coeff = coeff . as_coeff_Mul ( ) <EOL> if not c . is_Integer and not clear and numer . is_Add : <EOL> n , d = c . as_numer_denom ( ) <EOL> _numer = numer / d <EOL> if any ( a . as_coeff_Mul ( ) [ <NUM_LIT:0> ] . is_Integer <EOL> for a in _numer . args ) : <EOL> numer = _numer <EOL> coeff = n * _coeff <EOL> return _keep_coeff ( coeff , factors * numer / denom , clear = clear ) <EOL> if not isinstance ( terms , Basic ) : <EOL> return terms <EOL> if terms . is_Atom : <EOL> return terms <EOL> if terms . is_Mul : <EOL> c , args = terms . as_coeff_mul ( ) <EOL> return _keep_coeff ( c , Mul ( * [ gcd_terms ( i , isprimitive , clear , fraction ) <EOL> for i in args ] ) , clear = clear ) <EOL> def handle ( a ) : <EOL> if not isinstance ( a , Expr ) : <EOL> if isinstance ( a , Basic ) : <EOL> return a . func ( * [ handle ( i ) for i in a . args ] ) <EOL> return type ( a ) ( [ handle ( i ) for i in a ] ) <EOL> return gcd_terms ( a , isprimitive , clear , fraction ) <EOL> if isinstance ( terms , Dict ) : <EOL> return Dict ( * [ ( k , handle ( v ) ) for k , v in terms . args ] ) <EOL> return terms . func ( * [ handle ( i ) for i in terms . args ] ) <EOL> def factor_terms ( expr , radical = False , clear = False , fraction = False , sign = True ) : <EOL> """<STR_LIT>""" <EOL> def do ( expr ) : <EOL> is_iterable = iterable ( expr ) <EOL> if not isinstance ( expr , Basic ) or expr . is_Atom : <EOL> if is_iterable : <EOL> return type ( expr ) ( [ do ( i ) for i in expr ] ) <EOL> return expr <EOL> if expr . is_Pow or expr . is_Function or is_iterable or not hasattr ( expr , '<STR_LIT>' ) : <EOL> args = expr . args <EOL> newargs = tuple ( [ do ( i ) for i in args ] ) <EOL> if newargs == args : <EOL> return expr <EOL> return expr . func ( * newargs ) <EOL> cont , p = expr . as_content_primitive ( radical = radical , clear = clear ) <EOL> if p . is_Add : <EOL> list_args = [ do ( a ) for a in Add . make_args ( p ) ] <EOL> if all ( a . as_coeff_Mul ( ) [ <NUM_LIT:0> ] < <NUM_LIT:0> for a in list_args ) : <EOL> cont = - cont <EOL> list_args = [ - a for a in list_args ] <EOL> special = { } <EOL> for i , a in enumerate ( list_args ) : <EOL> b , e = a . as_base_exp ( ) <EOL> if e . is_Mul and e != Mul ( * e . args ) : <EOL> list_args [ i ] = Dummy ( ) <EOL> special [ list_args [ i ] ] = a <EOL> p = Add . _from_args ( list_args ) <EOL> p = gcd_terms ( p , <EOL> isprimitive = True , <EOL> clear = clear , <EOL> fraction = fraction ) . xreplace ( special ) <EOL> elif p . args : <EOL> p = p . func ( <EOL> * [ do ( a ) for a in p . args ] ) <EOL> rv = _keep_coeff ( cont , p , clear = clear , sign = sign ) <EOL> return rv <EOL> expr = sympify ( expr ) <EOL> return do ( expr ) <EOL> def _mask_nc ( eq , name = None ) : <EOL> """<STR_LIT>""" <EOL> name = name or '<STR_LIT>' <EOL> def numbered_names ( ) : <EOL> i = <NUM_LIT:0> <EOL> while True : <EOL> yield name + str ( i ) <EOL> i += <NUM_LIT:1> <EOL> names = numbered_names ( ) <EOL> def Dummy ( * args , ** kwargs ) : <EOL> from sympy import Dummy <EOL> return Dummy ( next ( names ) , * args , ** kwargs ) <EOL> expr = eq <EOL> if expr . is_commutative : <EOL> return eq , { } , [ ] <EOL> rep = [ ] <EOL> nc_obj = set ( ) <EOL> nc_syms = set ( ) <EOL> pot = preorder_traversal ( expr , keys = default_sort_key ) <EOL> for i , a in enumerate ( pot ) : <EOL> if any ( a == r [ <NUM_LIT:0> ] for r in rep ) : <EOL> pot . skip ( ) <EOL> elif not a . is_commutative : <EOL> if a . is_Symbol : <EOL> nc_syms . add ( a ) <EOL> elif not ( a . is_Add or a . is_Mul or a . is_Pow ) : <EOL> if all ( s . is_commutative for s in a . free_symbols ) : <EOL> rep . append ( ( a , Dummy ( ) ) ) <EOL> else : <EOL> nc_obj . add ( a ) <EOL> pot . skip ( ) <EOL> if len ( nc_obj ) == <NUM_LIT:1> and not nc_syms : <EOL> rep . append ( ( nc_obj . pop ( ) , Dummy ( ) ) ) <EOL> elif len ( nc_syms ) == <NUM_LIT:1> and not nc_obj : <EOL> rep . append ( ( nc_syms . pop ( ) , Dummy ( ) ) ) <EOL> nc_obj = sorted ( nc_obj , key = default_sort_key ) <EOL> for n in nc_obj : <EOL> nc = Dummy ( commutative = False ) <EOL> rep . append ( ( n , nc ) ) <EOL> nc_syms . add ( nc ) <EOL> expr = expr . subs ( rep ) <EOL> nc_syms = list ( nc_syms ) <EOL> nc_syms . sort ( key = default_sort_key ) <EOL> return expr , { v : k for k , v in rep } or None , nc_syms <EOL> def factor_nc ( expr ) : <EOL> """<STR_LIT>""" <EOL> from sympy . simplify . simplify import powsimp <EOL> from sympy . polys import gcd , factor <EOL> def _pemexpand ( expr ) : <EOL> "<STR_LIT>" <EOL> return expr . expand ( deep = True , mul = True , power_exp = True , <EOL> power_base = False , basic = False , multinomial = True , log = False ) <EOL> expr = sympify ( expr ) <EOL> if not isinstance ( expr , Expr ) or not expr . args : <EOL> return expr <EOL> if not expr . is_Add : <EOL> return expr . func ( * [ factor_nc ( a ) for a in expr . args ] ) <EOL> expr , rep , nc_symbols = _mask_nc ( expr ) <EOL> if rep : <EOL> return factor ( expr ) . subs ( rep ) <EOL> else : <EOL> args = [ a . args_cnc ( ) for a in Add . make_args ( expr ) ] <EOL> c = g = l = r = S . One <EOL> hit = False <EOL> for i , a in enumerate ( args ) : <EOL> if i == <NUM_LIT:0> : <EOL> c = Mul . _from_args ( a [ <NUM_LIT:0> ] ) <EOL> elif a [ <NUM_LIT:0> ] : <EOL> c = gcd ( c , Mul . _from_args ( a [ <NUM_LIT:0> ] ) ) <EOL> else : <EOL> c = S . One <EOL> if c is not S . One : <EOL> hit = True <EOL> c , g = c . as_coeff_Mul ( ) <EOL> if g is not S . One : <EOL> for i , ( cc , _ ) in enumerate ( args ) : <EOL> cc = list ( Mul . make_args ( Mul . _from_args ( list ( cc ) ) / g ) ) <EOL> args [ i ] [ <NUM_LIT:0> ] = cc <EOL> for i , ( cc , _ ) in enumerate ( args ) : <EOL> cc [ <NUM_LIT:0> ] = cc [ <NUM_LIT:0> ] / c <EOL> args [ i ] [ <NUM_LIT:0> ] = cc <EOL> for i , a in enumerate ( args ) : <EOL> if i == <NUM_LIT:0> : <EOL> n = a [ <NUM_LIT:1> ] [ : ] <EOL> else : <EOL> n = common_prefix ( n , a [ <NUM_LIT:1> ] ) <EOL> if not n : <EOL> if not args [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] : <EOL> break <EOL> b , e = args [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] . as_base_exp ( ) <EOL> ok = False <EOL> if e . is_Integer : <EOL> for t in args : <EOL> if not t [ <NUM_LIT:1> ] : <EOL> break <EOL> bt , et = t [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] . as_base_exp ( ) <EOL> if et . is_Integer and bt == b : <EOL> e = min ( e , et ) <EOL> else : <EOL> break <EOL> else : <EOL> ok = hit = True <EOL> l = b ** e <EOL> il = b ** - e <EOL> for i , a in enumerate ( args ) : <EOL> args [ i ] [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] = il * args [ i ] [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] <EOL> break <EOL> if not ok : <EOL> break <EOL> else : <EOL> hit = True <EOL> lenn = len ( n ) <EOL> l = Mul ( * n ) <EOL> for i , a in enumerate ( args ) : <EOL> args [ i ] [ <NUM_LIT:1> ] = args [ i ] [ <NUM_LIT:1> ] [ lenn : ] <EOL> for i , a in enumerate ( args ) : <EOL> if i == <NUM_LIT:0> : <EOL> n = a [ <NUM_LIT:1> ] [ : ] <EOL> else : <EOL> n = common_suffix ( n , a [ <NUM_LIT:1> ] ) <EOL> if not n : <EOL> if not args [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] : <EOL> break <EOL> b , e = args [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ - <NUM_LIT:1> ] . as_base_exp ( ) <EOL> ok = False <EOL> if e . is_Integer : <EOL> for t in args : <EOL> if not t [ <NUM_LIT:1> ] : <EOL> break <EOL> bt , et = t [ <NUM_LIT:1> ] [ - <NUM_LIT:1> ] . as_base_exp ( ) <EOL> if et . is_Integer and bt == b : <EOL> e = min ( e , et ) <EOL> else : <EOL> break <EOL> else : <EOL> ok = hit = True <EOL> r = b ** e <EOL> il = b ** - e <EOL> for i , a in enumerate ( args ) : <EOL> args [ i ] [ <NUM_LIT:1> ] [ - <NUM_LIT:1> ] = args [ i ] [ <NUM_LIT:1> ] [ - <NUM_LIT:1> ] * il <EOL> break <EOL> if not ok : <EOL> break <EOL> else : <EOL> hit = True <EOL> lenn = len ( n ) <EOL> r = Mul ( * n ) <EOL> for i , a in enumerate ( args ) : <EOL> args [ i ] [ <NUM_LIT:1> ] = a [ <NUM_LIT:1> ] [ : len ( a [ <NUM_LIT:1> ] ) - lenn ] <EOL> if hit : <EOL> mid = Add ( * [ Mul ( * cc ) * Mul ( * nc ) for cc , nc in args ] ) <EOL> else : <EOL> mid = expr <EOL> rep1 = [ ( n , Dummy ( ) ) for n in sorted ( nc_symbols , key = default_sort_key ) ] <EOL> unrep1 = [ ( v , k ) for k , v in rep1 ] <EOL> unrep1 . reverse ( ) <EOL> new_mid , r2 , _ = _mask_nc ( mid . subs ( rep1 ) ) <EOL> new_mid = powsimp ( factor ( new_mid ) ) <EOL> new_mid = new_mid . subs ( r2 ) . subs ( unrep1 ) <EOL> if new_mid . is_Pow : <EOL> return _keep_coeff ( c , g * l * new_mid * r ) <EOL> if new_mid . is_Mul : <EOL> cfac = [ ] <EOL> ncfac = [ ] <EOL> for f in new_mid . args : <EOL> if f . is_commutative : <EOL> cfac . append ( f ) <EOL> else : <EOL> b , e = f . as_base_exp ( ) <EOL> if e . is_Integer : <EOL> ncfac . extend ( [ b ] * e ) <EOL> else : <EOL> ncfac . append ( f ) <EOL> pre_mid = g * Mul ( * cfac ) * l <EOL> target = _pemexpand ( expr / c ) <EOL> for s in variations ( ncfac , len ( ncfac ) ) : <EOL> ok = pre_mid * Mul ( * s ) * r <EOL> if _pemexpand ( ok ) == target : <EOL> return _keep_coeff ( c , ok ) <EOL> return _keep_coeff ( c , g * l * mid * r ) </s>
