On Odd(z), Oddcomp(z), Seq1(z) and Seq2(z)

On Odd(z), Oddcomp(z), Seq1(z) and Seq2(z)

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: 10/10/97, Revsions 10/10 )

Abstract

We know that Oddcomp(z) is a subset of the Odd(z) [1,2,7,8]. By either adding or subtracting an offset of 2 interval units from terms in Oddcomp(z), the new sequences formed called Seq1(z) and Seq2(z) are expected to contain higher ratios of primes to odd composites. One way of comparing prime hit rates amongst sequences is to generate the same number of integers for each sequence and count the number of primes reported by each. Another way is to specify the lower and upper limts of a fixed interval and count the number of primes generated by each sequence within this interval. In this paper, the first method is adopted as being a fair one since the computational effort for each sequence is about the same. An analogy can be made of two wild pigeon hunters whereby each hunter is issued the same number of rounds bullets. The one who bags more pigeons is declared the winner. By this method, it is found that prime hit rates for Seq1(z) and Seq2(z) derived from Oddocmp(z) are significantly higher than those of Odd(z) and that the hit rates, with few exceptions, increase with integer sizes.

1. Introduction

Both Prime(z) and Oddcomp(z) are mutually exclusive subsets of Odd(z) [1]. This paper investigates the prime counts along the Odd(z) line against two new sequence expressions formed by introducing constant offsets of two interval units to each term in Oddcomp(z). Since the number of integers sampled is the same for sequences tested, the comparisons are deemed fair. The Maple program lines used in computations are given by equations (1) to (3).

.....Odd(z):=sum(z^isprime(2*i+1),i=1..10000); ...........................(1).

.....Seq1(z):=sum(z^isprime(6*i+5),i=1..10000); ............................(2).

.....Seq2(z):=sum(z^isprime(6*i+1),i=1..10000); ............................(3).

A reasonable question is why not chose 6*i+7 or 6*i-1 and other higher variations? The reason is that these two sequences generate distinct integers. The other reason is that higher variations contain overlaps on primes which will affect the prime counts. Another reason is that the prime hit rates are found to drop with these higher variations. Computations were performed using a 200 Mhz Pentium with 64 Mbytes of RAMs. The % enhancement on prime hit rate is defined by equation (4).

..........................................number of primes in Seq1(z) or Seq2(z)
............% enhancement = ----------------------------------------------- * 100 ........(4).
....................................................number of primes in Odd(z)

2. Theorems And Collorary

Theorem 1: The two sequences Seq1(z)=6*i+5 and Seq2(z)=6*i+1 generate distinct integers.

Proof: By putting Seq1(z)=Seq2(z) and solve for i we get 5=1 which is impossible. There is no solution. Therefore these two sequences must generate distinct integers. Q.E.D.

Colloary 1: The two sequences Seq1(z) and Seq2(z) must have distinct primes.

Proof: If two sequences have distinct integers, these must have distinct primes if these exist. This follows from theorem 1. Q.E.D.

Theorem 2: (Seq1(z)+Seq2(z))/2 = Oddcomp(z).

Proof: (Seq1(z)+Seq2(z))/2 = (6*+5+6*i+1)/2=6*i+3. But 6*i+3=2*i+1+4*i+2 which defines the odd composite sequence Oddcomp(z). Q.E.D.

3. Experiemental Findings

It should be pointed out that by adding an offset of +/- 2 to an odd composite integer, one is not assured of getting a prime. For example if the odd composite integer is 25, adding 2 to it gives 27 which is still an odd composite. However subtracting 2 from it will give a prime of 23.

It should also be mentioned that by fixing the range of i = 1..10000, the upperlimit for Odd(z) is 3 times lower than that for Seq1(z) and Seq2(z). For example if i =1000, then (2*i+1)/6*i+1 = 2001/6001 ~ 1/3. Since the range is only 1/3 that for Seq1(z) and Seq2(z), one might argue that it surely will contain less primes. This is true but do not forget that the latter two sequences are sampled at 3 times the intervals of Odd(z). Everything being equal, surely these two sequences have high prime hit rates than Odd(z).

4. Prime Hit Rates can be raised further

