Higher-order prime numbers

This article page is a stub, please help by expanding it.

Higher-order prime numbers, also called superprime numbers (super-prime numbers, super-primes or superprimes), a subsequence of the prime numbers, are the primes that occupy prime-numbered positions within the sequence of all prime numbers. They are also called prime-indexed primes.

A006450 Primes with prime subscripts:

a (n) = p  pn

.

{3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, 211, 241, 277, 283, 331, 353, 367, 401, 431, 461, 509, 547, 563, 587, 599, 617, 709, 739, 773, 797, 859, ...}

That is, if

pi

denotes the

i

-th prime number, the numbers in this sequence are those of the form

p  pi

. (Dressler & Parker 1975) used a computer-aided proof (based on calculations involving the subset sum problem) to show that every integer greater than 96 may be represented as a sum of distinct superprime numbers. Their proof relies on a result resembling Bertrand’s postulate, stating that (after the larger gap between superprimes 5 and 11) each superprime number is less than twice its predecessor in the sequence.

Asymptotic behavior of the superprimes

Broughan and Barnett show that there are

x (log x) 2 + O  x log log x (log x) 3

superprimes up to

x

. This can be used to show that the set of all superprimes is small, in the sense that the sum of their reciprocals converges. Using the asymptotic behavior of the

k

th prime

pk ∼ k log  k

with

k = n log  n

, we find that

p pn

has asymptotic behavior

p pn  ∼  (n log  n) log (n log  n)  ∼  (n log  n) (log n + log log  n)  ∼  n (log  n) 2,

thus giving the asymptotic density (there being

n

superprimes up to

p pn

)

n p pn  ∼  n n (log  n) 2  ∼  1 (log  n) 2  ,

in agreement with Broughan and Barnett.

Superprime gaps

A073131 Superprime gaps:

a (n) = p pn  + 1  −  p pn

, where

pi

is the

i

-th prime.

{2, 6, 6, 14, 10, 18, 8, 16, 26, 18, 30, 22, 12, 20, 30, 36, 6, 48, 22, 14, 34, 30, 30, 48, 38, 16, 24, 12, 18, 92, 30, 34, 24, 62, 18, 42, 48, 24, 40, 32, 24, 66, 18, 30, ...}

Harmonic series of the superprimes

The harmonic series of the superprimes (series of the reciprocals of the superprimes) converges to

S2  =    ∞ ∑   i  = 1    1 p pi  =  1 p2 + 1 p3 + 1 p5 + 1 p7 + 1 p11 + 1 p13 + 1 p17 + 1 p19 + ⋯  =

1 3 + 1 5 + 1 11 + 1 17 + 1 31 + 1 41 + 1 59 + 1 67 + ⋯  =  ?

Higher-order superprimes

One can also define “higher-order” primeness much the same way, and obtain analogous sequences of primes. (Fernandez 1999)

Order of primeness

Let

S ( p) = S ( pk ) = k

, the index of

p

;

a (n)

is order of primeness of

pn = 1 + m

where

m

is largest number such that

S (S ( ⋯ S ( pn ) ⋯ ))

with

m

S

’s is a prime.

F (n) = 0

if

n

is not prime (unit 1 or composite).

1. F ( p) = 1

   :

   p

   is prime but not primeth prime (

   S ( p)

   not prime);

2. F ( p) = 2

   :

   p

   is primeth prime but not primeth primeth prime (

   S (S ( p))

   not prime);

3. F ( p) = 3

   :

   p

   is primeth primeth prime but not primeth primeth primeth prime (

   S (S (S ( p)))

   not prime);
4. ...

A049076 Order of primeness: number of steps in the prime index chain for the

n

-th prime.

{1, 2, 3, 1, 4, 1, 2, 1, 1, 1, 5, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1,, ...}

“Order of primeness” − “order of compositeness”

Since the nonprimes have order of primeness 0 and the noncomposites have order of compositeness 0, if we subtract the order of compositeness from the order of primeness we get a “negative order of primeness” (negation of order of compositeness) for the composite numbers, and

• primes give a positive value (order of primeness),
• 1 gives zero (both order of primeness and order of compositiveness being zero),
• composites give a negative value (negation of order of compositiveness).

A078442 “Order of primeness” of

n

:

a ( p (n)) = a (n) + 1

for

n

-th prime

p (n)

;

a (n) = 0

if

n

is not prime.

{0, 1, 2, 0, 3, 0, 1, 0, 0, 0, 4, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 5, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, ...}

A?????? “Order of compositeness” of

n

:

a (c (n)) = a (n) + 1

for

n

-th composite

c (n)

;

a (n) = 0

if

n

