Talk:Higher-order prime numbers

p(n)

By the Style Sheet (and usual convention), p(n) refers to the number of partitions of n. In OEIS sequences this is written prime(n). Here it can also be written $p_{n},$ but should not be written p(n) or p[n].

Sorry, just an editorial thing...

Charles R Greathouse IV 02:21, 28 September 2012 (UTC)

Notation for primes and superprimes

For superprimes (and primes as [so to speak] "superprimes" of order at least 1), which notation is better (using square brackets to avoid confusion with $p(n)$ as the number of partitions of $n$)?

Order at least 1: $p[n]$ or $p_{n}$

Order at least 2: $p[p[n]]$ or $p_{p_{n}}$

Order at least 3: $p[p[p[n]]]$ or $p_{p_{p_{n}}}$

Order at least 4: $p[p[p[p[n]]]]$ or $p_{p_{p_{p_{n}}}}$

— Daniel Forgues 04:05, 28 September 2012 (UTC)

The latter. Charles R Greathouse IV 05:02, 28 September 2012 (UTC)

In the OEIS sequences, all the k's are incremented by 1

First table: In the OEIS sequences, all the k's are incremented by 1. (Why?)

Second table: In the OEIS sequences, all the k's are incremented by 1, so that "≥" are replaced by ">". (Why?)

— Daniel Forgues 04:07, 28 September 2012 (UTC)

Perhaps you can ask Neil Fernandez who wrote A049076. But the convention there is the one that makes the most sense to me: it's the number of primes you can get by iterating $\pi (n).$ Charles R Greathouse IV 05:02, 28 September 2012 (UTC)

Neil Fernandez who wrote A049076:

Let p(k) = k-th prime, let S(p) = S(p(k)) = k, the subscript of p; a(n) = order of primeness of p(n) = 1 + m where m is largest number such that S(S(..S(p(n))...)) with m S's is a prime.

So it's 1 + the number of primes you can get by iterating $\pi (n).$ This implies the the primes that are not superprimes have order of primeness 1. — Daniel Forgues 02:20, 29 September 2012 (UTC)

A049076 is not related to the prime counting function $\pi (n).$ (Unless there is a relation that I don't see...) It is related to the primeness of the subscript [index] $k$ of the prime $p_{k}$ (and the primeness of the index of the index, and so on...).

A049076 Number of steps in the prime index chain [until the index is not prime] for the n-th prime. (This should be the order of primeness, where we have 1 for the primes that are not superprimes.)

{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, ...}

Neil Fernandez has the convention (which I use on the page) that

Order of primeness at least 0: Positive integers (the nonprimes have order of primeness 0)

Order of primeness at least 1: Primes $p[n]$ or $p_{n}$ (the primes which are not superprimes have order of primeness 1)

Order of primeness at least 2: Superprimes $p[p[n]]$ or $p_{p_{n}}$ (the superprimes which are not supersuperprimes have order of primeness 2)

Order of primeness at least 3: Supersuperprimes $p[p[p[n]]]$ or $p_{p_{p_{n}}}$

Order of primeness at least 4: Supersupersuperprimes $p[p[p[p[n]]]]$ or $p_{p_{p_{p_{n}}}}$

where supersuperprimes, supersupersuperprimes... are convenient words here!

According to the OEIS, we have

Order of primeness at least 1: Positive integers

Order of primeness at least 2: Primes $p[n]$ or $p_{n}$

Order of primeness at least 3: Superprimes $p[p[n]]$ or $p_{p_{n}}$

Order of primeness at least 4: Supersuperprimes $p[p[p[n]]]$ or $p_{p_{p_{n}}}$

Order of primeness at least 5: Supersupersuperprimes $p[p[p[p[n]]]]$ or $p_{p_{p_{p_{n}}}}$ (e.g. A049090 Primes for which A049076 > 4.)

Order of primeness at least 6: Supersupersupersuperprimes $p[p[p[p[p[n]]]]]$ or $p_{p_{p_{p_{p_{n}}}}}$ (e.g. A049203 Primes for which A049076 > 5.)

I much prefer to have order of primeness at least 1 for the primes, so that the order of primeness of the nonprimes is 0 instead of 1. — Daniel Forgues 06:49, 28 September 2012 (UTC)

I don't know what you mean when you say, "According to the OEIS". Did you have some sequence in mind? A049076 uses the first convention.

A049076 is certainly closely related to the prime-counting function. An equivalent definition is "Apply $\pi$ to the n-th prime until the result is not prime; a(n) is the number of primes in the chain". (I see it as too obvious an equivalence to add to the sequence, do you disagree?)

Charles R Greathouse IV 17:55, 28 September 2012 (UTC)

Only A049076 uses the first, i.e. Neil Fernandez's convention. Look among the 24 sequences in the two tables, they use the second convention (I put two examples above).

Here is one more example from the first table:

A049090 Primes for which A049076 > 4. (This should be ≥ 4!)

Here is one more example from the second table:

A093046 Primes for which A049076(p) = 13. (This should be = 12!)

Obviously, the prime counting function gives the index of $p_{n}$! (Was I served decaffeinated coffee...?) — Daniel Forgues 02:10, 29 September 2012 (UTC)

Special names for these sequences

I always wanted to coin special names for these sequences. The first sequence: 2,3,5,7,11,13,17,19... is obviously the primes.

The sequence of primes whose indexes are primes can be called the super primes. (This sequence is A006450.)

The next sequence; in OEIS it is A038580, can be called the collosal primes.

Sequence A049090 can be called the golden primes.

Sequence A049203 can be called the platinum primes.

Sequence A049202 can be called the diamond primes.

But I can't think of a good name for A057849. Any suggestions?? J. Lowell 14:46, 23 January 2013 (UTC)

I think that the most natural names would be the 1st-order primes, 2nd-order primes, 3rd-order primes, etc. I guess there are two natural choices: primes as 0th-order (my preference) or as 1st-order.

Super-primes is in the literature, though not so much in the OEIS: actually the only mention of the term seems to be as an alternate name for A051362.

Colossal primes sounds like it should be a part of Yates' hierarchy rather than a higher-order prime. They're actually not very big, growing as n log^2 n, about the same as the safe or Sophie Germain primes.

Golden primes has been used to refer to A006883. That's the trouble with these special names: often they're used somewhere for something, and in any case their meaning is hard to remember. IMHO, at least.

Charles R Greathouse IV 14:59, 23 January 2013 (UTC)