This site is supported by donations to The OEIS Foundation.

Higher-order prime numbers

From OeisWiki
Jump to: navigation, search


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[1] 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
pkk log  k
with
k = n log  n
, we find that
ppn
has asymptotic behavior
ppn  ∼  (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
ppn
)
n
ppn
 ∼ 
n
n (log  n) 2
 ∼ 
1
(log  n) 2
 ,

in agreement with Broughan and Barnett.

Superprime gaps

A073131 Superprime gaps:
a (n) = ppn  + 1  −  ppn
, 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
ppi
 = 
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.[2]

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
ppkk (log  k) 2
with
k = n log  n
, we find that
pppn
has asymptotic behavior
pppn  ∼  (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
pppn
)
n
pppn
 ∼ 
n
n (log  n) 3
 ∼ 
1
(log  n) 3
 .

By induction, we obtain

thus giving the asymptotic density

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

     

Superprimes with order of primeness equal to k

Primes
p
such that order of primeness F ( p) = A049076 ( p) = k.[3]

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

Notes

  1. Kevin A. Broughan and A. Ross Barnett, On the Subsequence of Primes Having Prime Subscripts, Journal of Integer Sequences 12 (2009), article 09.2.3.
  2. In the OEIS, all the
    k
    ’s are incremented by 1, so that “  ≥  ” are replaced by “  >  ”. (Why?)
  3. In the OEIS, all the
    k
    ’s are incremented by 1. (Why?)

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 .

External links