Prime hit rates for Seq1(z) and Seq2(z) can be raised further by rejecting randomly generated integer i with its least significant digit ending in 0,2,4,5 and 7 by testing with all three equations. This is because such integers when computed using 2*i+1, 6*i+1, or 6*i+5 are bound to be composites with a few exceptions for some lower primes.

Odd(z)=2*i+1, Seq1(z)=6*i+5 and Seq2(z)=6*i+1 used together in fact can help to narrow down the search for primes in primality tests. In most primality tests, such as Lehmann's method, a random number is chosen which is less than p and one proceeds to test whether p is a prime or not a prime [9]. This wastes computational resources. Here we generate a random integer i and determine from its least significant digit whether it should be rejected as it will never be a prime in the Odd(z), Seq1(z) or Seq2(z). Of course the method has nothing to do with primality tests. These are designed to capture as many primes as possible by one formula.

We give below a worked example using Maple V R 3:

i:=rand()^101;

i :=

100125465154111712787879932337850731917498172745635603741630255111450469148 8209500685091889944166472\
997343815528754530431853440658789632420125084425096992805797762041930279897 1432369975578184245216326\
791491223889466683637532726429880523403968897866902359223204716148963194469 9059396523206633667470826\
750790477885129218084634009403700369981377038410211359347579763077719999056 0415093851016953800940689\
432516150946189730151853973953982815422692173524744483242933695675354704240 6486506324599415713469525\
061952090830069922193356072424925731634889290325296525017452949202730893209 1264886575206148812903963\
620757970267730358596509087829006522387934281475190074257861608103914685320 3260729238744436523757974\
836718353215065265134697691559637091217611574818516419211349050859697853254 3707635095395750697711663\
593130097755079319810252933970522685611050607521587561373043899716599519401 5823211257349034863370950\
187023139260908513587386514225830371609945787734380625127935737204669767164 2555133114246695130537632\
299266480645870995315749103235816252694984905338940390436462434553356182432 4247193550517497360914700\
943072571451649341049341827714754927417545439056629223374130272401038641034 2031537712256490930123140\
110897507

With the least significant digit in i ending in a 7, Odd(z) = 2*i+1 will compute to an integer with its least signiciant digit ending in a 5 which is composite. Therefore this should be rejected without further tests. Similarly a randomly generated integer ending in a digit of 0 or 5, will cause Seq1(z)=6*i+5 to generate a composite and so can be rejected immediately. These are the deterministic tests but there are some digits which are not globally deterministic and cannot be used. If Odd(z)=2*i+1 is also included in the tests, least significant digits of 0, 2, 5 and 7 can be immediately rejected without processing. In conventional primality tests, you only know the result after going through the tests but here no arithmetic operations are needed. The remarks might be obtuse as the sequences discussed in this paper are designed to capture as many primes as possible per generation run and not with testing a single integer for primeness or otherwise.

5. Observations

Prime hit rates based on Seq1(z) and Seq2(z) are significantly higher than those obtained from Odd(z) and with few exceptions are increasing with increasing sizes of integers tested. The investigations show that there might be an optimal interval in a sequence for scoring the highest prime hit rate. If the interval is a nonlinear integer function, this hit rate might be raised further but things are getting complicated. There is no reason to do this since more elegant methods of predicting the prime sequence Prime(z) deterministically have already been found in sequence algebra [2,3,6,7,8].

6. Reference:

1. Huen Y.K. : Methods Of Developing Sequence Algebraic Formulations For Comp(z) and Prime(z). URL site: http://web.singnet.com.sg /~huens/ .

2. Huen Y.K.: Improved Formulations For Comp(z) and Prime(z). URL site: http://web.singnet.com.sg/~huens/ .

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. Huren Y.K.: The Throwing Power Of Oddcomp(z), URL site: http://web.singnet.com.sg/ ~huens/

6. 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.

7. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ. Sci. Technol., 1996, VOL.27, NO. 5, 685-691.

8. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,1997, VOL.28 NO.3, 333-344.

9. Huen Y.K.: A Sequence Algebraist's View Of Lehmann's Primality Test, URL site: http://web.singnet.com.sg/~huens/

======================== END OF PAPER ======================