is not composite. (See A059981 for order of compositeness of

n

-th composite.)

{0, 0, 0, 1, 0, 1, 0, 1, 2, 1, 0, 2, 0, 1, 2, 3, 0, 2, 0, 1, 3, 1, 0, 2, 3, 4, 1, 3, 0, 1, 0, 2, ...}

A?????? “Order of primeness” − “order of compositeness.”

{0, 1, 2, −1, 3, −1, 1, −1, −2, −1, 4, −2, 1, −1, −2, −3, 2, −2, 1, −1, −3, −1, 1, −2, −3, − 4, −1, −3, 1, −1, 5, −2, ...}

Superprimes with order of primeness at least k

Primes

p

such that order of primeness F ( p) = A049076 ( p)   ≥   k.

k	Sequence	A-number
1	{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, ...}	A000040
2	{3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, 211, 241, 277, 283, 331, 353, 367, 401, 431, 461, 509, 547, 563, 587, 599, 617, 709, 739, 773, 797, ...}	A006450
3	{5, 11, 31, 59, 127, 179, 277, 331, 431, 599, 709, 919, 1063, 1153, 1297, 1523, 1787, 1847, 2221, 2381, 2477, 2749, 3001, 3259, 3637, 3943, 4091, 4273, 4397, ...}	A038580
4	{11, 31, 127, 277, 709, 1063, 1787, 2221, 3001, 4397, 5381, 7193, 8527, 9319, 10631, 12763, 15299, 15823, 19577, 21179, 22093, 24859, 27457, 30133, 33967, ...}	A049090
5	{31, 127, 709, 1787, 5381, 8527, 15299, 19577, 27457, 42043, 52711, 72727, 87803, 96797, 112129, 137077, 167449, 173867, 219613, 239489, 250751, 285191, ...}	A049203
6	{127, 709, 5381, 15299, 52711, 87803, 167449, 219613, 318211, 506683, 648391, 919913, 1128889, 1254739, 1471343, 1828669, 2269733, 2364361, 3042161, ...}	A049202
7	{709, 5381, 52711, 167449, 648391, 1128889, 2269733, 3042161, 4535189, 7474967, 9737333, 14161729, 17624813, 19734581, 23391799, 29499439, 37139213, ...}	A057849
8	{5381, 52711, 648391, 2269733, 9737333, 17624813, 37139213, 50728129, 77557187, 131807699, 174440041, 259336153, 326851121, 368345293, 440817757, ...}	A057850
9	{52711, 648391, 9737333, 37139213, 174440041, 326851121, 718064159, 997525853, 1559861749, 2724711961, 3657500101, 5545806481, 7069067389, ...}	A057851
10	{648391, 9737333, 174440041, 718064159, 3657500101, 7069067389, 16123689073, 22742734291, 36294260117, 64988430769, 88362852307, 136395369829, ...}	A057847
11	{9737333, 174440041, 3657500101, 16123689073, 88362852307, 175650481151, 414507281407, 592821132889, 963726515729, 1765037224331, 2428095424619, ...}	A058332
12	{174440041, 3657500101, 88362852307, 414507281407, 2428095424619, 4952019383323, 12055296811267, 17461204521323, 28871271685163, 53982894593057, ...}	A093047

Asymptotic behavior of the superprimes with order of primeness at least k

Using the asymptotic behavior of the

k

th superprime

p pk ∼ k (log  k) 2

with

k = n log  n

, we find that

p ppn

has asymptotic behavior

p ppn  ∼  (n log  n) (log (n log  n)) 2  ∼  (n log  n) (log  n + log log  n) 2  ∼  n (log  n) 3,

thus giving the asymptotic density (there being

n

supersuperprimes up to

p ppn

)

n p ppn  ∼  n n (log  n) 3  ∼  1 (log  n) 3  .

By induction, we obtain

