List Processing In Sequence Algebra
by
Huen Y.K.
CAHRC, P.O.Box 1003, Singapore 911101
http://web.singnet.com.sg/~activweb/
Related URL-sites: http://web.singnet.com.sg/~huens/
email: huens@mbox3.singnet.com.sg
(A short communication - 1st released: 23/12/97)
Abstract
Since number sequences are just lists in sequence algebraic format, mastering the
techniques of processing these by symbolic softwares is important. This paper shows how
number sequences can be converted into lists, manipulated, and translated back into new
number sequences. Most of these operations are either newly defined or unique to sequence
algebra. One can even implement inter-sequence scalar product and boolean logic
operations. Symbolic softwares do have a niche in sequence algebra.
1. Introduction
LISP stands for list processing. Most symbolic softwares including Macsyma support list
processing functions. The objective of this paper is to explore list programming techniques
on operations unique to sequence algebra. These will be demonstrated by worked examples.
2. Worked Examples
By definition, number sequences in sequence algebra are expressed in Laurent series when
expanded from the closed forms [3(i),3(ii)]. In number theory, the integer-set is defined by the
numerator coefficients of the sequence. For example, equation (1) would have been
translated into the integer-set [1,1,0,1,0,1,1]. The absolute magnitudes of integers are read
from the number of unit intervals displaced from the first integer in the above list. Just
because the first integer is 1, it does not mean that the integer-set starts from 1. The 1 is
interpreted as one copy of the term 1/z^0 and the actual integer is represented by the power-
index to z, i.e., 0. Just take the power index as a measure of number of unit intervals from
the first integer. 0 here means zero unit intervals from the first integer which is the integer
itself. This is called the holistic form and sequence algebra applied to number theory should
be called holistic number theory to distinguish it from conventional number theory. Sequence
algebraic generating functions are derived from z-transforms and are different from the
Euler's forms in discrete mathematics [1,2].
.....................1.........1.........1
.....1 + 1/z + ---- + ---- + ---- ..............................................(1).
.......................3.........5.........6
.....................z.........z.........z
=====================================================
Example 1: Given the number sequence in equation (2), find the integer-set as well as the
power-index set.
Solutions: The steps show how these can be solved using Macsyma 2.2.
Nat_z:1+1/z+1/z^3+1/z^5+1/z^6;
.......1......1.......1.......1
.....--- + --- + --- + --- + 1 ...................................................(2).
.......z........3.......5.......6
...............z.......z.......z
Integer_set:reverse(makelist(coeff(Nat_z,z,i),i,lopow(Nat_z,z),0));
.......................[1, 1, 0, 1, 0, 1, 1]...................................................(3).
Power_index:reverse(makelist(abs(i),i,lopow(Nat_z,z),0));
.......................[0, 1, 2, 3, 4, 5, 6]...................................................(4).
Comments on equation (4): The abs( ) function is inserted in equation (4) since the natural
number set is positive. Without it the power indices will be returned as negative since these
are in the denominators in equation (2).
=================Supplement to Example 1===============
Precautions: Note that Macsyma handles straightforward sequences and sequences
generated by taylor function differently which gives apparent discrepancies between the
output results. We give below an example:
(i) Nat_z:1+1/z+1/z^2+1/z^3+1/z^4+1/z^5;
.......1......1.......1......1.......1
.....--- + --- + --- + --- + --- + 1
.......z.........2......3......4.......5
...............z.......z......z.......z
integer_set:reverse(makelist(coeff(Nat_z,z,i),i,lopow(Nat_z,z),0));
..................................[1, 1, 1, 1, 1, 1]
(ii) Nat_z:taylor(z/(z-1),z,inf,5);
............1.......1.......1.......1.......1
.....1 + --- + --- + --- + --- + --- + . . .
............z.........2.......3.......4.......5
.....................z.......z.......z.......z
integer_set:reverse(makelist(coeff(Nat_z,z,i),i,lopow(Nat_z,z),0));
............................[1, 0, 0, 0, 0, 0]
The reason is TAYLOR uses a special representation called "Taylor
extended rational canonical expression" which is indicated in
the display by a /T/ near the line label; and in this case COEFF
needs to be called on the general representation. You can convert
from the extended RAT representation to general representation by
calling RATDISREP as follows:
Nat_z:ratdisrep(taylor(z/(z-1),z,inf,5));
Thereafter the discrepancies between the two outputs will be elminated.
====================================================
Example 2: Given a finite number sequence expression in equation (5):
............................1........1
.....F1(z) := 1/z + ---- + ---- .....................................(5),
..............................3........5
............................z........z
find the sequence in which all corresponding ordered-terms in the above equation have been
reciprocated as shown in equation (6). Note: Since no previous name was given to such an
operation, it is simply called scalar-reciprocation which differs from 1/F2(z).
.......................................5.....3
........................F2(z) := z + z + z ........................................(6).
Solutions:
F1_z:1/z+1/z^3+1/z^5;
.........................................1.......1........1
............................F1_z = --- + --- + ----- .......................................(7).
.........................................z..........3........5
..................................................z........z
F2_z:apply("+",1/args(F1_z));
...........................................5.......3
.............................F2_z = z ...+ z ... + z..........................................(8).
==============================================================
Example 3: Given the integer-set [0,1,0,1,0,1,0,1,0,1], reassemble this back into sequence
algebraic format.
Solutions:
coeffs:[0,1,0,1,0,1,0,1,0,1]; .................................................(9).
makelist(Coeffs[i]/z^(i-1),i,1,length(Coeffs));
............................1........1........1.........1........1
.....................[0, ---, 0, ---, 0, ---, 0, ---, 0, --- ]..................................(10).
............................z..........3.........5.........7........9
......................................z.........z..........z........z
apply("+",%);
....................1.......1.......1......1.......1
...................--- + --- + --- + --- + --- ...............................................(11).
....................z.........3........5......7.......9
.............................z........z.......z.......z
===================================================
Example 4: Given two sequences represented by integer-sets [1,1,1,0,1] and [1,1,0,0,1]
investigate whether logical AND, OR, and XOR can be replaced directly by arithmetic AND,
OR and XOR. Are there any advantages in arithmetic logic operations?
Solutions: Arithmatic logic AND, OR, and XOR will be presented first followed by logical
versions. The two sequences to be operated on must be lists of the same length and operations
are defined between numerator coefficients of the same ordered terms whilst the original
orders are preserved, i.e., the denominator parts are not multiplied. Note inter-sequence
logical operations have not been previously defined. So these are new. Note also that all
input sequences are assumed to have been normalised by the Normc( ) function [11].
=========================================
(i)Arithmetic AND version: logical AND is replaced by arithmetic Multiply.
x1:[1,1,1,0,1];
.......................[1, 1, 1, 0, 1] ...........................................(12).
x2:[1,1,0,0,1];
......................[1, 1, 0, 0, 1] .................................................(13).
makelist((pop(x1)*pop(x2))/z^i,i,0,length(x1)-1);
....................................1.............1
............................[1, ----, 0, 0, ---- ].........................................(14).
....................................z................4
...................................................z
apply("+",%);
................................1..........1
..............................----- + ---- + 1 .........................................(15).
................................z.............4
............................................z
(ii)Arithmetic OR version: logical OR is replaced by arithmetic Add.
Comments: The outputs have three levels, viz., 2, 1, and 0. 2 and 1 are counted as true and 0 as false.
Some symbolic packages will only accept 1s and 0s in logical operations. Therefor output
sequences must be presented in normalised forms by Normc( ) function especially when
these become inputs to other functions.
makelist((pop(x1)+pop(x2))/z^i,i,0,length(x1)-1);
.................................2......1..........2
.........................[2, ----, ---- , 0, ---- ] .........................................(16).
.................................z........2..........4
.........................................z..........z
apply("+",%);
.............................2........1.........2
.......................... ---- + ---- + ---- + 2 ........................................(17).
.............................z..........2..........4
......................................z..........z
(iii)Arithmetic XOR version: logical AND is replaced by arithmetic Subtract.
makelist((pop(x1)-pop(x2))/z^i,i,0,length(x1)-1);
Comments: There are three levels, viz., 1, 0, and -1 where 1 and -1 are treated as
True and 0 as False. The negative sign can be removed by abs( ) function before
normalising with Normc ( ) function.
.....................................1
..........................[0, 0, ----, 0, 0] ...............................................(18).
.......................................2
.....................................z
apply("+",%);
...................................1
.................................----- ....................................................(19).
.....................................2
...................................z
=========================================
(i) Logical AND versions: implemented by logand.
makelist(logand(pop(x1),pop(x2))/z^i,i,0,length(x1)-1);
.............................1...............1
....................[1, -----, 0, 0, ----- ] .............................................(20).
.............................z..................4
..............................................z
apply("+",%);
...............................1..........1
.............................----- + ---- + 1 ..............................................(21).
...............................z............4
...........................................z
(ii) Logical OR versions: implemented by logor.
makelist(logor(pop(x1),pop(x2))/z^i,i,0,length(x1)-1);
.................................1......1.........1
.........................[1, ----, ----, 0, ---- ] ..........................................(22).
.................................z........2.........4
........................................z..........z
apply("+",%);
...........................1.........1.........1
..........................---- + ---- + ---- + 1 ........................................(23).
...........................z............2.........4
......................................z..........z
(iii) Logical XOR versions: implemented by logxor.
makelist(logxor(pop(x1),pop(x2))/z^i,i,0,length(x1)-1);
...................................1
........................[0, 0, -----, 0, 0] ...............................................(24).
.....................................2
...................................z
apply("+",%);
...................................1
................................------ .....................................................(25).
.....................................2
...................................z
Comments: Why are inter-sequence logical operations required? There are still several
sequence algebraic formulae which have embedded logical operators, an example of which
is the generating function for the twin-prime sequence. We give below one version of the
twin-prime formulation written LISP-style and you will appreciate why logical operations are
needed [3(iii)].
Twin_prime:( OR (AND Prime_z z^2*Prime_z) (AND Prime_z z^(-2)*Prime_z));.....(26).
=======================================================
3. Summary
This paper describes briefly some inter-sequence operations, both arithmetic and logical,
which are unique to sequence algebra. Some new sequence algebraic operations are
fundamental as these cannot be developed from existing arithmetic or logical operations.
Although not included in this paper, the Normc function has to be independently defined {3(iii)). All
output sequences which are to be fed into other sequence algebraic functions must be
normalised using this function. Otherwise sequences cannot be handled algebraically and
globally in sequence algebra. Other examples described in this paper are equally important.
We describe arithmetic logical operations which depend purely on arithmetic operations of *, +
and -. These are interesting since boolean operators are not compatible with arithmetic
operators. But this domain has not be fully developed. So no miracles can be claimed yet.
4. Acknowledgements
The author would like to thank Dr. Jeffrey P. Golden of Macsyma Inc. for his contributions
to some of the program codelines used in this paper. Without his help, this paper would
have taken much longer to complete or maybe not completed at all.
5. References
Comments: Not all titles are directly referenced in the main paper. These
are included for background readings for readers who are not familiar with sequence
algebra. Only papers having some relevance to the paper are included.
1. Brualdi A. Richard (1977): Introductory Combinatorics, Chapter 7, Generating
Functions, North Holland, pp 127 to 139.
========================================================
2. Liu C.L. (1985): Elements Of Discrete Mathematics, McGRAW-HILL INTERNATIONAL
EDITIONS, computer science series, pp 290 to 295.
========================================================
(3) The following articles are either published or in the press
but for copyright reasons, these cannot be reproduced here for download. Please contact
the publishers: Taylor & Francis Ltd., 1 Gunpowder Square, London, EC4A 3DE, England,
for further information:
(i) Some interesting properties of the natural number system, INT.J.MATH.EDUC.SCI.TECHNOL,
1996,VOL.27,NO.5,685-691.
(ii) Visual algebra and its applications, INT.J.MATH.EDUC.SCI.TECHNOL,
1997,VOL.28,NO.3, 333-344.
(iii) The twin prime problem revisited, INT.J.MATH.EDUC.SCI.TECHNOL.,199?,VOL.??, NO.?,???-???, proof paper
mes-0488 (10 pages).
=========================================================
4. A Simple Introduction To Sequence
Algebra - by Huen Y.K.
(date release: 15.3.97) (38 KBytes, 11*A4 pages).
========================================================
5. The Canonical Generating Function
or CGF(z) ... - by Huen Y.K.
(date released : 27.5..97) (24 KBytes, 7*A4s).
========================================================
6. Unsolved Problems In Sequence
Algebra - by Huen Y.K. (date released : 6.6.97) (29.4 KBytes, 9*A4s).
========================================================
7. Methods Of Developing Sequence
Algebraic Formulations For Comp(z) and Prime(z) - by Huen Y.K. (date released : 20.6.97) (36.8 KBytes, 10*A4s).
========================================================
8. Lemmata, Corollaries, And
Theorems In Sequence Order Analysis. - by Huen Y.K. (date released : 6.7.97) (38.3 KBytes, 12*A4s).
========================================================
9. Generating Functions -
Closed Forms vs Open Forms
- by Huen Y.K. (date released : 1.10.97 ) (21 Kbytes).
========================================================
10. Evaluations Of Normc( ) Function
In Macsyma 2.2
- Huen Y.K. (Date Released 17/12/97, 14 Kbytes)
==================== END OF PAPER =================