# How Super is this Prime?

A super prime is a prime whose index in the list of primes is also a prime:

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


For this challenge, an "order 2" super prime is defined as a super prime whose index in the list of super primes is a super prime:

11, 31, 127, 277, 709, 1063, 1787, 2221, 3001, 4397, ...


An "order 3" super prime is an order 2 super prime whose index in the list of order 2 super primes is an order 2 super prime:

5381, 52711, 648391, ...


And so on.

Your task is to write a program or function, which, when given a prime, outputs/returns the highest order of super primes that the prime is a part of.

In other words, how "super" is the prime?

## Rules

• This is so the solution with the lowest byte count wins
• Standard loopholes are forbidden
• The index of each prime in the list of primes, super primes, and so on, is assumed to be 1-indexed
• You must output:
• 0 for primes which are not super primes
• 1 for super primes which are not order 2 super primes
• 2 for order 2 super primes which are not order 3 super primes
• And so on
• You can assume inputs will always be prime numbers

## Test Cases

2 -> 0
3 -> 1
11 -> 2
211 -> 1
277 -> 2
823 -> 0
4397 -> 2
5381 -> 3
171697 -> 2
499403 -> 2
648391 -> 3


Your program must in theory be able to handle any order of super prime from 0 to infinity, even if it can only do the first few in a reasonable time.

• Is 31 a valid input? If yes, is the expected output 2? Commented Apr 9, 2023 at 13:26
• Next prime with order 2 after 499403 is 506683. Found with Mathematica in ~ 20 s. And checked in TIO in 1.2 s Commented Apr 9, 2023 at 15:39
• @Arnauld Yes and yes Commented Apr 9, 2023 at 16:33
• Related Commented Apr 9, 2023 at 22:22

# Jelly,  12 11  10 bytes

ÆRJfịƊƬḊẎċ


A monadic Link that accepts a prime integer and yields the level.

Try it online!

### How?

