######################################################################
##ArithFormulas: Save this file as  ArithFormulas                    #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read ArithFormulas<Enter>                          #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Edinah K. Gnang and Doron Zeilberger, Rutgers University#
#zeilberg at math dot rutgers dot edu                                #
######################################################################
 
#Created: Feb.-March, 2013
 
print(`First posted:  March 1, 2013`):
print(` This is ArithFormulas `):
print(`It is a package that accompanies the article `):
print(`Zeroless Arithmetic: Representing Integers ONLY Using ONE`):
print(`by Edinah K. Gnang and Doron Zeilberger`):
print(`available from both Gnang's and Zeilberger's websites`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/  .`):

print(`------------------------------------------------`):
 print(`For a list of main procedures  format`):
print(` type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):

print(`------------------------------------------------`):
 print(`For a list of procedures  to generate sequences`):
print(` type ezraSeq();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):

print(`------------------------------------------------`):
 print(`For a list of supporting procedures  format`):
print(` type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):


print(`------------------------------------------------`):
 print(`For a list of the procedures in Tree format`):
print(` type ezraT();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`------------------------------------------------`):
 print(`For a list of the procedures in PostFix format`):
print(` type ezraP();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`------------------------------------------------`):


with(combinat):




ezraSeq:=proc()

if args=NULL then
 print(` The procedures to produce interesting sequences are: `):
 print(` CaSeq, CaeSeq, CameSeq, CamSeq `):
 print(` ShortestFaeSeq, ShortestFamSeq,ShortestFam21Seq,ShortestFameSeq `):
else
ezra(args):
fi:

end:

ezraP:=proc()

if args=NULL then
 print(` The PostFix-Format procedures are: `):
  print(` EvalP `):
 print(` FaP, , RaFaP,  `):
 print(` FaeP, , RaFaeP`):
 print(` FamP, , RaFamP`):
 print(` FameP, , RaFameP`):
 print(` ShortestPam, ShortestPae,ShortestPame `):

else
ezra(args):
fi:

end:

ezraT:=proc()

if args=NULL then
 print(` The Tree-Format procedures are: `):
 print(` EvalT `):
 print(` FaT, , RaFaT `):
 print(` FaeT, , RaFaeT `):
 print(` FamT, , RaFamT `):
 print(` FameT, RaFameT `):
 print(` ShortestTae, ShortestTam, ShortestTam21, ShortestTame `):
else
ezra(args):
fi:

end:

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are: `):
 print(`Cama, Camm, `):
 print(` CheckGFam, CheckGFame `):
 print(` FamTa, FamTm, , `):
 print(`FameTa,  FameTm, FameTe`):
 print(`LopCa , LopFaP, LopFaT, MinMemory, Mishkal, RollLD,  `):
 print(` RaFamTa, RaFamTm `):
 print(`    RaLopFaT,  RaLopFaP `):
 print(` TtoP, Zinn `):


else
ezra(args):
fi:

end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are: `):
 print(``):
 print(` Ca, Cae, Cam, Came, FCF, GFam, GFame, Omek, SCF`):
 print(` SeferAE, SeferAM, SeferAME, Stra `):
 

elif nops([args])=1 and op(1,[args])=Ca then
 print(` Ca(n): the number of formula-binary trees only using addition`):
 print(`that evaluate to the pos. integer n`):
 print(`try: Ca(6);`):


elif nops([args])=1 and op(1,[args])=Cae then
 print(` Cae(n): the number of formula-binary trees only using addition`):
 print(`and exponentiation `):
 print(`that evaluate to the pos. integer n`):
 print(`try: Cae(6);`):

elif nops([args])=1 and op(1,[args])=CaeSeq then
 print(` CaeSeq(n): the sequence of the `):
 print(` number of formula-binary trees only using addition`):
 print(`and exponentiation  for the integers from 1 to n. Try`):
 print(`try: CaeSeq(20);`):

elif nops([args])=1 and op(1,[args])=Cam then
 print(` Cam(n): the number of formula-binary trees only using addition`):
 print(`and multiplication `):
 print(`that evaluate to the pos. integer n`):
 print(`try: Cam(6);`):

elif nops([args])=1 and op(1,[args])=CamSeq then
 print(` CamSeq(n): the sequence of the `):
 print(` number of formula-binary trees only using addition`):
 print(`and multiplication  for the integers from 1 to n. Try`):
 print(`try: CamSeq(20);`):


elif nops([args])=1 and op(1,[args])=Came then
 print(` Came(n): the number of formula-binary trees only  addition`):
 print(`multiplication, and exponentiation `):
 print(`that evaluate to the pos. integer n`):
 print(`try: Came(6);`):


elif nops([args])=1 and op(1,[args])=Cama then
 print(` Cama(n): the number of formula-binary trees only using addition`):
 print(`and multiplication where the top operation is addition`):
 print(`that evaluate to the pos. integer n`):
 print(`try: Cama(6);`):

elif nops([args])=1 and op(1,[args])=Camm then
 print(` Camm(n): the number of formula-binary trees only using addition`):
 print(`and multiplication where the top operation is multiplication`):
 print(`that evaluate to the pos. integer n`):
 print(`try: Camm(6);`):


elif nops([args])=1 and op(1,[args])=CheckGFam then
print(`CheckGFam(n): checks procedure GFam(n,x,a,m) by`):
print(`doing it by brute force.`):
print(` up to FamP(n). `):
print(`Try: CheckGFam(6);`):

elif nops([args])=1 and op(1,[args])=CheckGFame then
print(`CheckGFame(n): checks procedure GFame(n,x,a,m,e) by`):
print(`doing it by brute force.`):
print(` up to FamPe(n). `):
print(`Try: CheckGFam(6);`):

elif nops([args])=1 and op(1,[args])=EvalP then
print(`EvalP(T): evaluates the formula in postfix notation, try:`):
print(`EvalP(FameP(5)[1]);`):

elif nops([args])=1 and op(1,[args])=EvalT then
print(`EvalT(T): evaluates the formula tree, try:`):
print(`EvalT(FameT(5)[1]);`):

