The Exploring Primeness Project

Neil Fernandez

An order of primeness, F(p)

Definition

Let us begin by adopting an apparently strange terminology, and call a prime number p a 'primeth' integer: meaning, the pth integer where p is prime.

It is evident right away that the property of primethness may be applied to members of sequences other than the sequence of integers.

Applying it to the sequence of primeth integers themselves, we see that another sequence suggests itself: the sequence of primeth primeth integers, or primeth primes. By extension, we can construct sequences of primeth primeth primeth integers, and so on. Composite numbers meanwhile do not get the slightest look in. Since they do not appear in the sequence of primeth integers, they do not appear in higher order sequences either. Their position is similar to that of prime numbers with regard to high or low compositeness. Their 'primethness' is non-existent or zero! :-)

I define an Order of Primeness, F(p), as follows.

For a prime p, F(p)=1 unless p is a primeth prime.

If p is a primeth prime, F(p)=2 unless p is a primeth primeth prime.

If p is a primeth primeth prime, F(p)=3 unless p is a primeth primeth primeth prime.

And so on.

All prime integers are primeth integers, a subset of these are primeth primeth integers, a subset of these are primeth primeth primeth integers, etc. The number of 'primeths' in each prime's description equals what I define as its order of primeness F(p).

Some resultant sequences

Various sequences now invite study. [They have been submitted to the On-Line Encyclopedia of Integer Sequences (OEIS)].

First of all, there are sequences of primes with F(p)=1,2,3,4,5,...

The first nine terms of each of these sequences is as follows:

Primes with F(p)=1: 2, 7 13, 19, 23, 29, 37, 43, 47,...

Primes with F(p)=2: 3, 17, 41, 67, 83, 109, 157, 191, 211,...

Primes with F(p)=3: 5, 59, 179, 331, 431, 599, 919, 1153, 1297,...

Primes with F(p)=4: 11, 277, 1063, 2221, 3001, 4397, 7193, 9319, 10631, ...

Primes with F(p)=5: 31, 1787, 8527, 19577, 27457, 42043, 72727, 96797,...

We have here a sort of sieve. Having taken the 'integers with prime subscripts', namely the primes, in sequence, we remove those that do not have prime subscripts in **that** sequence, and iterate.

Other sequences consist of those numbers that remain in the sieve after each iteration, namely those with F(p)>1,2,3,4,...

The first nine terms in each of these sequences are as follows:

Primes with F(p)>1: 3, 5, 11, 17, 31, 41, 59, 67, 83,...

Primes with F(p)>2: 5, 11, 31, 59, 127, 179, 277, 331, 431,...

Primes with F(p)>3: 11, 31, 127, 277, 709, 1063, 1787, 2221, 3001, ...

Then there is the sequence consisting of the smallest prime p for which F(p) = n, for each n. Thus the smallest prime with F(p)=1 is 2, the smallest with F(p)=5 is 31, the smallest with F(p)=9 is 52711. The first terms are as follows:

Smallest primes for which F(p)=n: 2, 3, 5, 11, 31, 127, 709, 5381, 52711, ...

The terms of another sequence are simply the values of F(p(n)) for each prime p(n). This starts as follows:

F(p(n)) for successive primes p(n): 1, 2, 3, 1, 4, 1, 2, 1, 1, 1, 5, 1, 2, 1, 1, 1, 3, 1, 2, ...

This is a fascinating sequence which I suspect has many interesting features awaiting discovery. Repeating subsequences include the 19-unit long string '1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1', which appears between terms 12 and 30 and again between terms 36 and 54.

More terms of each of the above sequences are given in a separate document.

A few were known before. Thus the sequence for F=1 is listed in the OEIS as A007821, Primes p(n) where n is composite, with reference to Clark Kimberling's paper, Fractal sequences and interspersions, Ars Combinatoria, 45 (1997) 157. The sequence for F>1 has also been noted, and appears in the OEIS as A006450, Primes with prime subscripts, with reference to R.E.Dressler and S.T.Parker's paper, Primes with a prime subscript, J. ACM, 22 (1975), 380-381. And the last but one sequence given above also appears, although in a slightly different guise, with a zeroth term, 1, appended at the beginning. This is R.G.Wilson's primeth recurrence (A007097), where the zeroth term is 1 and the (n+1)th term is the nth prime.

The Exploring Primeness Project will report on further investigations in due course.

Copyright, Neil Fernandez 1999.

Last modified: 8 August 1999.