Generating Functions - Closed Forms vs Open Forms
by
Huen Y.K.
CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~huens/
email: huens@mbox3.singnet.com.sg
(A short communication - 1st released: 1/10/97 )
Abstract
Every sequence algebraic function in closed form has an equivalent open form which is
computationally efficient. Series expansions of closed form is resource intensive and tend
to reach numerical saturation at low upper limits. With open forms the upper limits
can be greatly extended. This paper gives a summary of important formulations in closed and
open forms [1 to 5]. The accuracy of the open form of Oddcomp(z) is calibrated against the closed
form as a standard reference. It also gives a general method of translating closed forms to
open forms. This does not mean that we can do away with closed forms since these are
still required in algebaric manipulations of generating functions. However, the availability of
open forms means that one could carry out big integer computations in a PC using an
algebraic package. One is still not able to perform multiprecision floating point arithmetic in
symbolic softwares but that is another story.
1. Introduction
A sequence algebraic generating function is defined as a closed form if the expression can
be reduced to the general canonical form given by equation (1):
upperbound
-----
. \ ........ 1
.. ) ------------------- ............................................(1).
. / ......f1(i)...f2(i)
----- z......(z.... - 1)
i = lowerbound
All sequence algebraic generating functions described so far in this series of papers can be
reduced to the above form by imposing specific conditions on f1(i) and f2(i) and the summation
limits on i. f1(i) and f2(i) are integer functions which can be nonlinear. Here we give some well known examples in both closed and open forms.
(i) Nat(z): f1(i) = 0, f2(i) = 1.
Closed form:
................. z
Nat(z) := ----- ....................................................(2a).
............... z - 1
Open form:
upperbound
-----
. \...........1
.. ).....-------- ......................................................(2b)
. / ............ i
----- ......z
i = 0
(ii) Odd(z): f1(i)=0, f2(i)=2.
Closed form:
.................. z
Odd(z) := ------- .................................................(3a).
................... 2
................. z - 1
Open form:
upperbound
-----
. \ ................1
.. ).........------------ .................................................(3b).
. / ..................(2 i+1)
----- ............z
i = 0
(iii) Even(z): f1(i)=0, f2(i)=2.
Closed form:
................... 2
................. z
Even(z) := ------- .................................................(4a).
................... 2
................ z... - 1
Open form:
upperbound
-----
. \ ..................1
.. )...........------------ .................................................(4b).
. /......................(2i)
----- ...............z
i = 0
(iv) Comp(z): f1(i) = f2(i) = i.
Closed form:
upperbound
-----
. \...................1
.. )..........----------- ................................................(5a).
. /.................i.....i
----- ..........z...(z.. - 1)
i = 2
Open form:
upperbound2./..upperbound1.................\
----- .............|...-----................................|
. \ ..................|....\.................1..................|
.. )..................|.....)....... ------------------| .........................(5b).
. /...................|..../..............(i + i j)............|
-----..............|...----- .......z......................|
j = 1...............\...i = 2............................../
(v) Oddcomp(z): f1(i)=2*i+1, f2(i)=4*i+2.
Closed form:
upperbound
-----
. \ ....................1
.. ) --------------------------- .........................................(6a).
. /.............(2 i + 1)...(4 i + 2)
----- .....z............(z.............- 1)
i = 2
Open form: Not that the index sums to z are always odd to give odd composite integers.
upperbound2../upperbound1...................................\
----- .............|...-----................................................|
. \..................|....\....................1................................|
.. ).................|.....)......----------------------------.....| ...................(6b).
. /..................|..../............(2 i + 1 + j (4 i + 2))...........|
-----..............|...----- ....z.........................................|
j = 1..............\ i = 1................................................./
A general translation algorithm can be formulated as shown in equation (7) which translates
closed forms to the open forms and vice versa such as shown from equations (1) to (6b).
Note that single summations in some more complicated closed forms are translated into
double
summations in the open forms. This is because series expansions of an individual Z/i layer
is translated into a separate summation.
upperbound2../upperbound1..............................\
-----..............|...-----...........................................|
. \..................|....\.....................1..........................|
.. ).................|.....)......------------------------.....| ...................(7).
. /..................|..../..............f1(i)......j * f2(i)...........|
-----..............|...-----........z.........z.......................|
j = 1..............\ i = 1............................................/
2. Open Form vs Closed Form of Oddcomp(z)
The closed form is, by definition, always taken as the standard reference by which the open
form is to be calibrated. There is in fact no proof that the closed form is more accurate than
the open form. In fact, the author speculates that both forms are equally accurate but in the
closed form, one is able to specify exactly the number of terms to be generated whereas this
cannot be done in the open form. The closed forms are more suitable for use in algebraic
manipulations of sequences in generating functions whereas the open forms are more
efficient in numerical computations. The procedures of calibration can be applied to other
formulations but for page economy, only one example is described here.
In this section we calibrate the numerical accuracy of the open form of Oddcomp(z) given by
equation (6b) by its corresponding closed form given by equation (6a). The experiments
show that in order for the open form to generate the same number of correct terms without
misses, its upperbound for i should be set to at least one-fifth of that of the closed form.
The results are summarised in Table 1. The reason for is due to the different ways by which
f1(i) and f2(i) are defined in Oddcomp(z) and is not indicative that the open form has
greater predictive power.
Table 1 -- Calibration Of Comp(z): Open Form vs Closed Form
Equation (6a) versus Equation (6b).
100 terms are to be generated by both the closed form and the open form
of Oddcomp(z) using Maple V R 3's syntax. It is noted that the open form
could match the closed form when the range of i is set to 1/5 that of the
closed form.
======================================================
Closed form: sort(series(sum(1/(z^(2*i+1)*(z^(4*i+2)-1)),i=1..100),z=infinity,100));
9 15 21 25 27 33 35 39 45 49 51 55 57 63 65
69 75 77 81 85 87 91 93 95 99 ..................
Open form: sort(sum(sum(1/(z^(2*i+1)*z^((4*i+2)*j)),i=1..20),j=1..20));
9 15 21 25 27 33 35 39 45 49 51 55 57 63 65
69 75 77 81 85 87 91 93 95 99 ......................
=======================================================
Table 2 -- Calibration Of The Numerator Coefficient Of Open Form vs Closed Form In Oddcomp(z).
=======================================================
Closed form: sort(series(sum(1/(z^(2*i+1)*(z^(4*i+2)-1)),i=1..200),z=infinity,200));
Comments: Both closed form and open form generate exactly identical
sequence including complete agreement on the numerator coefficients.
Using the rule found in Table 1, the upper limit for i for the open form is set to i = 1..40
which is 1/5 that
of the limits for the closed form.
......1..........1.......2.......2......1........2......2......2......2.......4.......1.......2.......2.......2......4......2
O(----) + ---- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + ---
......201........9......15......21....25....27....33.....35.....39.....45.....49.....51.....55....57....63....65
.....z...........z.......z........z.......z.......z.......z.......z........z.......z.......z........z.......z.......z......z.......z
....2.......4.......2.......3.......2.......2.......2.......2.......2......4.......6........2.......2........4.........2
+ --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + ---- + ---- + ---- + ---- + ----
.....69.....75.....77.....81....85.....87.....91......93.....95.....99....105....111....115....117....119
....z........z.......z.......z.......z........z.......z........z........z........z........z........z........z........z.........z
.....1........2........2........2.........2........6........2........2........2.........4........4........2.......2
+ ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ----
.....121....123....125....129.....133....135....141....143....145.....147....153....155....159
....z.........z........z.........z.........z.........z.........z.........z.........z.........z.........z.........z.......z
.....2.........6.......1........4........4........2.........2........2.........2.........6........6
+ ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ----
......161.....165....169....171....175....177....183....185....187....189....195
.....z.........z........z.........z.........z........z.........z.........z........z.........z.........z
Open form: sort(sum(sum(1/(z^(2*i+1)*z^((4*i+2)*j)),i=1..40),j=1..40));
...1......2......2.......1.......2.......2.......2.......2......4.......1.......2......2........2......4......2.......2......4
---- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + --- + ---
....9......15.....21....25......27....33....35......39.....45.....49.....51.....55....57....63.....65....69....75
...z......z........z.......z.......z.......z.......z.......z.........z.......z.......z.......z.......z........z.......z.......z......z
.....2......3......2.......2.......2......2.......2.......4........6........2.........2.......4........2.......1........2
+ --- + --- + --- + --- + --- + --- + --- + --- + ---- + ---- + ---- + ---- + ---- + ---- + ----
.....77.....81....85....87.....91.....93....95......99....105......111....115....117....119....121....123
....z.......z......z........z.......z.......z........z.......z.......z..........z.........z.........z........z........z........z
.....2.........2........2........6........2........2........2........4........4........2........2........2........6
+ ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ----
......125....129....133....135....141....143....145....147....153....155....159....161....165
.....z........z.........z........z.........z........z.........z.........z.........z........z.........z........z.........z
.....1.........4.......4.........2........2........2........2........6........6
+ ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ----
.......169....171....175....177....183....185....187....189....195
......z........z........z.........z..........z........z.........z........z........z
===========================================================
Table 3: Evaluation Of Numerical Limits Of Oddcomp(z) Using Maple V R 3
(Tested using a 200Mhz Pentium with 64 Mbytes of RAMs).
=======================================================
Closed form:
sort(series(sum(1/(z^(2*i+1)*(z^(4*i+2)-1)),i=2^28..2^28+10000),z=infinity, 6*2^28+10000));
Open form:
sort(sum(sum(1/(z^(2*i+1)*z^((4*i+2)*j)),i=2^500000..2^500000+2),j=1..2));
It has not reached the limit yet which is probably somewhere around 2^870000.
=======================================================
3. Conclusions
Thus from Tables 1 and 2, one concludes that the open forms can be made as accurate as the
corresponding closed forms by setting the summation limits of i and j but the open forms generate many
more higher terms in the sequence which must be manually truncated if these are not
wanted. If one attempts to truncate the number of terms by lowering the limit of j,
inaccuracies will creep in. The closed form is much neater since the exact number of terms
can be specified by the z limits.
From Table 3, the results definitely show that the open form is far more superior in handling
large integers all the way up to 2^500000 which is equivalent to a number with 150515
decimal digits.
Closed forms are suitable for algebraic manipulations and open forms for numerical
computations. Sequence algebra thus enjoys the best of both worlds. A sequence algebraist
can investigate number theoretic problems either algebraically or numerically using a
symbolic package without the need to move to a separte compiled software program.
4. Reference:
1. Huen Y.K.: Improved Formulations For Comp(z) and
Prime(z). URL site: http://web.singnet.com.sg/~huens/ .
2. Huen Y.K. : Lemmata, Corollaries, And Theorems In Sequence Order Analysis. URL site:
http://web.singnet.com.sg/~huens/ .
3. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci.
Technol., 1994, VOL. 25, NO.6, pp 913-920.
4. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math.
Educ. Sci. Technol., 1996, VOL.27, NO. 5, 685-691.
5. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,1997,
VOL.28 NO.3, 333-344.
======================== END OF PAPER ======================