${\begin{array}{l}\displaystyle {\underbrace {p_{p_{{\ddots \,}_{p_{p_{n}}}}}} _{p{\text{'s }}(k~{\text{times}})}\sim n(\log n)^{k},}\end{array}}$

thus giving the asymptotic density

${\begin{array}{l}\displaystyle {{\frac {n}{\underbrace {p_{p_{{\ddots \,}_{p_{p_{n}}}}}} _{p{\text{'s }}(k~{\text{times}})}}}\sim {\frac {n}{n(\log n)^{k}}}\sim {\frac {1}{(\log n)^{k}}}.}\end{array}}$

Harmonic series of the superprimes with order of primeness at least k

The harmonic series of the superprimes (series of the reciprocals of the superprimes) with order of primeness at least

k

converges to

     ${\begin{array}{l}\displaystyle {S_{k}=\sum _{i=1}^{\infty }{\frac {1}{\underbrace {p_{p_{{\ddots \,}_{p_{p_{n}}}}}} _{p{\text{'s}}(k~{\text{times}})}}}=\;?,\quad k\geq 2.}\end{array}}$

Superprimes with order of primeness equal to k

Primes

p

such that order of primeness F ( p) = A049076 ( p) = k.

k	Sequence	A-number
1	{2, 7, 13, 19, 23, 29, 37, 43, 47, 53, 61, 71, 73, 79, 89, 97, 101, 103, 107, 113, 131, 137, 139, 149, 151, 163, 167, 173, 181, 193, 197, 199, 223, 227, 229, 233, 239, ...}	A007821
2	{3, 17, 41, 67, 83, 109, 157, 191, 211, 241, 283, 353, 367, 401, 461, 509, 547, 563, 587, 617, 739, 773, 797, 859, 877, 967, 991, 1031, 1087, 1171, 1201, ...}	A049078
3	{5, 59, 179, 331, 431, 599, 919, 1153, 1297, 1523, 1847, 2381, 2477, 2749, 3259, 3637, 3943, 4091, 4273, 4549, 5623, 5869, 6113, 6661, 6823, 7607, 7841, ...}	A049079
4	{11, 277, 1063, 2221, 3001, 4397, 7193, 9319, 10631, 12763, 15823, 21179, 22093, 24859, 30133, 33967, 37217, 38833, 40819, 43651, 55351, 57943, 60647, ...}	A049080
5	{31, 1787, 8527, 19577, 27457, 42043, 72727, 96797, 112129, 137077, 173867, 239489, 250751, 285191, 352007, 401519, 443419, 464939, 490643, 527623, 683873, ...}	A049081
6	{127, 15299, 87803, 219613, 318211, 506683, 919913, 1254739, 1471343, 1828669, 2364361, 3338989, 3509299, 4030889, 5054303, 5823667, 6478961, 6816631, ...}	A058322
7	{709, 167449, 1128889, 3042161, 4535189, 7474967, 14161729, 19734581, 23391799, 29499439, 38790341, 56011909, 59053067, 68425619, 87019979, 101146501, ...}	A058324
8	{5381, 2269733, 17624813, 50728129, 77557187, 131807699, 259336153, 368345293, 440817757, 563167303, 751783477, 1107276647, 1170710369, 1367161723, ...}	A058325
9	{52711, 37139213, 326851121, 997525853, 1559861749, 2724711961, 5545806481, 8012791231, 9672485827, 12501968177, 16917026909, 25366202179, ...}	A058326
10	{648391, 718064159, 7069067389, 22742734291, 36294260117, 64988430769, 136395369829, 200147986693, 243504973489, 318083817907, 435748987787, ...}	A058327
11	{9737333, 16123689073, 175650481151, 592821132889, 963726515729, 1765037224331, 3809491708961, 5669795882633, 6947574946087, 9163611272327, ...}	A058328
12	{174440041, 414507281407, 4952019383323, 17461204521323, 28871271685163, 53982894593057, 119543903707171, 180252380737439, 222334565193649, ...}	A093046

Harmonic series of the superprimes with order of primeness equal to k

The harmonic series of the superprimes (series of the reciprocals of the superprimes) with order of primeness equal to

k

thus converges to

sk = Sk  −  Sk  + 1

, for

k   ≥   2

. Since

S1

, the harmonic series of the primes, diverges with asymptotic growth

n log  n

and

S2

converges, this implies that

s1 = S1  −  S2

, i.e. the harmonic series of the primes which are not superprimes, also diverges with asymptotic growth

n log  n

.

Sequences

A175247 Primes (A000040) with noncomposite (A008578) subscripts. (Same as A006450, prepended with

p (1) = 2

, the unit 1 being noncomposite.)

{2, 3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, 211, 241, 277, 283, 331, 353, 367, 401, 431, 461, 509, 547, 563, 587, 599, 617, 709, 739, 773, 797, 859, ...}

A018252 The nonprime numbers (unit 1 together with the composite numbers, A002808). (Order of primeness is 0.)

See also

• Higher-order composite numbers
• Order of compositeness

References

• Dressler, Robert E.; Parker, S. Thomas (1975), “Primes with a prime subscript”, Journal of the ACM 22 (3): 380–381, doi:10.1145/321892.321900 .

• Fernandez, Neil (1999), An order of primeness, F(p), http://borve.org/primeness/FOP.html .

External links

• Michael R. Mirzayanov, A Russian programming contest problem related to the work of Dressler and Parker, 2001.