######################################################################
##GuessPq.txt: Save this file as  GuessPq.txt                        #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read  GuessPq.txt <Enter>                          #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
##DoronZeil at gmail dot com                                         #
#Edited by Bryan Ek, Rutgers University ,                            #
#bryan.t.ek@math.rutgers.edu                                         #
######################################################################

print(`This is a small package for guessing a general polynomial for a list of polynomials in q.`):
print(`Originally written by Doron Zeilberger, Rutgers University.`):
print(`Edited by Bryan Ek, Rutgers University.`):
print(``):
print(`The latest version of this package is available from`):
print(`http://www.math.rutgers.edu/~bte14/Code/Gnk/GuessPq.txt`):
print(``):
print(`For a list of procedures, type ez().`):


ez:=proc()
	if args=NULL then
		print(`Procedures for guessing a polynomial in q^n are GPq, GPq1, GPq2.`):
		print(`For help with a specific procedure, type ezra(function).`):

	elif nops([args])=1 and op(1,[args])=GPq1 then
		print(`GPq1(L,q,n,d1): Guesses a polynomial of degree d1 in q^n for L[n]. L is a 1D list of polynomials in q. Try`):
		print(`GPq1([seq(q^n1,n1=1..20)],q,n,1);`):

	elif nops([args])=1 and op(1,[args])=GPq2 then
		print(`GPq2(L,q,n,d1): Guesses a polynomial of degree d1 in q^n for L[n]. L is a list of pairs of indices and polynomials in q. Try`):
		print(`GPq2([seq([n1,q^n1],n1=1..20)],q,n,1);`):

	elif nops([args])=1 and op(1,[args])=GPq then
		print(`GPq(L,q,n,d1): Guesses a polynomial of degree <=d1 in q^n for L[n]. Try`):
		print(`GPq([seq([n1,q^n1],n1=1..20)],q,n,1);`):

	else
		print(`There is no ezra for`,args):
	fi:
end:

#GPq1(L,q,n,d1): Guesses a polynomial of degree d1 in q^n for L[n]. Try
#GPq1([seq(q^n1,n1=1..20)],q,n,1);
GPq1:=proc(L,q,n,d1) local eq,var,a,P,eq1,i1,x,n1:
	var:={seq(a[i1],i1=0..d1)}:
	P:=add(a[i1]*x^i1,i1=0..d1):
	if nops(L)<d1+3 then
		RETURN(FAIL):
	fi:

	eq:={seq(subs(x=q^n1,P)-L[n1],n1=1..d1+2)}:
	eq1:=subs(q=3,eq):
	if solve(eq1,var)=NULL then
		RETURN(FAIL):
	fi:
	var:=solve(eq,var):
	P:=subs(var,P):

	if normal(expand({seq(subs(x=q^n1,P)-L[n1],n1=d1+3..nops(L))}))<>{0} then
		print(P, `did not work out`):
		RETURM(FAIL):
	fi:
	P:=factor(P):
	subs(x=q^n,P):
end:

#GPq2(L,q,n,d1): Guesses a polynomial of degree d1 in q^n for L[n].
GPq2:=proc(L,q,n,d1) local eq,var,a,P,eq1,i1,x,n1:
	var:={seq(a[i1],i1=0..d1)}:
	P:=add(a[i1]*x^i1,i1=0..d1):
	if nops(L)<d1+3 then
		RETURN(FAIL):
	fi:

	eq:={seq(subs(x=q^L[n1][1],P)-L[n1][2],n1=1..d1+2)}:
	eq1:=subs(q=3,eq):
	if solve(eq1,var)=NULL then
		RETURN(FAIL):
	fi:
	var:=solve(eq,var):
	P:=subs(var,P):

	if normal(expand({seq(subs(x=q^L[n1][1],P)-L[n1][2],n1=d1+3..nops(L))}))<>{0} then
		print(P, `did not work out`):
		RETURM(FAIL):
	fi:
	P:=factor(P):
	subs(x=q^n,P):
end:

#GPq(L,q,n,d1): Guesses a polynomial of degree <=d1 in q^n for L[n]. Try
#GPq([seq([n1,q^n1],n1=1..20)],q,n,1);
GPq:=proc(L,q,n,d1) local d11,gu:
	if nops(L)<d1+3 then
		print(`List too short`):
		RETURN(FAIL):
	fi:
	for d11 from 1 to d1 do
		gu:=GPq2(L,q,n,d11):
		if gu<>FAIL then
			RETURN(gu):
		fi:
	od:
	FAIL:
end: