16
\$\begingroup\$

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.

Task

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.

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

7 Answers 7

5
\$\begingroup\$

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
      Ƭ    - start with L=that and collect up while distinct applying:
     Ɗ     -   last three links as a monad - f(L):
  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)
\$\endgroup\$
4
\$\begingroup\$

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.

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

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 106 98 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)&
\$\endgroup\$
6
  • \$\begingroup\$ Great work! But for n=648391 it will timeout? It seems better to store a result table in advance. \$\endgroup\$
    – 138 Aspen
    Apr 9, 2023 at 14:08
  • 1
    \$\begingroup\$ @138Aspen This is code golf. Answers only need to work in theory, given enough time and memory. \$\endgroup\$
    – Arnauld
    Apr 9, 2023 at 14:12
  • \$\begingroup\$ 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. \$\endgroup\$
    – 138 Aspen
    Apr 9, 2023 at 14:15
  • 1
    \$\begingroup\$ @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 (^_^) \$\endgroup\$
    – lesobrod
    Apr 9, 2023 at 14:15
  • 1
    \$\begingroup\$ -22 \$\endgroup\$
    – att
    Apr 9, 2023 at 19:14
1
\$\begingroup\$

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.

Try it online or verify all 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)
\$\endgroup\$
0
\$\begingroup\$

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]

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.