#John Kim
#Use whatever you like

#read "C:/Users/John Y. Kim/Documents/Maple/hw9.txt":
#L:=[seq(U(n,x),n=0..25)]:
#P:=GuessPR1(L,y,2,1);
#solve(P,y[2]);

Help9:=proc(): print(`  GenHOMPolG(X,d,a,DegList, co), `):
print(` GPg(X,d,a,DegList) ,    GuessPR1(L,x,ORDER,DEGREE), M(n)  `): 
 end:


Help8:=proc(): 
print(`GenPol(X,d,a,co), GenHOMPol(X,d,a,co)`):
print(` GP(X,d,a) , GuessPR(L,x,ORDER,DEGREE)`):
end:

####Stuff from C8.txt#########################
#GenPol(X,d,a,co): 
#Inputs 
#(i) a list of variables X e.g. [x,y,z] (let m=nops(X), the number of
#variables)
#(ii)  a pos. integer d, for the degree
#(iii) a symbol a by which the coeff. (undetermined) of the pol.
#are expressed
#(iiii) co, starting counter
#Outputs: 
#(i)A generic polynomial in the variables X of degree d
#with coeff. expressed as a[co],ac[co+1], ...,  a[co+AsNeeded]
#(ii) the set of coefficients
#(iii) the new value of the counter
#For example, GenPol([x],1,a,0); should output
#a[0]+a[1]*x,{a[0],a[1]},2    
GenPol:=proc(X,d,a,co) local P, var, co1,m,i,x,X1,P1:
option remember:
m:=nops(X):


x:=X[1]:

if m=1 then
RETURN(add( a[co+i]*x^i,i=0..d), {seq(a[co+i],i=0..d)},co+d+1):
fi:


co1:=co:

X1:=[op(2..m,X)]:

P:=0:
var:={}:
for i from 0 to d do
P1:=GenPol(X1,d,a,co1):
P:=expand(P+P1[1]*x^i):
var:=var union P1[2]:
co1:=P1[3]:
od:

P,var,co1:
end:


#GenHOMPol(X,d,a,co): 
#Inputs 
#(i) a list of variables X e.g. [x,y,z] (let m=nops(X), the number of
#variables)
#(ii)  a pos. integer d, for the degree
#(iii) a symbol a by which the coeff. (undetermined) of the pol.
#are expressed
#(iiii) co, starting counter
#Outputs: 
#(i)A generic HOMOG. polynomial in the variables X of degree d
#with coeff. expressed as a[co],ac[co+1], ...,  a[co+AsNeeded]
#(ii) the set of coefficients
#(iii) the new value of the counter
#For example, GenPol([x],1,a,0); should output
#a[0]+a[1]*x,{a[0],a[1]},2    
GenHOMPol:=proc(X,d,a,co) local P, var, co1,m,i,x,X1,P1:
option remember:
m:=nops(X):


x:=X[1]:

if m=1 then
RETURN(a[co]*x^d, {a[co]},co+1):
fi:


co1:=co:

X1:=[op(2..m,X)]:

P:=0:
var:={}:
for i from 0 to d do
P1:=GenHOMPol(X1,d-i,a,co1):
P:=expand(P+P1[1]*x^i):
var:=var union P1[2]:
co1:=P1[3]:
od:

P,var,co1:
end:


#GP(X,d,a): 
#Inputs 
#(i) a list of variables X e.g. [x,y,z] (let m=nops(X), the number of
#variables)
#(ii)  a pos. integer d, for the degree
#(iii) a symbol a by which the coeff. (undetermined) of the pol.
#are expressed

#Outputs: 
#(i)A generic polynomial in the variables X of total degree d
#with coeff. expressed as a[co],ac[co+1], ...,  a[co+AsNeeded]
#(ii) the set of coefficients
#(iii) the new value of the counter
#For example, GenPol([x],1,a,0); should output
#a[0]+a[1]*x,{a[0],a[1]},2    
GP:=proc(X,d,a) local P, var,co1,d1,P1:

co1:=0:
P:=0:

var:={}:

for d1 from 0 to d do

P1:=GenHOMPol(X,d1,a,co1):

var:=var union P1[2] :

co1:=P1[3]:

P:=P+P1[1]:

od:

P,var:

end:

