How To Generate A Short And Contiguous Oddcomp(z) Sequence?
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: 15/10/97, revised: 16/10/97 )
Abstract
One of the problems with sequence algebraic formulations is that infinite summations of Z/i-
layers from i = 1 upward greatly slow down computations. Currently sequence algebra has
found its niche in dialactic analyses especially on hard problems hitherto unsolved by
conventional methods [1,2]. In other words, sequence algebra is weak in numerical analysis.
This paper describes an algorithm which can generate a finite contiguous Oddcomp(z)
sequence which can be located anywhere within the natural number line. The algorithm
gives rise to a primality test by mutual exclusion, i.e., if an odd integer is absent from an
Oddcomp(z) sequence, then it must be a prime. Most primality tests are deterministic on
true primes but false reports could arise on composites but the present method is
deterministic on both composites and primes [8]. The computing procedures are described by
a symbolic software but for working with large integers one needs a compiled language
program supported by multiprecision arithmetic subroutines.
1. Introduction
Current primality tests are probabilistic. Most primality tests will not make false reports on
true primes but could do so with composites [8]. This paper describes a primality test
method which is deterministic for both primes and odd composites and is based on the
following principle:
Theoretical Basis: The generating function Oddcomp(z) is global and deterministic [4,5,6]. Any
odd integer which is not an odd composite must be a prime. To achieve efficient
computations using Oddcomp(z), an algorithm is developed whereby one is able to generate
an odd composite sequence within a specified interval which could be located anywhere
along the natural number line. This sequence must be contiguous for odd composites,
i.e. there should be no missing odd composite terms in it.
The generating function in closed form for Oddcomp(z) as given by equation (1) is globally
deterministic but series expansions of Z/i layers must start from i = 1 from the very beginning
of the number axis [5,6]. This is computationally inefficient and for large integers it will take
an inordinately long time to complete the computations. Since frequently we are only
interested in primality testing of one or several integers, what is needed is an algorithm
which enables one to generate a finite and contiguous sequence of odd composites within a
specified interval. The Maple program line in equation (1) is the starting point but the series
expansions waste precious computing resources. Equation (1) is often used as a
reference to calibrate open formulations for Oddcomp(z) since it is known to be accurate.
Oddcomp(z):=sum(1/(z^(2*i+1)*(z^(4*i+2)-1)),i=1..ub2);
........................ub2
........................-----
.........................\ ...................1
Oddcomp(z) :=...) --------------------------- ...............................(1).
........................./.........(2 i + 1).....(4 i + 2)
........................----- z..............(z............ - 1)
........................i = 1
Great improvements in computational speed can be obtained by using the open form of
Oddcomp(z) as given by equation (2) [4,5,6]. Here a factor k is inserted in the upper limit for i
because it can be proved by geometrical considerations between the Odd(z) line of 2*i+1 and
the even offset line of 4*i+2 that in view of the smaller slope of the latter, it intersects any
normal dropped from a point in the former line two-third the way down. This is left as an
exerecise to readers interested in it.
Oddcompx(z):=sum(sum(1/z^(2*i+1+j*(4*i+2)),j=1..ub),i=1..k*ub);
.........................ub
........................-----..../........................................................\
.........................\........|.....................1...................................|
Oddcompx(z) :=).......| ------------------------------------...| ..............................(2).
........................./........|........(2 i + 1)......j*(4 i + 2)................|
........................-----....\......z..............z................................./
.......................i, j = 1
Figure 1 shows the matrix map of the above equation showing the initial (2*i+1)-line which is
the odd divisor line. This type of matrix map was used by the author to derive the equation
of composites [1]. To the right of this line are lines of integer multiple offsets of (4*i+2)
measured from the odd integer divisor line. Even in this small example, if one specifes a
narrow interval say from n1=45 and n2=50, one could already see the amount of superfluous
computations which could be eliminated to the left and to the right of this interval. For any
Z/i layer, we must establish the offset point just to the left of n1 so that additional offsets can
be added to determine whether these points falls within the specified interval. You will find
that for a very small interval, all points will miss this interval at any point which is greater
than one-third the height of the normal. In other words, the upper limit for i needs not be
greater than (n1)/3 (marked with a bold x for n = 17 in figure 1).
.......................Odd(z) line......................Relative Offsets from 2*i+1
........................2*i+1..............................4*i+2................................8*i+4
xxxxxxxxxxxxxxx#xxxxxxxxxxxxxxxxxxxxx#xxxxxxxxxxxxxxxxxxxxx#x(i+5)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxx#xxxxxxxxxxxxxxxxx#xxxxxxxxxxxxxxxxx#xxxxxxxxxxxx(i+4)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxx#xxxxxxxxxxxxx#xxxxxxxxxxxxx#xxxxxxxxxxxxx#xxxxxxxxx(i+3)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxx#xxxxxxxxx#xxxxxxxxx#xxxxxxxxx#xxxxxxxxx#xxxxxxxxx#xxxx(i+2)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxx#xxxxx#xxxxx#xxxxx#xxxxx#xxxxx#xxxxx#xxxxx#xxxxx#xxxxx#xxx(i=1)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
#xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
========1========2========3========4========5========6
1234567890123456789012345678901234567890123456789012345678901 (Integers n)
Fig.1 - Map showing how the Z/i layers In Oddcomp(z) are plotted.
2. A Numerical Example
Example 1: The example shows how to find all the primes within an interval of 50 units delimited by
n1=181113 and n2=181163. The Maple program line for the computations is shown
in equation (5).
for i from 1 to trunc(181113/3)+1 do i:=i: n1:=181113: n2:=181163: j2:=trunc((n2-
n1)/(4*i+2)): a(i):=sum(1/z^(n1- ((n1-(2*i+1)) mod (4*i+2))*(4*i+2) +j*(4*i+2)),j=1..j2+1) od;....(5).
Oddcomp(z):=
..........12..............2..............1.............2.............42.............2..............2..............5..............2
.......------- ..+ ------- ..+ ------- ..+ ------- .+ ------- .+ ------- .+ ------- .+ ------- .+ -------
......181115.....181117....181119....181121....181125....181127....181129....181131....181133
.....z................z...............z..............z..............z...............z..............z...............z..............z
.
...........5...............8..............5.............4..............1..............2..............1..............2..............3
....+ ------- ..+ ------- ..+ ------- ..+ ------- ..+ ------- .+ ------- .+ ------- .+ ------- .+ -------
......181135.....181137.....181139....181143....181145....181147....181149....181151....181153
.....z................z...............z..............z..............z...............z..............z................z..............z
...........12.............5................2................2
....+ ------- ..+ ------- ..+ ------- ..+ ------- ..+ ..................
.......181155....181159......181161......181163
......z..............z................z................z
The missing odd integers between n1=181113 and n2=181163 are tested by Maple's isprime
function. Since these are true, the reports must be correct thus confirming the accuracy of
the Oddcomp(z) method. All the odd composite terms between these two limits are
generated correctly.
isprime(181123); true
isprime(181141); true
isprime(181157); true
3. Conclusions
Due to the use of arrays a(i)s which need to be summed to get the above Oddcomp(z)
sequence, memory runs out at about a(62000). It is impossible to implement a large
integer example using Maple V R 3. It is quite easy to implement the algorithm using a
compiled language provided it supports multiprecision arithmetic subroutines. The
continued lack of support by compiled language software makers will simply mean that in
future more number theorists will switch to symbolic softwares which have limited big integer
arithmetic capabilities. The author thinks that with increasing computing power predicted for
the next generation of PCs and improvements in symbolic softwares, the time may come
when people realise the convenience of symbolic softwares in algebraic and numerical
investigations. Symbolic program lines are particular useful in presentations of research
results since readers could easily test these programs by cutting and pasting the lines into a
symbolic software package. Very few examples used by the author required more than one
line of codes.
3. Reference:
Remarks: Not all papers are directly relevant to the present paper but are included for
readers who may not be familiar with sequence algebra.
1. Huen Y.K.: A matrix map for primes and nonprimes, Int. J. Math.Educ.Sci.Technol., 1994,
Vol.25, No.6, pp 913 - 920.
2. Huen Y.K..: Visual algebra and its applications, Int. J. Math. Educ. Sci. Technol., 1997,
Vol.28, No.3, 333-344.
3. Huen Y.K.: Lemmata, Corollaries, And Theorems In Sequence Order Analysis. URL site:
http://web.singnet.com.sg/~huens/ .
4. Huen Y.K.: Detecting False Reports In Primality Tests By The Oddcomp(z) Method, URL
site: http://web.singnet.com.sg/~huens/ .
5. Huen Y.K.: The Throwing Power Of Oddcomp(z), URL site: http://web.singnet.com.sg/
~huens/
6. Huen Y.K.: Generating Large Odd Composites With Two Prime Factors, URL site:
http://web.singnet.com.sg/ ~huens/
7. Huen Y.K.: In Search Of Counter-Examples In Maple's Isprime Function, URL site:
http://web.singnet.com.sg/ ~huens/
8. Huen Y.K.: A Sequence Algebraist's View Of Lehmann's Primaity Test, URL site:
http://web.singnet.com.sg/ ~huens/
======================== END OF PAPER ======================