<s> """<STR_LIT>""" <EOL> from __future__ import print_function , division <EOL> from sympy . utilities import public <EOL> from sympy . core . compatibility import range <EOL> from sympy . core import Function , Symbol <EOL> from sympy . core . numbers import Zero <EOL> from sympy import ( sympify , floor , lcm , denom , Integer , Rational , <EOL> exp , integrate ) <EOL> @ public <EOL> def find_simple_recurrence_vector ( l ) : <EOL> """<STR_LIT>""" <EOL> q1 = [ <NUM_LIT:0> ] <EOL> q2 = [ Integer ( <NUM_LIT:1> ) ] <EOL> z = len ( l ) >> <NUM_LIT:1> <EOL> while len ( q2 ) <= z : <EOL> b = <NUM_LIT:0> <EOL> while l [ b ] == <NUM_LIT:0> : <EOL> b += <NUM_LIT:1> <EOL> if b == len ( l ) : <EOL> c = <NUM_LIT:1> <EOL> for x in q2 : <EOL> c = lcm ( c , denom ( x ) ) <EOL> if q2 [ <NUM_LIT:0> ] * c < <NUM_LIT:0> : c = - c <EOL> for k in range ( len ( q2 ) ) : <EOL> q2 [ k ] = int ( q2 [ k ] * c ) <EOL> return q2 <EOL> m = [ Integer ( <NUM_LIT:1> ) / l [ b ] ] <EOL> for k in range ( b + <NUM_LIT:1> , len ( l ) ) : <EOL> s = <NUM_LIT:0> <EOL> for j in range ( b , k ) : <EOL> s -= l [ j + <NUM_LIT:1> ] * m [ b - j - <NUM_LIT:1> ] <EOL> m . append ( s / l [ b ] ) <EOL> l = m <EOL> a , l [ <NUM_LIT:0> ] = l [ <NUM_LIT:0> ] , <NUM_LIT:0> <EOL> q = [ <NUM_LIT:0> ] * max ( len ( q2 ) , b + len ( q1 ) ) <EOL> for k in range ( len ( q2 ) ) : <EOL> q [ k ] = a * q2 [ k ] <EOL> for k in range ( b , b + len ( q1 ) ) : <EOL> q [ k ] += q1 [ k - b ] <EOL> while q [ - <NUM_LIT:1> ] == <NUM_LIT:0> : q . pop ( ) <EOL> q1 , q2 = q2 , q <EOL> return [ <NUM_LIT:0> ] <EOL> @ public <EOL> def find_simple_recurrence ( v , A = Function ( '<STR_LIT:a>' ) , N = Symbol ( '<STR_LIT:n>' ) ) : <EOL> """<STR_LIT>""" <EOL> p = find_simple_recurrence_vector ( v ) <EOL> n = len ( p ) <EOL> if n <= <NUM_LIT:1> : return Zero ( ) <EOL> rel = Zero ( ) <EOL> for k in range ( n ) : <EOL> rel += A ( N + n - <NUM_LIT:1> - k ) * p [ k ] <EOL> return rel <EOL> @ public <EOL> def rationalize ( x , maxcoeff = <NUM_LIT> ) : <EOL> """<STR_LIT>""" <EOL> p0 , p1 = <NUM_LIT:0> , <NUM_LIT:1> <EOL> q0 , q1 = <NUM_LIT:1> , <NUM_LIT:0> <EOL> a = floor ( x ) <EOL> while a < maxcoeff or q1 == <NUM_LIT:0> : <EOL> p = a * p1 + p0 <EOL> q = a * q1 + q0 <EOL> p0 , p1 = p1 , p <EOL> q0 , q1 = q1 , q <EOL> if x == a : break <EOL> x = <NUM_LIT:1> / ( x - a ) <EOL> a = floor ( x ) <EOL> return sympify ( p ) / q <EOL> @ public <EOL> def guess_generating_function_rational ( v , X = Symbol ( '<STR_LIT:x>' ) ) : <EOL> """<STR_LIT>""" <EOL> q = find_simple_recurrence_vector ( v ) <EOL> n = len ( q ) <EOL> if n <= <NUM_LIT:1> : return None <EOL> p = [ sum ( v [ i - k ] * q [ k ] for k in range ( min ( i + <NUM_LIT:1> , n ) ) ) <EOL> for i in range ( len ( v ) ) ] <EOL> return ( sum ( p [ k ] * X ** k for k in range ( len ( p ) ) ) <EOL> / sum ( q [ k ] * X ** k for k in range ( n ) ) ) <EOL> @ public <EOL> def guess_generating_function ( v , X = Symbol ( '<STR_LIT:x>' ) , types = [ '<STR_LIT:all>' ] , maxsqrtn = <NUM_LIT:2> ) : <EOL> """<STR_LIT>""" <EOL> if '<STR_LIT:all>' in types : <EOL> types = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> result = { } <EOL> if '<STR_LIT>' in types : <EOL> t = [ <NUM_LIT:1> if k == <NUM_LIT:0> else <NUM_LIT:0> for k in range ( len ( v ) ) ] <EOL> for d in range ( max ( <NUM_LIT:1> , maxsqrtn ) ) : <EOL> t = [ sum ( t [ n - i ] * v [ i ] for i in range ( n + <NUM_LIT:1> ) ) for n in range ( len ( v ) ) ] <EOL> g = guess_generating_function_rational ( t , X = X ) <EOL> if g : <EOL> result [ '<STR_LIT>' ] = g ** Rational ( <NUM_LIT:1> , d + <NUM_LIT:1> ) <EOL> break <EOL> if '<STR_LIT>' in types : <EOL> w , f = [ ] , Integer ( <NUM_LIT:1> ) <EOL> for i , k in enumerate ( v ) : <EOL> f *= i if i else <NUM_LIT:1> <EOL> w . append ( k / f ) <EOL> t = [ <NUM_LIT:1> if k == <NUM_LIT:0> else <NUM_LIT:0> for k in range ( len ( w ) ) ] <EOL> for d in range ( max ( <NUM_LIT:1> , maxsqrtn ) ) : <EOL> t = [ sum ( t [ n - i ] * w [ i ] for i in range ( n + <NUM_LIT:1> ) ) for n in range ( len ( w ) ) ] <EOL> g = guess_generating_function_rational ( t , X = X ) <EOL> if g : <EOL> result [ '<STR_LIT>' ] = g ** Rational ( <NUM_LIT:1> , d + <NUM_LIT:1> ) <EOL> break <EOL> if '<STR_LIT>' in types : <EOL> w , f = [ ] , Integer ( - <NUM_LIT:1> ) <EOL> for i , k in enumerate ( v ) : <EOL> f = - f <EOL> w . append ( f * k / Integer ( i + <NUM_LIT:1> ) ) <EOL> t = [ <NUM_LIT:1> if k == <NUM_LIT:0> else <NUM_LIT:0> for k in range ( len ( w ) ) ] <EOL> for d in range ( max ( <NUM_LIT:1> , maxsqrtn ) ) : <EOL> t = [ sum ( t [ n - i ] * w [ i ] for i in range ( n + <NUM_LIT:1> ) ) for n in range ( len ( w ) ) ] <EOL> g = guess_generating_function_rational ( t , X = X ) <EOL> if g : <EOL> result [ '<STR_LIT>' ] = g ** Rational ( <NUM_LIT:1> , d + <NUM_LIT:1> ) <EOL> break <EOL> if '<STR_LIT>' in types : <EOL> w = [ ] <EOL> for i , k in enumerate ( v ) : <EOL> w . append ( k / Integer ( i + <NUM_LIT:1> ) ) <EOL> t = [ <NUM_LIT:1> if k == <NUM_LIT:0> else <NUM_LIT:0> for k in range ( len ( w ) ) ] <EOL> for d in range ( max ( <NUM_LIT:1> , maxsqrtn ) ) : <EOL> t = [ sum ( t [ n - i ] * w [ i ] for i in range ( n + <NUM_LIT:1> ) ) for n in range ( len ( w ) ) ] <EOL> g = guess_generating_function_rational ( t , X = X ) <EOL> if g : <EOL> result [ '<STR_LIT>' ] = g ** Rational ( <NUM_LIT:1> , d + <NUM_LIT:1> ) <EOL> break <EOL> if v [ <NUM_LIT:0> ] != <NUM_LIT:0> and ( '<STR_LIT>' in types <EOL> or ( '<STR_LIT>' in types and '<STR_LIT>' not in result ) ) : <EOL> a , w = sympify ( v [ <NUM_LIT:0> ] ) , [ ] <EOL> for n in range ( len ( v ) - <NUM_LIT:1> ) : <EOL> w . append ( <EOL> ( v [ n + <NUM_LIT:1> ] * ( n + <NUM_LIT:1> ) - sum ( w [ - i - <NUM_LIT:1> ] * v [ i + <NUM_LIT:1> ] for i in range ( n ) ) ) / a ) <EOL> t = [ <NUM_LIT:1> if k == <NUM_LIT:0> else <NUM_LIT:0> for k in range ( len ( w ) ) ] <EOL> for d in range ( max ( <NUM_LIT:1> , maxsqrtn ) ) : <EOL> t = [ sum ( t [ n - i ] * w [ i ] for i in range ( n + <NUM_LIT:1> ) ) for n in range ( len ( w ) ) ] <EOL> g = guess_generating_function_rational ( t , X = X ) <EOL> if g : <EOL> result [ '<STR_LIT>' ] = g ** Rational ( <NUM_LIT:1> , d + <NUM_LIT:1> ) <EOL> if '<STR_LIT>' not in result : <EOL> result [ '<STR_LIT>' ] = exp ( integrate ( result [ '<STR_LIT>' ] , X ) ) <EOL> break <EOL> if v [ <NUM_LIT:0> ] != <NUM_LIT:0> and ( '<STR_LIT>' in types <EOL> or ( '<STR_LIT>' in types and '<STR_LIT>' not in result ) ) : <EOL> z , f = [ ] , Integer ( <NUM_LIT:1> ) <EOL> for i , k in enumerate ( v ) : <EOL> f *= i if i else <NUM_LIT:1> <EOL> z . append ( k / f ) <EOL> a , w = z [ <NUM_LIT:0> ] , [ ] <EOL> for n in range ( len ( z ) - <NUM_LIT:1> ) : <EOL> w . append ( <EOL> ( z [ n + <NUM_LIT:1> ] * ( n + <NUM_LIT:1> ) - sum ( w [ - i - <NUM_LIT:1> ] * z [ i + <NUM_LIT:1> ] for i in range ( n ) ) ) / a ) <EOL> t = [ <NUM_LIT:1> if k == <NUM_LIT:0> else <NUM_LIT:0> for k in range ( len ( w ) ) ] <EOL> for d in range ( max ( <NUM_LIT:1> , maxsqrtn ) ) : <EOL> t = [ sum ( t [ n - i ] * w [ i ] for i in range ( n + <NUM_LIT:1> ) ) for n in range ( len ( w ) ) ] <EOL> g = guess_generating_function_rational ( t , X = X ) <EOL> if g : <EOL> result [ '<STR_LIT>' ] = g ** Rational ( <NUM_LIT:1> , d + <NUM_LIT:1> ) <EOL> if '<STR_LIT>' not in result : <EOL> result [ '<STR_LIT>' ] = exp ( integrate ( result [ '<STR_LIT>' ] , X ) ) <EOL> break <EOL> return result </s>