#GenHomPol(X,d,a,co): 
#Inputs 
#(i) a list of variables X e.g. [x,y,z] (let m=nops(X), the number of
#variables)
#(ii)  a pos. integer d, for the degree
#(iii) a symbol a by which the coeff. (undetermined) of the pol.
#are expressed
#(iiii) co, starting counter
#Outputs: 
#(i)A generic HOMOG. polynomial in the variables X of degree d
#with coeff. expressed as a[co],ac[co+1], ...,  a[co+AsNeeded]
#(ii) the set of coefficients
#(iii) the new value of the counter
#For example, GenPol([x],1,a,0); should output
#a[0]+a[1]*x,{a[0],a[1]},2    
GenHOMPol:=proc(X,d,a,co) local P, var, co1,m,i,x,X1,P1:
option remember:
m:=nops(X):


x:=X[1]:

if m=1 then
RETURN(a[co]*x^d, {a[co]},co+1):
fi:


co1:=co:

X1:=[op(2..m,X)]:

P:=0:
var:={}:
for i from 0 to d do
P1:=GenHOMPol(X1,d-i,a,co1):
P:=expand(P+P1[1]*x^i):
var:=var union P1[2]:
co1:=P1[3]:
od:

P,var,co1:
end:

#GuessPR(L,x,ORDER,DEGREE)
#Inputs 
#(i)a sequene L of numbers
#(ii) a SYMBOL x (for the indexed variables x[1],x[2], ...)
#(iii) a pos. integer, ORDER
#(iv) a pos. integer Degree
#Output
#A polynomial, let's call it, P(x[0],x[1], ..., x[ORDER]) such
#that for all n P(L[n],L[n+1], ..., L[n+ORDER])=0
GuessPR:=proc(L,x,ORDER,DEGREE) local X,i,P,var,eq,a:

X:=[seq(x[i],i=0..ORDER)]:

P:=GP(X,DEGREE,a):

var:=P[2]:

if nops(var)+6>nops(L) then
 print(`Please make the list longer, we need`, nops(var)+6 , `terms`):
 RETURN(FAIL):
fi:

P:=P[1]:

#eq:={ seq( subs( {x[0]=L[n],x[1]=L[n+1], ..., x[ORDER]=L[n+ORDER]},
#  P)=0, n=1..min(nops(L)-ORDER, nops(var)+6)  }:


eq:={ seq( subs( {seq(x[i]=L[n+i],i=0..ORDER)},
  P)=0, n=1.. nops(var)+6 ) }:

var:=solve(eq,var):

factor(subs(var,P)):

end:


#####End of stuff from C8.txt


###start new stuff
#GenHOMPolG(X,d,a,DegList, co): 
#Inputs 
#(i) a list of variables X e.g. [x,y,z] (let m=nops(X), the number of
#variables)
#(ii)  a pos. integer d, for the degree
#(iii) a symbol a by which the coeff. (undetermined) of the pol.
#are expressed
#(iv) a list of degrees for the individual variables (corres. X)
#(v) co, starting counter
#Outputs: 
#(i)A generic HOMOG. polynomial in the variables X of degree d
#with coeff. expressed as a[co],ac[co+1], ...,  a[co+AsNeeded]
#AND the degree in the variable X[i] is <=DegList[i]
#(ii) the set of coefficients
#(iii) the new value of the counter
#For example, GenHOMPolG([x,y],3,a,[1,2],0); should output
#a[0]*x*y^2,{a[0]},1    
GenHOMPolG:=proc(X,d,a,DegList,co) local 
P, var, co1,m,i,x,X1,P1,DegList1,d1:
option remember:
m:=nops(X):

if nops(DegList)<>m then
  RETURN(FAIL):
fi:

if convert(DegList,`+`)<d then
 RETURN(0,{},co):
fi:

x:=X[1]:
d1:=DegList[1]:

if m=1 then
RETURN(a[co]*x^d, {a[co]},co+1):
fi:


co1:=co:

X1:=[op(2..m,X)]:
DegList1:=[op(2..m,DegList)]:

P:=0:
var:={}:

for i from 0 to min(d,d1) do
P1:=GenHOMPolG(X1,d-i,a,DegList1,co1):
P:=expand(P+P1[1]*x^i):
var:=var union P1[2]:
co1:=P1[3]:
od:

P,var,co1:
end:

#GPg(X,d,a,DegList): 
#Inputs 
#(i) a list of variables X e.g. [x,y,z] (let m=nops(X), the number of
#variables)
#(ii)  a pos. integer d, for the degree
#(iii)A list of max. degrees,DegList for the variables
#(iv) a symbol a by which the coeff. (undetermined) of the pol.
#are expressed