elif nops([args])=1 and op(1,[args])=FamP then
 print(` FamP(n): All the of formulas, in postfix notaion`):
 print(`  only using addition`):
 print(`and multiplication `):
  print(`that evaluate to the pos. integer n`):
 print(`try: FamP(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FameP then
 print(` FameP(n): All the of formulas, in postfix notaion`):
 print(`  using addition, multiplication and exponentiation,`):
  print(`that evaluate to the pos. integer n`):
 print(`try: FameP(6);`):
 print(``):


elif nops([args])=1 and op(1,[args])=FaT then
 print(` FaT(n): All the of formula-binary trees only using addition`):
  print(`that evaluate to the pos. integer n`):
 print(`try: FaT(6);`):
 print(``):


elif nops([args])=1 and op(1,[args])=FameT then
 print(` FameT(n): All the of formula-binary trees using addition,`):
 print(`multiplication and exponentiation `):
  print(`that evaluate to the pos. integer n`):
 print(`try: FameT(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FameTa then
 print(` FameTa(n): All the of formula-binary trees only using addition`):
 print(`multiplication and exponentiation `):
  print(`that evaluate to the pos. integer n`):
  print(`and the top operation is addition`):
 print(`try: FameTa(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FameTm then
 print(` FameTm(n): All the of formula-binary trees only using addition`):
 print(`multiplication and exponentiation `):
  print(`that evaluate to the pos. integer n`):
  print(`and the top operation is multiplication`):
 print(`try: FameTm(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FameTe then
 print(` FameTe(n): All the of formula-binary trees only using addition`):
 print(`multiplication and exponentiation `):
  print(`that evaluate to the pos. integer n`):
  print(`and the top operation is exponentiation`):
 print(`try: FameTe(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FaeT then
 print(` FaeT(n): All the of formula-binary trees only using addition`):
 print(`and multiplication `):
  print(`that evaluate to the pos. integer n`):
 print(`try: FaeT(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FamT then
 print(` FamT(n): All the of formula-binary trees only using addition`):
 print(`and multiplication `):
  print(`that evaluate to the pos. integer n`):
 print(`try: FamT(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FamTa then
 print(` FamTa(n): All the of formula-binary trees only using addition`):
 print(`and multiplication where the top operation is plus`):
  print(`that evaluate to the pos. integer n`):
 print(`try: FamTa(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FamTm then
 print(` FamTa(n): All the of formula-binary trees only using addition`):
 print(`and multiplication where the top operation is times`):
  print(`that evaluate to the pos. integer n`):
 print(`try: FamTm(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FaP then
 print(` FaP(n): All the of formula-binary trees only using addition`):
 print(`that evaluate to the pos. integer n`):
 print(`In Postfix FORMAT `):
 print(`try: FaP(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FaeP then
 print(` FaeP(n): All the of formula-binary trees only using addition`):
print(`and exponentiation `):
 print(`that evaluate to the pos. integer n`):
 print(`In Postfix FORMAT `):
 print(`try: FaeP(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=FCF then
print(`FCF(n): the First Canonical Form based on Goodstein encoding`):
print(` (iterated binary representation). Try:`):
print(`FCF(10);`):


elif nops([args])=1 and op(1,[args])=GFam then
print(`GFam(n,x,a,m): The weight-enumerator of the set of`):
print(`of formula-binary trees only using addition`):
print(`and multiplication, where the weight of a formula is`):
print(`x^(length)*a^(#pluses)*m^(#times)`):
print(`try: GFam(6,x,a,m);`):

elif nops([args])=1 and op(1,[args])=GFame then
print(`GFame(n,x,a,m): The weight-enumerator of the set of`):
print(`of formula-binary trees using addition,`):
print(`multiplication and exponentiation, where the weight of a formula is`):
print(`x^(length)*a^(#pluses)*m^(#times)*e^(#^)`):
print(`try: GFame(6,x,a,m,e);`):

elif nops([args])=1 and op(1,[args])=LopFaP then
 print(` LopFaP(n):All the of formulas in Postfix, only using addition`):
 print(`that evaluate to the pos. integer n`):
 print(`but where all in all additions the left term is >=the right term`):
 print(`try: LopFaP(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=LopFaT then
 print(` LopFaT(n): All the of formula-binary trees only using addition`):
 print(`that evaluate to the pos. integer n`):
 print(`but where all in all additions the left term is >=the right term`):
 print(`try: LopFaT(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=LopCa then
 print(` LopCa(n): the number of lop-sided, where a+b and a>=b` ):
 print(`formula-binary trees only using addition`):
 print(`that evaluate to the pos. integer n`):
 print(`try: LopCa(6);`):
 print(``):

elif nops([args])=1 and op(1,[args])=MinMemory then
print(`MinMemory(T): given a formula-tree finds an equivalent`):
print(`form such that the Strahler number of the left-child`):
print(`is always >=0 to that of the right child for any node`):
print(`in case of ties, the left-child should evaluate to a larger`):
print(`number than the right child, and in case of ties again,`):
print(`we pick at random`):
print(`Try:`):
print(`MinMemory(["+",1,1]); `):

elif nops([args])=1 and op(1,[args])=Mishkal then
print(`Mishkal(P,x,a,m,e): the weight of the formula P in postfix notation`):
print(`x^(nops(P))*a^(#pluses)*m^(#times)*e^(#^)`):
print(`try:`):
print(` Mishkal([1,1,"+"],x,a,m,e); `):

elif nops([args])=1 and op(1,[args])=Omek then
print(`Omek(T): the depth of the formula-tree T`):

elif nops([args])=1 and op(1,[args])=RaFameP then
print(`RaFameP(n): a uniformly at random formula evaluating to the pos.`):
print(`integer n using addition, multiplication, and exponentiations. `):
print(`In postfix notation `):
print(`Try:`):
print(`RaFameP(10);`):

elif nops([args])=1 and op(1,[args])=RaFamP then
print(`RaFamP(n): a uniformly at random formula evaluating to the pos.`):
print(`integer n only using addition and multiplication. `):
print(`In postfix notation `):
print(`Try:`):
print(`RaFamP(10);`):

elif nops([args])=1 and op(1,[args])=RaFaT then
print(`RaFaT(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition. Try:`):
print(`RaFaT(10);`):

elif nops([args])=1 and op(1,[args])=RaFaeP then
print(`RaFaeP(n): a uniformly at random postfix expression of the pos.`):
print(`integer n only using addition and exponentiation. Try:`):
print(`RaFaeP(10);`):

elif nops([args])=1 and op(1,[args])=RaFaeT then
print(`RaFaeT(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition and exponentiation. Try:`):
print(`RaFaeT(10);`):

elif nops([args])=1 and op(1,[args])=RaFameT then
print(`RaFameT(n): a uniformly at random formula tree of the pos.`):
print(`integer n using addition, multiplication and exponentiation. Try:`):
print(`RaFameT(10);`):

elif nops([args])=1 and op(1,[args])=RaFameTa then
print(`RaFameTa(n): a uniformly at random formula tree of the pos.`):
print(`integer n using addition, multiplication and exponentiation. `):
print(` where the top is addition. `):
print(`Try:`):
print(`RaFameTa(10);`):

elif nops([args])=1 and op(1,[args])=RaFameTm then
print(`RaFameTm(n): a uniformly at random formula tree of the pos.`):
print(`integer n using addition, multiplication and exponentiation. `):
print(` where the top is multiplication. `):
print(`Try:`):
print(`RaFameTm(10);`):

elif nops([args])=1 and op(1,[args])=RaFameTe then
print(`RaFameTe(n): a uniformly at random formula tree of the pos.`):
print(`integer n using addition, multiplication and exponentiation. `):
print(` where the top is exponentiation. `):
print(`Try:`):
print(`RaFameTe(10);`):

elif nops([args])=1 and op(1,[args])=RaFamT then
print(`RaFamT(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition and multiplication. Try:`):
print(`RaFamT(10);`):

elif nops([args])=1 and op(1,[args])=RaFamTa then
print(`RaFamTa(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition and multiplication, where the top`):
print(`is addition. Try:`):
print(`RaFamTa(10);`):

elif nops([args])=1 and op(1,[args])=RaFamTm then
print(`RaFamTm(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition and multiplication, where the top`):
print(`is multiplication. Try:`):
print(`RaFamTm(10);`):


elif nops([args])=1 and op(1,[args])=RaFaP then
print(`RaFaP(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition. Postfix Format.Try:`):
print(`RaFaP(10);`):

elif nops([args])=1 and op(1,[args])=RaLopFaT then
print(`RaLopFaT(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition and whenver there is an addition`):
print(`a+b, a>=b. Try:`):
print(`RaLopFaT(10);`):

elif nops([args])=1 and op(1,[args])=RaLopFaP then
print(`RaLopFaP(n): a uniformly at random formula tree of the pos.`):
print(`integer n only using addition and whenver there is an addition`):
print(`a+b, a>=b. In Postfix format. Try:`):
print(`RaLopFaP(10);`):


elif nops([args])=1 and op(1,[args])=RollLD then
print(`RollLD(L): Given a Loaded die, L, rolls it, try:`):
print(`RollLD([1,3,2]);`):


elif nops([args])=1 and op(1,[args])=SCF then
print(`SCF(n): the Second Canonical Form based on Gnang encoding`):
print(`(using iterated Fundamental Theorem of Arithmetics).`):
print(`Try:`):
print(`SCF(10);`):

elif nops([args])=1 and op(1,[args])=SeferAE then
print(`SeferAE(K1,K2): inputs  positive integers K1 and K2 and outputs`):
print(`a webbook about formuals representing integers up to K2.`):
print(`using addition and exponentiation`):
print(`It also gives the enumerating sequence, the number of formulas`):
print(`representations of n for n from 1 to K1`):
print(`Try: `):
print(`SeferAE(30,100): `):

elif nops([args])=1 and op(1,[args])=SeferAM then
print(`SeferAM(K1,K2): inputs  positive integers K1 and K2 and outputs`):
print(`a webbook about formuals representing integers up to K2.`):
print(`using addition and multiplication.`):
print(`It also gives the enumerating sequence, the number of formulas`):
print(`representations of n for n from 1 to K1`):
print(`Try: `):
print(`SeferAM(30,100): `):

elif nops([args])=1 and op(1,[args])=SeferAME then
print(`SeferAME(K1,K2): inputs  positive integers K1 and K2 and outputs`):
print(`a webbook about formuals representing integers up to K2.`):
print(`using addition, multiplication, and exponentiation`):
print(`It also gives the enumerating sequence, the number of formulas`):
print(`representations of n for n from 1 to K1`):
print(`Try: `):
print(`SeferAME(30,100): `):

elif nops([args])=1 and op(1,[args])=ShortestFaeSeq then
print(`ShortestFaeSeq(N): the sequence whose n-th entry, from`):
print(`1 to N is the length of the shortest formula, only using`):
print(`addition and exponentiation that evaluate to n,`):
print(`Try: `):
print(`ShortestFaeSeq(30); `):

elif nops([args])=1 and op(1,[args])=ShortestFameSeq then
print(`ShortestFameSeq(N): the sequence whose n-th entry, from`):
print(`1 to N is the length of the shortest formula, using`):
print(`addition, multiplication, and exponentiation, that evaluates to n,`):
print(`Try: `):
print(`ShortestFameSeq(30); `):

elif nops([args])=1 and op(1,[args])=ShortestFamSeq then
print(`ShortestFamSeq(N): the sequence whose n-th entry, from`):
print(`1 to N is the length of the shortest formula, only using`):
print(`addition and multiplication that evaluate to n,`):
print(`Try: `):
print(`ShortestFamSeq(30); `):

elif nops([args])=1 and op(1,[args])=ShortestFam21Seq then
print(`ShortestFam21Seq(N): the sequence whose n-th entry, from`):
print(`1 to N is the length of the shortest formula, only using`):
print(`addition and multiplication with inputs 1 and 2, that evaluate to n,`):
print(`Try: `):
print(`ShortestFam21Seq(30); `):


elif nops([args])=1 and op(1,[args])=ShortestPae then
print(`ShortestPae(n): A shortest expression evaluating`):
print(`to n only using addition and exponentiation. `):
print(`in postfix notation`):
print(`Try:`):
print(`ShortestPae(10);`):

elif nops([args])=1 and op(1,[args])=ShortestPam then
print(`ShortestPam(n): A shortest expression evaluating`):
print(`to n only using addition and multiplication. `):
print(`in postfix notation`):
print(`Try:`):
print(`ShortestPam(10);`):

elif nops([args])=1 and op(1,[args])=ShortestPame then
print(`ShortestPame(n): A shortest expression evaluating`):
print(`to n using addition, multiplication, and exponentiation, `):
print(`expressed in postfix notation.`):
print(`Try:`):
print(`ShortestPame(10);`):

elif nops([args])=1 and op(1,[args])=ShortestTae then
print(`ShortestTae(n):`):
print(`the length of the shortest expression, `):
print(`followed by one of them, evaluating `):
print(`to n only using addition and exponentiation. Try:`):
print(`ShortestTae(10);`):

elif nops([args])=1 and op(1,[args])=ShortestTam then
print(`ShortestTam(n):`):
print(`the length of the shortest expression, `):
print(`followed by one of them, evaluating `):
print(`to n only using addition and multiplication. Try:`):
print(`ShortestTam(10);`):

elif nops([args])=1 and op(1,[args])=ShortestTam21 then
print(`ShortestTam21(n): `):
print(`the length of the shortest expression, `):
print(`followed by one of them evaluating`):
print(`to n using addition and multiplication`):
print(`and allowing both 1 and 2 as inputs Try:`):
print(`ShortestTam21(10);`):

elif nops([args])=1 and op(1,[args])=ShortestTame then
print(`ShortestTame(n):`):
print(`the length of the shortest expression, `):
print(`followed by one of them, evaluating `):
print(`to n using addition, multiplication, and exponentiation. Try:`):
print(`ShortestTame(10);`):

elif nops([args])=1 and op(1,[args])=Stra then
print(`Stra(T): the Strahler number  of the formula-tree T`):

elif nops([args])=1 and op(1,[args])=TtoP then
print(`TtoP(T): converts the formula tree to postfix notation`):
print(`try:`):
print(`TtoP(["*",["+",1,1],["+",1,1]]);`):


elif nops([args])=1 and op(1,[args])=Zinn then
print(`Zinn(L): Inputs a list and outputs numbers theta,mu`):
print(`that are non-rigorous `):
print(`esimates such that L[n] is a const. times`):
print(`mu^n *n^theta. Try: `):
print(`Zinn([seq(2^i*i,i=1..50)]);`):


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

sn:=proc(resh,n1):
-1/log(op(n1+1,resh)*op(n1-1,resh)/op(n1,resh)^2):
end:
 
#Zinn(resh): Zinn-Justin's method to estimate
#the C,mu, and theta such that
#resh[i] is appx. Const*mu^i*i^theta
#For example, try:
#Zinn([seq(5*i*2^i,i=1..30)]);
Zinn:=proc(resh)
local s1,s2,theta,mu,n1,i:
if nops({seq(sign(resh[i]),i=1..nops(resh))})<>1 then
 RETURN(FAIL):
fi:

n1:=nops(resh)-1:
s1:=sn(resh,n1):
s2:=sn(resh,n1-1):
theta:=evalf(2*(s1+s2)/(s1-s2)^2):
mu:=evalf(sqrt(op(n1+1,resh)/op(n1-1,resh))*exp(-(s1+s2)/((s1-s2)*s1))):
[theta,mu]:
end:

#RollLD(L): Given a Loaded die, L, rolls it, try:
#RollLD([1,3,2]);
RollLD:=proc(L) local i,r,N:
N:=convert(L,`+`):
r:=rand(1..N)():

for i from 1 to nops(L) while convert([op(1..i,L)],`+`)<r do od:
i:

end:

###Begin only addition

#FaT(n): All the of formula-binary trees only using addition
#try: FaT(6);
FaT:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({1}):
fi:


gu:={}:

for i from 1 to n-1 do
gu1:=FaT(i):
gu2:=FaT(n-i):

gu:=gu union {seq(seq(["+",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:

od:

gu:

end:


#FaP(n): All the of formula-binary trees only using addition
#in Postfix Format. Try: FaP(6);
FaP:=proc(n) local gu,gu1:
option remember:
gu:=FaT(n):
{seq(TtoP(gu1),gu1 in gu)}:

end:


#Ca(n): The number of formula-binary trees only using addition
#try: Ca(6);
Ca:=proc(n) local i:
option remember:

if n=1 then
 1:
else
add(Ca(i)*Ca(n-i),i=1..n-1):
fi:

end:


#LopFaT(n): All the of formula-binary trees only using addition
#but the first term of an addition is>=the second term
#try: LopFaT(6);
LopFaT:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({1}):
fi:


gu:={}:

for i from 1 to trunc(n/2) do
gu1:=LopFaT(i):
gu2:=LopFaT(n-i):

gu:=gu union {seq(seq(["+",gu2a,gu1a],gu1a in gu1) ,gu2a in gu2)}:

od:

gu:

end:

#LopCa(n): The number of formula-binary trees only using addition
#but where the first term of an addition is >=the second term
#try: Ca(6);
LopCa:=proc(n) local i:
option remember:

if n=1 then
 1:
else
add(LopCa(i)*LopCa(n-i),i=1..trunc(n/2)):
fi:

end:




#RaFaT(n): a uniformly at random formula tree of the pos.
#integer n only using addition. Try:
#RaFaT(10);
RaFaT:=proc(n) local i,gu1,gu2:

if n=1 then
 RETURN(1):
fi:


i:=RollLD([seq(Ca(i)*Ca(n-i),i=1..n-1)]):

gu1:=RaFaT(i):
gu2:=RaFaT(n-i):
["+",gu1,gu2]:

end:


#RaFaP(n): a uniformly at random formula tree of the pos.
#integer n only using addition, Postfix format. Try:
#RaFaP(10);
RaFaP:=proc(n):

TtoP(RaFaT(n)):

end:



#RaLopFaT(n): a uniformly at random formula tree of the pos.
#integer n only using additionm but with a>=b for all additions
#a+b. Try:
#RaLopFaT(10);
RaLopFaT:=proc(n) local i,gu1,gu2:

if n=1 then
 RETURN(1):
fi:


i:=RollLD([seq(LopCa(i)*LopCa(n-i),i=1..trunc(n/2))]):

gu1:=RaLopFaT(n-i):
gu2:=RaLopFaT(i):
["+",gu1,gu2]:

end:



#RaLopFaP(n): a uniformly at random formula tree of the pos.
#integer n only using additionm but with a>=b for all additions
#a+b. In Postfix format.Try:
#RaLopFaP(10);
RaLopFaP:=proc(n) :
TtoP(RaLopFaT(n)):
end:


#LopFaP(n): All the of formula-binary formulas in Postfix
#notation only using addition
#but the first term of an addition is>=the second term
#try: LopFaT(6);
LopFaP:=proc(n) local gu,gu1:
option remember:

gu:=LopFaT(n):

{seq(TtoP(gu1),gu1 in gu)}:

end:

###end only addition


###start addition and muliplication


#FamTa(n): All the of formula-binary trees only using addition
#and multiplication, where the top operation is addition
#try: FamT(6);
FamTa:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({1}):
fi:


gu:={}:

for i from 1 to n-1 do
gu1:=FamT(i):
gu2:=FamT(n-i):

gu:=gu union {seq(seq(["+",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:

od:

gu:

end:


#FamTm(n): All the of formula-binary trees only using addition
#and multiplication, where the top operation is multiplication
#try: FamTm(6);
FamTm:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({}):
fi:


gu:={}:

for i from 2 to trunc(n/2) do

if type(n/i,integer) then
 gu1:=FamT(i):
 gu2:=FamT(n/i):

gu:=gu union {seq(seq(["*",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:
fi:

od:

gu:

end:

#FamT(n): All the of formula-binary trees only using addition
#and multiplication
#try: FamT(6);
FamT:=proc(n) option remember:
FamTa(n) union FamTm(n):
end:



#Cam(n): The number of formula-binary trees only using addition
#and multiplication
#try: Cam(6);
Cam:=proc(n) option remember:
Cama(n) + Camm(n):
end:

#Cama(n): nops(FamTa) 
#try: Cama(6);
Cama:=proc(n) local i:
if n=1 then
 RETURN(1):
else
add(Cam(i)*Cam(n-i),i=1..n-1):
fi:

end:

Camm:=proc(n) local i,gu:
gu:=0:

for  i from 2 to n/2 do

 if type(n/i,integer) then
   gu:=gu+Cam(i)*Cam(n/i):
 fi:

od:

gu:

end:





#RaFamT(n): a uniformly at random formula tree of the pos.
#integer n only using addition and multiplication. Try:
#RaFamT(10);
RaFamT:=proc(n) local i:

if n=1 then
 RETURN(1):
fi:


i:=RollLD([Cama(n),Camm(n)]):

if i=1 then
RaFamTa(n):
 else
RaFamTm(n):
fi:

end:


#RaFamTa(n): a uniformly at random formula tree of the pos.
#integer n only using addition and multiplication with the
#top being plus Try:
#RaFamTa(10);
RaFamTa:=proc(n) local i,L,gu1,gu2:
if n=1 then
 RETURN(1):
fi:


L:=[seq(Cam(i)*Cam(n-i),i=1..n-1)]:

i:=RollLD(L):

gu1:=RaFamT(i):

gu2:=RaFamT(n-i):

["+",gu1,gu2]:


end:



#RaFamTm(n): a uniformly at random formula tree of the pos.
#integer n only using addition and multiplication with the
#top being times. Try:
#RaFamTm(10);
RaFamTm:=proc(n) local i,L,gu1,gu2,lu:
if n=1 then
 RETURN(FAIL):
fi:

if isprime(n) then
 RETURN(FAIL):
fi:

lu:=[]:
L:=[]:
for i from 2 to n/2 do
 if type(n/i, integer) then
  lu:=[op(lu),i]:
  L:=[op(L),Cam(i)*Cam(n/i)]:
 fi:
od:

i:=RollLD(L):

gu1:=RaFamT(lu[i]):

gu2:=RaFamT(n/lu[i]):

["*",gu1,gu2]:


end:


#TtoP(T): converts the formula tree to postfix notation
#try:
#TtoP(["*",["+",1,1],["+",1,1]]);
TtoP:=proc(T) :

if not type(T,list) then
 RETURN(T):
elif nops(T)<>3 then
 RETURN(FAIL):
else
 RETURN([op(TtoP(T[2])),op(TtoP(T[3])),T[1]]):
fi:

end:



#FamP(n): The set of formulas in postfix notation
#of the pos.
#integer n only using addition and multiplication. Try:
#FamP(10);
FamP:=proc(n) local gu,gu1:
gu:=FamT(n):
{seq(TtoP(gu1),gu1 in gu)}:
end:

#RaFamP(n): a uniformly at random formula in postfix notation
#of the pos.
#integer n only using addition and multiplication. Try:
#RaFamP(10);
RaFamP:=proc(n):
TtoP(RaFamT(n)):
end:


#RaFameP(n): a uniformly at random formula in postfix notation
#of the pos.
#integer n using addition, multiplication and exponentiation. Try:
#RaFameP(10);
RaFameP:=proc(n):
TtoP(RaFameT(n)):
end:

###end addition and muliplication


###start addition and muliplication and exponentiation



#FameP(n): The set of formulas in postfix notation
#of the pos.
#integer n only using addition and multiplication. Try:
#FameP(10);
FameP:=proc(n) local gu,gu1:
gu:=FameT(n):
{seq(TtoP(gu1),gu1 in gu)}:
end:


#FameT(n): All the of formula-binary trees only using addition,
#multiplication, and exponentiations
#try: FameT(6);
FameT:=proc(n) option remember:
FameTa(n) union FameTm(n) union FameTe(n):
end:

#FameTa(n): All the of formula-binary trees only using addition,
#multiplication, and exponentiation
#where the top operation is addition
#try: FameTa(6);
FameTa:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({1}):
fi:


gu:={}:

for i from 1 to n-1 do
gu1:=FameT(i):
gu2:=FameT(n-i):

gu:=gu union {seq(seq(["+",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:

od:

gu:

end:


#FameTm(n): All the of formula-binary trees using addition,
#multiplication and exponentiatins, 
#where the top operation is multiplication
#try: FameTm(6);
FameTm:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({}):
fi:


gu:={}:

for i from 2 to trunc(n/2) do

if type(n/i,integer) then
 gu1:=FameT(i):
 gu2:=FameT(n/i):

gu:=gu union {seq(seq(["*",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:
fi:

od:

gu:

end:



#FameTe(n): All the of formula-binary trees using addition,
#multiplication and exponentiatins, 
#where the top operation is exponentiation
#try: FameTe(6);
FameTe:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({}):
fi:

if isprime(n) then 
 RETURN({}):
fi:


gu:={}:

for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then
 gu1:=FameT(root(n,i)):
 gu2:=FameT(i):

gu:=gu union {seq(seq(["^",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:
fi:

od:

gu:

end:


#Came(n): The number of formula-binary trees using addition
#multiplication, and exponentiation
#try: Came(6);
Came:=proc(n) option remember:
Camea(n) + Camem(n)+Camee(n):
end:

#Camea(n): nops(FameTa) 
#try: Camea(6);
Camea:=proc(n) local i:
if n=1 then
 RETURN(1):
else
add(Came(i)*Came(n-i),i=1..n-1):
fi:

end:

Camem:=proc(n) local i,gu:
gu:=0:

for  i from 2 to n/2 do

 if type(n/i,integer) then
   gu:=gu+Came(i)*Came(n/i):
 fi:

od:

gu:

end:


Camee:=proc(n) local i,gu:
gu:=0:


for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then
 gu:=gu+Came(root(n,i))*Came(i)
fi:

od:

gu:

end:




#RaFameT(n): a uniformly at random formula tree of the pos.
#integer n  using addition, multiplication and exponentiation. Try:
#RaFameT(10);
RaFameT:=proc(n) local i:

if n=1 then
 RETURN(1):
fi:


i:=RollLD([Camea(n),Camem(n),Camee(n)]):

if i=1 then
RaFameTa(n):
 elif i=2 then
RaFameTm(n):
else
RaFameTe(n):
fi:

end:


#RaFameTa(n): a uniformly at random formula tree of the pos.
#integer n using addition,multiplication and exponentiation
#with the
#top being plus Try:
#RaFameTa(10);
RaFameTa:=proc(n) local i,L,gu1,gu2:
if n=1 then
 RETURN(1):
fi:


L:=[seq(Came(i)*Came(n-i),i=1..n-1)]:

i:=RollLD(L):

gu1:=RaFameT(i):

gu2:=RaFameT(n-i):

["+",gu1,gu2]:


end:



#RaFameTm(n): a uniformly at random formula tree of the pos.
#integer n only  addition, multiplication and exponentiation
#with the
#top being times. Try:
#RaFameTm(10);
RaFameTm:=proc(n) local i,L,gu1,gu2,lu:
if n=1 then
 RETURN(FAIL):
fi:

if isprime(n) then
 RETURN(FAIL):
fi:

lu:=[]:
L:=[]:
for i from 2 to n/2 do
 if type(n/i, integer) then
  lu:=[op(lu),i]:
  L:=[op(L),Came(i)*Came(n/i)]:
 fi:
od:

i:=RollLD(L):

gu1:=RaFameT(lu[i]):

gu2:=RaFameT(n/lu[i]):

["*",gu1,gu2]:


end:



#RaFameTe(n): a uniformly at random formula tree of the pos.
#integer n only  addition, multiplication and exponentiation
#with the
#top being exponentiation. Try:
#RaFameTe(16);
RaFameTe:=proc(n) local i,L,gu1,gu2,lu:
if n=1 then
 RETURN(FAIL):
fi:

if isprime(n) then
 RETURN(FAIL):
fi:

lu:=[]:
L:=[]:


for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then
  lu:=[op(lu),i]:
 L:=[op(L),Came(root(n,i))*Came(i)]:
fi:

od:

if lu=[] then
 RETURN(FAIL):
fi:

i:=RollLD(L):

gu2:=RaFameT(lu[i]):

gu1:=RaFameT(root(n,lu[i])):

["^",gu1,gu2]:


end:

###end addition and muliplication and exponentiation

#EvalT(T): evaluates the formula tree, try:
#EvalT(FameT(5)[1]);
EvalT:=proc(T):

if not type(T,list) then
  if T<>1 then
    RETURN(FAIL):
  else
   RETURN(1):
 fi:
fi:

if T[1]="+" then
  RETURN(EvalT(T[2])+EvalT(T[3])):
elif T[1]="*" then
  RETURN(EvalT(T[2])*EvalT(T[3])):
elif T[1]="^" then
   RETURN(EvalT(T[2])^EvalT(T[3])):
else
 RETURN(FAIL):
fi:

end:


#EvalP(P): evaluates the formula in postfix notation, try:
#EvalP(FameP(5)[1]);
EvalP:=proc(P) local i:

if not type(P,list) then
 RETURN(P):
fi:

if type(P,list) and nops(P)=1 then
 RETURN(P[1]):
fi:

for i from 1 to nops(P) while type(P[i],integer) do od:

if P[i]="+" then
 RETURN(EvalP([op(1..i-3,P),P[i-2]+P[i-1],op(i+1..nops(P),P)])):
elif P[i]="*" then
 RETURN(EvalP([op(1..i-3,P),P[i-2]*P[i-1],op(i+1..nops(P),P)])):
elif P[i]="^" then
 RETURN(EvalP([op(1..i-3,P),P[i-2]^P[i-1],op(i+1..nops(P),P)])):
else
 RETURN(FAIL):
fi:

end:


#Omek(T): the depth of the formula-tree T
Omek:=proc(T):

if not type(T,list) then
RETURN(0):
else
 1+ max(Omek(T[2]),Omek(T[3])):
fi:

end:

#Stra(T): the depth of the formula-tree T
Stra:=proc(T):

if not type(T,list) then
RETURN(0):
elif Stra(T[2])=Stra(T[3]) then
  1+ Stra(T[2]):
else
 max(Stra(T[2]),Stra(T[3])):

fi:

end:

 


#ShortestTam(n): 
#the length of the shortest expression, followed by one of them evaluating
#to n only using addition and multiplication. Try:
#ShortestTam(10);
ShortestTamOld:=proc(n) local T1,T2,aluf,si,i:
option remember:

if n=1 then
 RETURN(1,1):
fi:


aluf:=0:
si:=2*n:

for i from 1 to n-1 do
 T1:=ShortestTamOld(i):
 T2:=ShortestTamOld(n-i):
  if T1[1]+T2[1]+1<si then
       si:=T1[1]+T2[1]+1:
     aluf:=["+",T1[2],T2[2]]:
  fi:

od:

for  i from 2 to n/2 do

 if type(n/i,integer) then
  T1:=ShortestTam(i):
  T2:=ShortestTam(n/i):

    if T1[1]+T2[1]+1<si then
    si:=T1[1]+T2[1]+1:
     aluf:=["+",T1[2],T2[2]]:
    fi:
 fi:

od:

si, aluf:

end:



#ShortestPam(n): A shortest expression evaluating
#to n only using addition and multiplication. 
#in postfix notation
#Try:
#ShortestTam(10);
ShortestPam:=proc(n) local gu,lu:
gu:=ShortestTam(n):
lu:=TtoP(gu[2]):
if nops(lu)<>gu[1] then
 RETURN(FAIL):
fi:
gu[1],lu:

end:



#ShortestTam(n): 
#the length of the shortest expression, followed by one of them evaluating
#to n only using addition and multiplication. Try:
#ShortestTam(10);
ShortestTam:=proc(n) local T1,T2,aluf,si,i:
option remember:

if n=1 then
 RETURN(1,1):
fi:


aluf:=0:
si:=2*n:

for i from 1 to n-1 do
 T1:=ShortestTam(i):
 T2:=ShortestTam(n-i):
  if T1[1]+T2[1]+1<si then
       si:=T1[1]+T2[1]+1:
    if EvalT(T1[2])<=EvalT(T2[2]) then
     aluf:=["+",T1[2],T2[2]]:
      else
       aluf:=["+",T2[2],T1[2]]:
  fi:
  fi:
od:

for  i from 2 to n/2 do

 if type(n/i,integer) then
  T1:=ShortestTam(i):
  T2:=ShortestTam(n/i):

    if T1[1]+T2[1]+1<si then
    si:=T1[1]+T2[1]+1:
    if EvalT(T1[2])<= EvalT(T2[2]) then
     aluf:=["*",T1[2],T2[2]]:
      else
       aluf:=["*",T2[2],T1[2]]:
    fi:


    fi:
 fi:

od:

si, aluf:

end:




#ShortestTame(n): 
#the length of the shortest expression, followed by one of them evaluating
#to n using addition, multiplication and exponentiation. Try:
#ShortestTame(10);
ShortestTame:=proc(n) local T1,T2,aluf,si,i:
option remember:

if n=1 then
 RETURN(1,1):
fi:


aluf:=0:
si:=2*n:

for i from 1 to n-1 do
 T1:=ShortestTame(i):
 T2:=ShortestTame(n-i):
  if T1[1]+T2[1]+1<si then
       si:=T1[1]+T2[1]+1:
    if EvalT(T1[2])<=EvalT(T2[2]) then
     aluf:=["+",T1[2],T2[2]]:
      else
       aluf:=["+",T2[2],T1[2]]:
  fi:
  fi:
od:

for  i from 2 to n/2 do

 if type(n/i,integer) then
  T1:=ShortestTame(i):
  T2:=ShortestTame(n/i):

    if T1[1]+T2[1]+1<si then
    si:=T1[1]+T2[1]+1:
    if EvalT(T1[2])<= EvalT(T2[2]) then
     aluf:=["*",T1[2],T2[2]]:
      else
       aluf:=["*",T2[2],T1[2]]:
    fi:


    fi:
 fi:

od:



for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then


 T1:=ShortestTame(root(n,i)):
 T2:=ShortestTame(i):


    if T1[1]+T2[1]+1<si then
    si:=T1[1]+T2[1]+1:
     aluf:=["^",T1[2],T2[2]]:

    fi:
fi:

od:

si, aluf:

end:



#ShortestPame(n): 
#the length of the shortest expression, followed by one of them evaluating
#to n using addition, multiplication and exponentiation. 
#In postfix notation.
#Try:
#ShortestPame(10);
ShortestPame:=proc(n) local gu,lu:
gu:=ShortestTame(n):
lu:=TtoP(gu[2]):
if nops(lu)<>gu[1] then
 RETURN(FAIL):
fi:
gu[1],lu:
end:



#CaSeq(n): The sequence for the
#number of formula-binary trees only using addition
#try: CaSeq(6);
CaSeq:=proc(n) local i:
[seq(Ca(i),i=1..n)]:
end:


#CamSeq(n): The sequence for the
#number of formula-binary trees only using addition
#and multiplication
#try: CamSeq(6);
CamSeq:=proc(n) local i:
[seq(Cam(i),i=1..n)]:
end:

#CameSeq(n): The sequence for the
#number of formula-binary trees using addition,
#multiplication, and exponentiation
#try: CameSeq(6);
CameSeq:=proc(n) local i:
[seq(Came(i),i=1..n)]:
end:

#ShortestFamSeq(N): the sequence whose n-th entry, from
#1 to N is the length of the shortest formula, only using
#addition and multiplication that evaluate to n,
#Try:
#ShortestFamSeq(30);
ShortestFamSeq:=proc(N) local n:
[seq(ShortestTam(n)[1],n=1..N)]:
end:

#ShortestFam21Seq(N): the sequence whose n-th entry, from
#1 to N is the length of the shortest formula, only using
#addition and multiplication and the inputs being 1 or 2
#that evaluate to n,
#Try:
#ShortestFam21Seq(30);
ShortestFam21Seq:=proc(N) local n:
[seq(ShortestTam21(n)[1],n=1..N)]:
end:


#ShortestFameSeq(N): the sequence whose n-th entry, from
#1 to N is the length of the shortest formula, only 
#addition and multiplication and exponentiation that evaluate to n,
#Try:
#ShortestFameSeq(30);
ShortestFameSeq:=proc(N) local n:
[seq(ShortestTame(n)[1],n=1..N)]:
end:

#ShortestFaeSeq(N): the sequence whose n-th entry, from
#1 to N is the length of the shortest formula, only 
#addition and multiplication and exponentiation that evaluate to n,
#Try:
#ShortestFaeSeq(30);
ShortestFaeSeq:=proc(N) local n:
[seq(ShortestTae(n)[1],n=1..N)]:
end:





#GFam(n,x,a,m): The weight-enumerator of the set of
#of formula-binary trees only using addition
#and multiplication, where the weight of a formula is
#x^(length)*a^(#pluses)*m^(#times)
#try: GFam(6,x,a,m);
GFam:=proc(n,x,a,m) option remember:
GFama(n,x,a,m) + GFamm(n,x,a,m):
end:


#GFama(n,x,a,m): 
#try: GFama(6,x,a,m);
GFama:=proc(n,x,a,m) local i:
if n=1 then
 RETURN(x):
else
expand(add(x*a*GFam(i,x,a,m)*GFam(n-i,x,a,m),i=1..n-1)):
fi:

end:


GFamm:=proc(n,x,a,m) local i,gu:
gu:=0:

for  i from 2 to n/2 do

 if type(n/i,integer) then
   gu:=expand(gu+x*m*GFam(i,x,a,m)*GFam(n/i,x,a,m)):
 fi:

od:

gu:

end:


#Mishkal(P,x,a,m,e): the weight of the formula P in postfix notation
#x^(nops(P))*a^(#pluses)*m^(#times)*e^(#^)
#try:
#Mishkal([1,1,"+"],x,a,m,e);
Mishkal:=proc(P,x,a,m,e) local gu,i:

if P=1 then
 RETURN(x):
fi:

gu:=1:

for i from 1 to nops(P) do
 if P[i]=1 then
   gu:=gu*x:
 elif P[i]="+" then
    gu:=gu*a*x:
 elif P[i]="*" then
    gu:=gu*m*x:
 elif P[i]="^" then
    gu:=gu*e*x:
 else
  RETURN(FAIL):
 fi:
od:

gu:

end:




#CheckGFam(n): checks procedure GFam(n,x,a,m) by
#doing it by brute force up to FamP(n).
#Try: CheckGFam(6);
CheckGFam:=proc(n) local x,a,m,e,gu1,n1:

evalb(
{seq(expand(add(Mishkal(gu1,x,a,m,e),gu1 in FamP(n1))-GFam(n1,x,a,m)),
n1=1..n)}={0}):

end:



#GFame(n,x,a,m,e): The weight-enumerator of the set of
#of formula-binary trees using addition,
#multiplication and exponetiation, where the weight of a formula is
#x^(length)*a^(#pluses)*m^(#times)*e^(#^)
#try: GFame(6,x,a,m,e);
GFame:=proc(n,x,a,m,e) option remember:
GFamea(n,x,a,m,e) + GFamem(n,x,a,m,e)+ GFamee(n,x,a,m,e):
end:


#GFamea(n,x,a,m,e): 
#try: GFamae(6,x,a,m,e);
GFamea:=proc(n,x,a,m,e) local i:
if n=1 then
 RETURN(x):
else
expand(add(x*a*GFame(i,x,a,m,e)*GFame(n-i,x,a,m,e),i=1..n-1)):
fi:

end:


GFamem:=proc(n,x,a,m,e) local i,gu:
gu:=0:

for  i from 2 to n/2 do

 if type(n/i,integer) then
   gu:=expand(gu+x*m*GFame(i,x,a,m,e)*GFame(n/i,x,a,m,e)):
 fi:

od:

gu:

end:



GFamee:=proc(n,x,a,m,e) local i,gu:
gu:=0:


for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then
 gu:=expand(gu+x*e*GFame(root(n,i),x,a,m,e)*GFame(i,x,a,m,e)):
fi:

od:

gu:

end:

#CheckGFame(n): checks procedure GFame(n,x,a,m) by
#doing it by brute force up to FameP(n).
#Try: CheckGFame(6);
CheckGFame:=proc(n) local x,a,m,e,gu1,n1:

evalb(
{seq(
expand(add(Mishkal(gu1,x,a,m,e),gu1 in FameP(n1))-GFame(n1,x,a,m,e)),
n1=1..n)}={0}
):

end:




#SeferAM(K1,K2): inputs  positive integers K1 and K2 and outputs
#a webbook about formuals representing integers up to K2
#using addition and multiplication
#it also gives the enumerating sequence for the number of formulas
#up to K1 terms
#Try
#SeferAM(30,100):
SeferAM:=proc(K1,K2) local gu,mu,lu,n1,n,t0,fu,KA,C:
t0:=time():
print(`Everything About Formulas Representing Integers Using`):
print(`Additions and Multiplication for integers from 1 to`, K2):
print(``):
print(` By Shalosh B. Ekhad `):
print(``):
print(`using the method described in Edinah Gnang and Doron Zeilberger's`):
print(`article:`):
print(`Zeroless Arithmetic: Representing Integers ONLY Using ONE`):
print(``):
mu:=CamSeq(K2):

print(`The sequence enumerating the number of formula representations`):
print(`of the positive integers for n from 1 to`, K1):
print(`Using ADDITION and  MULTIPLICATION is:`):
print(``):
lprint(CamSeq(K1)):
print(``):
print(`Here is the sequence of minimal lengths of  formulas representing`):
print(`n only using addition and multiplication for n from 1 to`, K2):
gu:=ShortestFamSeq(K2):
print(gu):
print(``):
print(`Finally, for each n from 1 to`, K2, `here are the minimal lengths`):
print(`again, followed by ONE of the minimal formuals (in postfix)`):

for n1 from 1 to K2 do 
lu:=ShortestTam(n1):
lu:=lu[1],TtoP(MinMemory(lu[2])):
print(`n=`, n1,`length=`, lu[1], `formula=`, cat(op(lu[2]))):
print(``):
od:

Digits:=100:
lu:=Zinn(mu):
if abs(lu[1]+3/2)<1/100 then
print(`Finally the enumerating sequence  seems to be asymptotically`):
fu:=[seq(mu[n1]/(n1^(-3/2)*evalf(lu[2],4)^n1),n1=K2-20..K2)]:

KA:=fu[nops(fu)]:
 if abs(evalf(KA-fu[1]))<1/10^4 then:
    KA:=evalf(KA,3):
    lprint(KA*n^(-3/2)*evalf(lu[2],4)^n):
 else
     lprint(C*n^(-3/2)*evalf(lu[2],4)^n):
   print(`for some constant C`):
fi:

fi:

print(`This concludes this fascinating article that took`):
print(time()-t0 , `seconds to generate. `):
end:







#SeferAME(K1,K2): inputs  positive integers K1 and K2 and outputs
#a webbook about formuals representing integers up to K2
#using addition, multiplication, and exponentiations
#it also gives the enumerating sequence for the number of formulas
#up to K1 terms
#Try
#SeferAME(30,100):
SeferAME:=proc(K1,K2) local gu,mu,lu,n1,n,t0,lu1,lu2,fu,KA,C:
t0:=time():
print(`Everything About Formulas Representing Integers Using`):
print(`Additions, Multiplcation and Exponentiation for integers from 1 to`, K2):
print(``):
print(` By Shalosh B. Ekhad `):
print(``):
print(`using the method described in Edinah Gnang and Doron Zeilberger's`):
print(`article:`):
print(`Zeroless Arithmetic: Representing Integers ONLY Using ONE`):
print(``):
mu:=CameSeq(K2):

print(`The sequence enumerating the number of formula representations`):
print(`of the positive integers for n from 1 to`, K1):
print(`Using ADDITION, MULTIPLICATION and EXPONENTIATION, is:`):
print(``):
lprint(CameSeq(K1)):
print(``):
print(`Here is the sequence of minimal lengths of  formulas representing`):
print(`n only using addition, multiplication, and exponentiaton for n from 1 to`, K2):
gu:=ShortestFameSeq(K2):
print(gu):
print(``):
print(`Finally, for each n from 1 to`, K2, `here are the minimal lengths`):
print(`again, followed by ONE of the minimal formuals (in postfix)`):
print(`followed by the First and Second Canonical Forms `):

for n1 from 1 to K2 do 
lu:=ShortestTame(n1):
lu:=lu[1],TtoP(MinMemory(lu[2])):
lu1:=TtoP(FCF(n1)):
lu2:=TtoP(SCF(n1)):
print(`n=`, n1):

if lu[1]=nops(lu1) and lu[1]=nops(lu2) then
print(`shortest formula=`, cat(op(lu1)), `length=`, lu[1]):
print(`FCF: `,cat(op(lu1)),`length=`, nops(lu1), `(shortest!)`):
print(`SCF: `,cat(op(lu2)),`length=`, nops(lu2), `(also shortest!)`):
print(``):

elif lu[1]=nops(lu1) then
print(`shortest formula=`, cat(op(lu1)), `length=`, lu[1]):
print(`FCF: `,cat(op(lu1)),`length=`, nops(lu1), `(shortest!)`):
print(`SCF: `,cat(op(lu2)),`length=`, nops(lu2)):
print(``):

elif lu[1]=nops(lu2) then
print(`shortest formula=`, cat(op(lu2)), `length=`, lu[1]):
print(`FCF: `,cat(op(lu1)),`length=`, nops(lu1)):
print(`SCF: `,cat(op(lu2)),`length=`, nops(lu2), `(shortest!)`):

else
print(`shortest formula=`, cat(op(lu2)), `length=`, lu[1]):
print(`FCF: `,cat(op(lu1)),`length=`, nops(lu1)):
print(`SCF: `,cat(op(lu2)),`length=`, nops(lu2)):

fi:
od:

Digits:=100:
lu:=Zinn(mu):
if abs(lu[1]+3/2)<1/100 then
print(`Finally the enumerating sequence  seems to be asymptotically`):
fu:=[seq(mu[n1]/(n1^(-3/2)*evalf(lu[2],4)^n1),n1=K2-20..K2)]:
KA:=fu[nops(fu)]:
 if abs(evalf(KA-fu[1]))<1/10^4 then:
    KA:=evalf(KA,3):
    lprint(KA*n^(-3/2)*evalf(lu[2],4)^n):
 else
   lprint(C*n^(-3/2)*evalf(lu[2],4)^n):
   print(`for some constant C`):
fi:

fi:

print(`This concludes this fascinating article that took`):
print(time()-t0 , `seconds to generate. `):
end:



#FCF(n): the First Canonical Form based on Goodstein encoding
#Try:
#FCF(10);
FCF:=proc(n) local k,n1:
option remember:
 if n=1 then
   RETURN(1):
 fi:

if n=2 then
 RETURN(["+",1,1]):
fi:

if n=3 then
 RETURN(["+",["+",1,1],1]):
fi:

for k from 1 while 2^k<=n do od:

k:=k-1:

n1:=n-2^k:

if n1=0 then
 RETURN(["^",["+",1,1],FCF(k)]):
else
 RETURN(["+",["^",["+",1,1],FCF(k)],FCF(n1)] ):
fi:

end:




#SCF(n): the Second Canonical Form based on Gnang encoding
#(using iterated Fundamental Theorem of Arithmetics)
#Try:
#SCF(10);
SCF:=proc(n) local gu,gu1,p,a,n1,n2:
option remember:
 if n=1 then
   RETURN(1):
 fi:

if n=2 then
 RETURN(["+",1,1]):
fi:

if n=3 then
 RETURN(["+",["+",1,1],1]):
fi:

if isprime(n) then
  RETURN(["+",1,SCF(n-1)]):
fi:

gu:=ifactor(n):

if type(gu,`^`) then
 p:=op(1,op(1,gu)):
 a:=op(2,gu):
 RETURN(["^", ["+",1,SCF(p-1)],SCF(a)]):
fi:

gu1:=op(1,gu);

if type(gu1,`^`) then
n1:=op(1,op(1,gu1))^op(2,gu1):
n2:=n/n1:
 RETURN(["*", SCF(n1),SCF(n2)]):
else
n1:=op(1,gu1):
n2:=n/n1:
 RETURN(["*", SCF(n1),SCF(n2)]):
fi:



end:


#ShortestTam21(n): 
#the length of the shortest expression, followed by one of them evaluating
#to n using addition and multiplication
#and allowing both 1 and 2 as inputs Try:
#ShortestTam21(10);
ShortestTam21:=proc(n) local T1,T2,aluf,si,i:
option remember:

if n=1 then
 RETURN(1,1):
fi:


if n=2 then
 RETURN(1,2):
fi:

aluf:=0:
si:=2*n:

for i from 1 to n-1 do
 T1:=ShortestTam21(i):
 T2:=ShortestTam21(n-i):
  if T1[1]+T2[1]+1<si then
       si:=T1[1]+T2[1]+1:
     aluf:=["+",T1[2],T2[2]]:
 fi:
od:

for  i from 2 to n/2 do

 if type(n/i,integer) then
  T1:=ShortestTam21(i):
  T2:=ShortestTam21(n/i):

    if T1[1]+T2[1]+1<si then
    si:=T1[1]+T2[1]+1:
     aluf:=["*",T1[2],T2[2]]:
    fi:
 fi:



od:




si, aluf:

end:





#MinMemory(T): given a formula-tree finds an equivalent
#form such that the Strahler number of the left-child
#is always >=0 to that of the right child for any node
#in case of ties, the left-child should evaluate to a larger
#number than the right child, and in case of ties again,
#we pick at random
MinMemory:=proc(T) local T1,T2:

if T=1 then
 RETURN(1):
fi:

T1:=T[2]:
T2:=T[3]:

if Stra(T1)>Stra(T2) then
  RETURN([T[1],MinMemory(T1),MinMemory(T2)]):
elif Stra(T1)<Stra(T2) then
  RETURN([T[1],MinMemory(T2),MinMemory(T1)]):
else
   if EvalT(T1)>EvalT(T2) then
      RETURN([T[1],MinMemory(T1),MinMemory(T2)]):
   else
    RETURN([T[1],MinMemory(T2),MinMemory(T1)]):
   fi:
fi:

end:


   


###start addition and exponentiation


#FaeP(n): The set of formulas in postfix notation
#of the pos.
#integer n only using addition and exponentation. Try:
#FaeP(10);
FaeP:=proc(n) local gu,gu1:
gu:=FaeT(n):
{seq(TtoP(gu1),gu1 in gu)}:
end:


#FaeT(n): All the of formula-binary trees only using addition,
# and exponentiations
#try: FaeT(6);
FaeT:=proc(n) option remember:
FaeTa(n)  union FaeTe(n):
end:

#FaeTa(n): All the of formula-binary trees only using addition,
#and exponentiation
#where the top operation is addition
#try: FaeTa(6);
FaeTa:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({1}):
fi:


gu:={}:

for i from 1 to n-1 do
gu1:=FaeT(i):
gu2:=FaeT(n-i):

gu:=gu union {seq(seq(["+",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:

od:

gu:

end:

#FaeTe(n): All the of formula-binary trees using addition
#and exponentiatins, 
#where the top operation is exponentiation
#try: FaeTe(6);
FaeTe:=proc(n) local i,gu,gu1,gu2,gu1a,gu2a:
option remember:

if n=1 then 
 RETURN({}):
fi:

if isprime(n) then 
 RETURN({}):
fi:


gu:={}:

for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then
 gu1:=FaeT(root(n,i)):
 gu2:=FaeT(i):

gu:=gu union {seq(seq(["^",gu1a,gu2a],gu1a in gu1) ,gu2a in gu2)}:
fi:

od:

gu:

end:


#CaeSeq(n): The sequence for the
#number of formula-binary trees using addition,
#multiplication, and exponentiation
#try: CaeSeq(6);
CaeSeq:=proc(n) local i:
[seq(Cae(i),i=1..n)]:
end:

#Cae(n): The number of formula-binary trees using addition
#and exponentiation
#try: Cae(6);
Cae:=proc(n) option remember:
Caea(n) + Caee(n):
end:

#Caea(n): nops(FaeTa) 
#try: Caea(6);
Caea:=proc(n) local i:
if n=1 then
 RETURN(1):
else
add(Cae(i)*Cae(n-i),i=1..n-1):
fi:

end:


Caee:=proc(n) local i,gu:
gu:=0:


for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then
 gu:=gu+Cae(root(n,i))*Cae(i)
fi:

od:

gu:

end:




#RaFaeT(n): a uniformly at random formula tree of the pos.
#integer n  using addition and exponentiation. Try:
#RaFaeT(10);
RaFaeT:=proc(n) local i:

if n=1 then
 RETURN(1):
fi:


i:=RollLD([Caea(n),Caee(n)]):

if i=1 then
RaFaeTa(n):
else
RaFaeTe(n):
fi:

end:


#RaFaeP(n): a uniformly at random formula in postfix notation
#of the pos.
#integer n using addition and exponentiation. Try:
#RaFaeP(10);
RaFaeP:=proc(n):
TtoP(RaFaeT(n)):
end:

#RaFaeTa(n): a uniformly at random formula tree of the pos.
#integer n using addition and exponentiation
#with the
#top being plus Try:
#RaFaeTa(10);
RaFaeTa:=proc(n) local i,L,gu1,gu2:
if n=1 then
 RETURN(1):
fi:


L:=[seq(Cae(i)*Cae(n-i),i=1..n-1)]:

i:=RollLD(L):

gu1:=RaFaeT(i):

gu2:=RaFaeT(n-i):

["+",gu1,gu2]:


end:


#RaFaeTe(n): a uniformly at random formula tree of the pos.
#integer n only  addition and exponentiation
#with the
#top being exponentiation. Try:
#RaFaeTe(16);
RaFaeTe:=proc(n) local i,L,gu1,gu2,lu:
if n=1 then
 RETURN(FAIL):
fi:

if isprime(n) then
 RETURN(FAIL):
fi:

lu:=[]:
L:=[]:


for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then
  lu:=[op(lu),i]:
 L:=[op(L),Cae(root(n,i))*Cae(i)]:
fi:

od:

if lu=[] then
 RETURN(FAIL):
fi:

i:=RollLD(L):

gu2:=RaFaeT(lu[i]):

gu1:=RaFaeT(root(n,lu[i])):

["^",gu1,gu2]:


end:



#ShortestTae(n): 
#the length of the shortest expression, followed by one of them evaluating
#to n using addition and exponentiation. Try:
#ShortestTae(10);
ShortestTae:=proc(n) local T1,T2,aluf,si,i:
option remember:

if n=1 then
 RETURN(1,1):
fi:


aluf:=0:
si:=2*n:

for i from 1 to n-1 do
 T1:=ShortestTae(i):
 T2:=ShortestTae(n-i):
  if T1[1]+T2[1]+1<si then
       si:=T1[1]+T2[1]+1:
    if EvalT(T1[2])<=EvalT(T2[2]) then
     aluf:=["+",T1[2],T2[2]]:
      else
       aluf:=["+",T2[2],T1[2]]:
  fi:
  fi:
od:


for i from 2 to trunc(log(n)/log(2))+1 do

if type(root(n,i),integer) then


 T1:=ShortestTae(root(n,i)):
 T2:=ShortestTae(i):


    if T1[1]+T2[1]+1<si then
    si:=T1[1]+T2[1]+1:
     aluf:=["^",T1[2],T2[2]]:

    fi:
fi:

od:

si, aluf:

end:


#ShortestPae(n): 
#the length of the shortest expression, followed by one of them evaluating
#to n using multiplication and exponentiation. 
#In postfix notation.
#Try:
#ShortestPae(10);
ShortestPae:=proc(n) local gu,lu:
gu:=ShortestTae(n):
lu:=TtoP(gu[2]):
if nops(lu)<>gu[1] then
 RETURN(FAIL):
fi:
gu[1],lu:
end:


#SeferAE(K1,K2): inputs  positive integers K1 and K2 and outputs
#a webbook about formuals representing integers up to K2
#using addition and exponentiations
#it also gives the enumerating sequence for the number of formulas
#up to K1 terms
#Try
#SeferAE(30,100):
SeferAE:=proc(K1,K2) local gu,mu,lu,n1,n,t0,lu1,fu,KA,C:
t0:=time():
print(`Everything About Formulas Representing Integers Using`):
print(`Additions and Exponentiation for integers from 1 to`, K2):
print(``):
print(` By Shalosh B. Ekhad `):
print(``):
print(`using the method described in Edinah Gnang and Doron Zeilberger's`):
print(`article:`):
print(`Zeroless Arithmetic: Representing Integers ONLY Using ONE`):
print(``):
mu:=CaeSeq(K2):

print(`The sequence enumerating the number of formula representations`):
print(`of the positive integers for n from 1 to`, K1):
print(`Using ADDITION and EXPONENTIATION, is:`):
print(``):
lprint(CaeSeq(K1)):
print(``):
print(`Here is the sequence of minimal lengths of  formulas representing`):
print(`n only using addition, multiplication, and exponentiaton for n from 1 to`, K2):
gu:=ShortestFaeSeq(K2):
print(gu):
print(``):
print(`Finally, for each n from 1 to`, K2, `here are the minimal lengths`):
print(`again, followed by ONE of the minimal formuals (in postfix)`):
print(`followed by the First and Second Canonical Forms `):

for n1 from 1 to K2 do 
lu:=ShortestTae(n1):
lu:=lu[1],TtoP(MinMemory(lu[2])):
lu1:=TtoP(FCF(n1)):
print(`n=`, n1):

if lu[1]=nops(lu1) then
print(`shortest formula=`, cat(op(lu1)), `length=`, lu[1]):
print(`FCF: `,cat(op(lu1)),`length=`, nops(lu1), `(shortest!)`):
print(``):

else
print(`shortest formula=`, cat(op(lu[2])),`length=`, lu[1]):
print(`FCF: `,cat(op(lu1)),`length=`, nops(lu1)):

fi:
od:

Digits:=100:
lu:=Zinn(mu):
if abs(lu[1]+3/2)<1/100 then
print(`Finally the enumerating sequence  seems to be asymptotically`):
fu:=[seq(mu[n1]/(n1^(-3/2)*evalf(lu[2],4)^n1),n1=K2-20..K2)]:
KA:=fu[nops(fu)]:
 if abs(evalf(KA-fu[1]))<1/10^4 then:
    KA:=evalf(KA,3):
    lprint(KA*n^(-3/2)*evalf(lu[2],4)^n):
 else
   lprint(C*n^(-3/2)*evalf(lu[2],4)^n):
   print(`for some constant C`):
fi:

fi:

print(`This concludes this fascinating article that took`):
print(time()-t0 , `seconds to generate. `):
end:

###end addition and  exponentiation