ÆRJfịƊƬḊẎċ - Link: prime number, P   e.g
ÆR         - get all primes in [2..P] in ascending order
J        -     indices of L -> [1..length(L]
f       -     filter keep if in (L)
ị      -     index into (L) -> next level, less than or equal to P -> new L
Ḋ   - dequeue - remove the initial list of primes
Ẏ  - tighten - to a flat list of all of the numbers found at all levels
ċ - count occurrences of (P)


# Wolfram Language (Mathematica), 43 bytes

If[PrimeQ@#,1+#0@PrimePi@#,0]&/*Log2/*Floor


Try it online!

Primes of order $$\n\$$ are those that are a result of applying Prime (with Prime[x] the xth prime) on an integer $$\2^n\$$ times.

• Thank you for cool ideas! But what does /* mean here? Commented Apr 10, 2023 at 3:42
• @lesobrod /* is RightComposition; (f/*g)[x]=g[f[x]].
– att
Commented Apr 10, 2023 at 5:34

# Vyxal, 21 bytes

Þp¥(¨₂›æ;)ḟ›&›)⁽æ$ŀL‹  Try it Online! ## Explained Þp¥(¨₂›æ;)ḟ›&›)⁽æ$ŀL‹
)⁽  \$ŀ   # While applying function ⁽ on the result of function ) is true, collect results.
⁽æ      # Function ⁽: Is argument prime?
Þp¥(¨₂›æ;)ḟ›&›)        # Function ):
Þp                     #   The list of all primes
¥(     )             #   #register times (starts at 0):
¨₂  ;              #     Filter the top of the stack by:
›                #       item index + 1
æ               #       is prime
#   This gets the (register)th order super primes
ḟ›           #   Find the index of the function argument in that list
&›         #   Increment the register for the next iteration
L‹ # Length of that - 1


# JavaScript (ES6), 84 bytes

n=>~~Math.log2((g=n=>{for(i=k=0;k<n;i+=!d)for(d=k++;k%d--;);return!d*n&&1+g(i)})(n))


Try it online!

# Wolfram Language (Mathematica), 10698 66 bytes

   (a=Prime@Range@PrimePi@#;0)//.c_/;!FreeQ[a=0&@@a[[#]]&/@a,#]:>c+1&


Try it online!

Thanks to @att!

Old less golfed version for such noobs as I am:

(a=Table[Prime@k,{k,PrimePi@#}];
c=0;
While[
MemberQ[a=If[#<=Length@a,a[[#]],Nothing]
/@a,#],
c++];
c)&

• Great work! But for n=648391 it will timeout? It seems better to store a result table in advance. Commented Apr 9, 2023 at 14:08
• @138Aspen This is code golf. Answers only need to work in theory, given enough time and memory. Commented Apr 9, 2023 at 14:12
• Yes, you are true. "Your program must in theory be able to handle any order of super prime from 0 to infinity, even if it can only do the first few in a reasonable time." I omitted the rule. Commented Apr 9, 2023 at 14:15
• @138Aspen Yes, you are right in terms of efficiency, but in CG the size of the code is important. And if it solves the problem in principle, it is enough. I know that Mathematica can solve this problem more efficiently, and I’ll work on it (^_^) Commented Apr 9, 2023 at 14:15
• -22
– att
Commented Apr 9, 2023 at 19:14

# 05AB1E, 12 bytes

ÅP.ΓDāåÏ}˜I¢


Very slow for larger inputs due to the āåÏ. The test suite below uses the legacy version with a slightly modified (1 byte longer) version to speed it up significally - although it'll still time out for the largest two test cases.

Explanation:

ÅP        # Push a list of all primes <= the (implicit) input-prime
.Γ      # Loop until the result no longer changes, retaining any intermediate results:
D     #  Duplicate the current list
ā    #  Push a list in the range [1,length] (without popping)
å   #  Check for each index whether it's in the list
Ï  #  Only keep the values at the truthy indices
}˜     # After the changes-loop: flatten the list of lists
I¢   # Count the input in this flattened list
# (after which the result is output implicitly)


# Wolfram Language (Mathematica), 354 bytes

Try it online!

NMax=648391;OrderMax=4;PrimePiPowerNest=Composition@@Table[PrimePi,{2^#}]&;x=Prime[Range@*PrimePi@NMax];res={x};n=1;While[n<=OrderMax,x=Table[x[[i]],{i,x[[;;PrimePiPowerNest[n][NMax]]]}];res=Append[res,x];n++];f[num_]:=Module[{i,output},output=-1;For[i=1,i<Length[res],i++,If[MemberQ[res[[i]],num]&&!MemberQ[res[[i+1]],num],output=i-1;Break[];];];output]


How does it work? Or Ungolfed version:

ClearAll["Global*"];

NMax = 648391;
OrderMax = 4;

PrimePiPowerNest[n_] := Composition @@ Table[PrimePi, {2^n}];
PrimePowerNest[n_] := Composition @@ Table[Prime, {2^n}];
x = Prime[Range[1, PrimePi[NMax], 1]];
res = {x};
n = 1;
While[n <= OrderMax,
x = Table[x[[i]], {i, x[[;; PrimePiPowerNest[n][NMax]]]}];
Print[x[[;; 5]]];
res = Append[res, x];
n++]

f[num_] := Module[{i, output}, output = -1;
For[i = 1, i < Length[res], i++,
If[MemberQ[res[[i]], num] && ! MemberQ[res[[i + 1]], num],
output = i - 1;
Break[];];];
output]    (*input 648391 output 3, 648391 is 3 order super prime*)

f[2]//Print
f[3]//Print
f[11]//Print
f[211]//Print
f[277]//Print
f[823]//Print
f[4397]//Print
f[5381]//Print
f[171697]//Print
f[499403]//Print
f[648391]//Print


the $$\k\$$-th element of $$\n\$$-order super prime is just PrimePowerNest[n][k]`