#Outputs: 
#(i)A generic polynomial in the variables X of total degree d
#with coeff. expressed as a[co],ac[co+1], ...,  a[co+AsNeeded]
#(ii) the set of coefficients
#(iii) the new value of the counter
#For example, GenPol([x],1,a,0); should output
#a[0]+a[1]*x,{a[0],a[1]},2    
GPg:=proc(X,d,a,DegList) local P, var,co1,d1,P1:

co1:=0:
P:=0:

var:={}:

for d1 from 0 to d do

P1:=GenHOMPolG(X,d1,a,DegList,co1):

var:=var union P1[2] :

co1:=P1[3]:

P:=P+P1[1]:

od:

P,var:

end:

#GuessPR1(L,x,ORDER,DEGREE)
#Inputs 
#(i)a sequene L of numbers
#(ii) a SYMBOL x (for the indexed variables x[1],x[2], ...)
#(iii) a pos. integer, ORDER
#(iv) a pos. integer Degree
#Output
#A polynomial, let's call it, P(x[0],x[1], ..., x[ORDER]) 
#of degree 1 in x[ORDER]
#such
#that for all n P(L[n],L[n+1], ..., L[n+ORDER])=0
GuessPR1:=proc(L,x,ORDER,DEGREE) local X,i,P,var,eq,a:

X:=[seq(x[i],i=0..ORDER)]:

P:=GPg(X,DEGREE,a,[DEGREE$ORDER,1]):

var:=P[2]:

if nops(var)+6>nops(L) then
 print(`Please make the list longer, we need`, nops(var)+6 , `terms`):
 RETURN(FAIL):
fi:

P:=P[1]:

#eq:={ seq( subs( {x[0]=L[n],x[1]=L[n+1], ..., x[ORDER]=L[n+ORDER]},
#  P)=0, n=1..min(nops(L)-ORDER, nops(var)+6)  }:


eq:={ seq( subs( {seq(x[i]=L[n+i],i=0..ORDER)},
  P)=0, n=1.. nops(var)+6 ) }:

var:=solve(eq,var):

factor(subs(var,P)):

end:




#x[2]:=(1-2*x[1]^2+x[0]*x[1])/(-x[1]+x[0])

#The sequence of RATIONAL  numbers  (a priori)
#defined by M(1)=1, M(2)=4, and
#M(n)=(1-2*M(n-1)^2+M(n-2)*M(n-1))/(M(n-2)-M(n-1)):
M:=proc(n) option remember:

if n=1 then
 1:
elif n=2 then
 4:
else
(1-2*M(n-1)^2+M(n-2)*M(n-1))/(M(n-2)-M(n-1)):
fi:

end:


#U(n,x): The nth Chebychev polynomials of the second kind in the variable x.
U:=proc(n,x) option remember:

if n=0 then
 1:
elif n=1 then
 2*x:
else
 2*x*U(n-1,x)-U(n-2,x):
fi:

end:

#T(n,x): The square of the nth Chebychev polynomial of the second kind in the variable x.
#It satisfies the 2nd order linear recurrence:
#T(n,x)=2+4*T(n-1,x)*x^2-2*T(n-1,x)-T(n-2,x).

T:=proc(n,x) option remember:

if n=0 then
 1:
elif n=1 then
 4*x^2:
else
 2+4*T(n-1,x)*x^2-2*T(n-1,x)-T(n-2,x):
fi:

end:


#GFtoSeq(f,q,m): inputs an expression f in the variable q and 
#outputs the list of numbers L of length m, such that L[i] is 
#the coefficient of q^(i-1) in the Maclaurin series.

GFtoSeq:=proc(f,q,m) local i:
[seq(coeff(taylor(f,q=0,m),q,i),i=0..m-1)]:
end:


#Find linear recurrence that coeffs of gen function satisfy via GuessPR1.
#Solve for highest order term.

SeqToGF:=proc(L,q) local ORD,P,x,i,j:

ORD:=1:
P:=GuessPR1(L,x,ORD,1):

if P<>FAIL and P<>0 then
 RETURN(simplify(subs({x[0]=0,seq(x[i]=add(L[i-j+1]*q^(ORD-j),j=1..i),i=1..ORD)},P)/subs({seq(x[i]=q^(ORD-i),i=0..ORD)},P))):
fi:

while(ORD<=6 and (P=FAIL or P=0)) do
 
 ORD:=ORD+1:
 P:=GuessPR1(L,x,ORD,1):
 if P<>FAIL and P<>0 then
  RETURN(simplify(subs({x[0]=0,seq(x[i]=add(L[i-j+1]*q^(ORD-j),j=1..i),i=1..ORD)},P)/subs({seq(x[i]=q^(ORD-i),i=0..ORD)},P))):
 fi:

od:

FAIL:

end: