Super-prime numbers, also known as higher-order primes or prime-indexed primes (PIPs), are the
subsequence
In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a ...
of
prime numbers
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
that occupy prime-numbered positions within the sequence of all prime numbers.
The subsequence begins
: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, 877, 919, 967, 991, ... .
That is, if ''p''(''n'') denotes the ''n''th prime number, the numbers in this sequence are those of the form ''p''(''p''(''n'')).
used a computer-aided proof (based on calculations involving the
subset sum problem The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' T ...
) to show that every integer greater than 96 may be represented as a sum of distinct super-prime numbers. Their proof relies on a result resembling
Bertrand's postulate
In number theory, Bertrand's postulate is a theorem stating that for any integer n > 3, there always exists at least one prime number p with
:n < p < 2n - 2.
A less restrictive formulation is: for every , there is always ...
, stating that (after the larger gap between super-primes 5 and 11) each super-prime number is less than twice its predecessor in the sequence.
show that there are
:
super-primes up to ''x''.
This can be used to show that the set of all super-primes is
small
Small may refer to:
Science and technology
* SMALL, an ALGOL-like programming language
* Small (anatomy), the lumbar region of the back
* ''Small'' (journal), a nano-science publication
* <small>, an HTML element that defines smaller text ...
.
One can also define "higher-order" primeness much the same way and obtain analogous sequences of primes .
A variation on this theme is the sequence of prime numbers with
palindromic prime
In mathematics, a palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number. Palindromicity depends on the base of the number system and its notational conventions, while primality is independent of such ...
indices, beginning with
:3, 5, 11, 17, 31, 547, 739, 877, 1087, 1153, 2081, 2381, ... .
References
*
*.
*.
*.
External links
A Russian programming contest problem related to the work of Dressler and Parker
Classes of prime numbers
{{numtheory-stub