17
\$\begingroup\$

The Recursively Prime Primes is are sequence of primes such that

p(1) = 2
p(n) = the p(n-1)th prime

Here is an example of how one might calculate the 4th Recursively Prime Prime.

p(4) = the p(3)th prime
p(3) = the p(2)th prime
p(2) = the p(1)th prime
p(1) = 2
p(2) = the 2nd prime
p(2) = 3
p(3) = the 3rd prime
p(3) = 5
p(4) = the 5th prime
p(4) = 11

You should write a program or function that when given n, outputs the nth Recursively Prime Prime.

You may choose to use 0 based indexing if you wish in which case you must indicate so in your answer.

This is so the goal is to minimize your byte count.


Test Cases

1 -> 2
2 -> 3
3 -> 5
4 -> 11
5 -> 31
6 -> 127
7 -> 709
8 -> 5381
9 -> 52711

Relevant OEIS entry: OEIS A007097

\$\endgroup\$

11 Answers 11

13
\$\begingroup\$

Oasis, 3 bytes

The program is 0-indexed. Code:

<q2

Uses the formula: a(n) = nth_prime(a(n-1) - 1), with the base case a(0) = 2.

Code explanation:

  2   = a(0)

<     # Decrement a(n - 1) to get a(n - 1) - 1
 q    # prime(a(n - 1) - 1)

Try it online!

\$\endgroup\$
8
\$\begingroup\$

Actually, 7 bytes

1@⌠DP⌡n

Try it online!

Explanation:

1@⌠DP⌡n
1        push 1
 @       swap 1 with n
  ⌠DP⌡n  do the following n times:
   DP      decrement, prime at index
\$\endgroup\$
8
\$\begingroup\$

Mathematica, 16 bytes

Nest[Prime,1,#]&

Anonymous function. Takes a number as input and returns a number as output.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 5 4 bytes

1 byte thanks to @Dennis.

1ÆN¡

Try it online!

Explanation

1        Starting with n = 1,
 ÆN      replace n by the nth prime
   ¡     (input) times.
\$\endgroup\$
  • \$\begingroup\$ You don't need the . \$\endgroup\$ – Dennis Feb 21 '17 at 18:57
  • \$\begingroup\$ @Dennis So does ¡ only accept nilads as repetitions and default to input if none are found? \$\endgroup\$ – PurkkaKoodari Feb 21 '17 at 19:15
  • \$\begingroup\$ <f><n>¡ happily accepts monadic or dyadic atoms for <n>. However, if <f> is a nilad, something must be wrong, so it is parsed as <f>¡ instead and takes the last input (last command-line argument, STDIN is there are none) as <n> instead. \$\endgroup\$ – Dennis Feb 21 '17 at 19:59
5
\$\begingroup\$

JavaScript (ES6), 71 bytes

p=(n,x=1)=>n?p(n-1,(N=y=>x?N(++y,x-=(P=z=>y%--z?P(z):z==1)(y)):y)(1)):x

Ungolfed, you have three separate recursive functions:

P=(n,x=n)=>n%--x?P(n,x):x==1
N=(n,x=1)=>n?N(n-P(++x),x):x
p=(n,x=1)=>n?p(n-1,N(x)):x
  • P determines whether n is prime;
  • N finds the nth prime;
  • p recursively runs N on input 1 n times.
\$\endgroup\$
4
\$\begingroup\$

MATL, 6 bytes

1i:"Yq

Try it online!

Explanation

1      % Push 1
i      % Input n
:      % Range [1 2 ... N]
"      % For each (that is, do the following N times)
  Yq   %   k-th prime, where k is the input
       % End for each (implicit)
       % Display stack (implicit)
\$\endgroup\$
3
\$\begingroup\$

R, 98 93 bytes

5 bytes thanks to @smci

Here is a horribly inefficient recursive solution:

f<-function(m,n=1){j<-1;for(i in 1:n){j<-numbers::nextPrime(j)};a<-ifelse(m==0,j,f(m-1,j));a}

Test Output:

f(6)
[1] 127

f(10)        ### takes almost a minute... YIKES!!!
[1] 648391
\$\endgroup\$
  • 1
    \$\begingroup\$ You can shave a little off by doing a<-ifelse(m==0,j,f(m-1,j)) \$\endgroup\$ – smci Feb 22 '17 at 0:31
  • 1
    \$\begingroup\$ 74 bytes \$\endgroup\$ – Giuseppe Oct 7 '17 at 19:23
  • \$\begingroup\$ @Giuseppe, you should post that as an answer... that is a considerable decrease!!! I have never seen if used like that before... pretty cool!! \$\endgroup\$ – Joseph Wood Oct 7 '17 at 21:11
  • \$\begingroup\$ @JosephWood nah, those are just standard golfs; the core algorithm didn't change. I'd suggest reading tips for golfing in R for some more cool golfing tips (although usually they are terrible R style). \$\endgroup\$ – Giuseppe Oct 7 '17 at 22:01
2
\$\begingroup\$

Bash + common utilities, 55

Since we're doing recursive primes, here's a recursive answer:

((SHLVL-2<$1))&&primes 2|sed -n "`$0 $1`{p;q}"||echo 1

Since recursion level counting is based off the $SHLVL built-in variable, then the answer can be off if you're already a few shell levels deep. This is probably why this answer doesn't work on TIO.


If that's no good, then here's a more conventional answer:

Bash + common utilities, 58

for((i=$1;i--;));{
n=`primes 2|sed -n "$n{p;q}"`
}
echo $n

Try it online.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 58 bytes

1-indexed

f 1=2;f n=[x|x<-[2..],all((>)2.gcd x)[2..x-1]]!!(f(n-1)-1)

Try it online!

Explanation:

Uses the same 0-indexed prime-list access trick as Adnan's answer.
Essentially straight-up follows the specification otherwise.

f 1=2; -- base case
f n= -- main case
    [x|x<-[2..],all((>)2.gcd x)[2..x-1]]             -- list of all primes
    [x|x<-[2..],                                     -- consider all numbers
                               [2..x-1]              -- consider all smaller numbers
                all((>)2.gcd x)                      -- is coprime with them?
                    (>)2.                            -- 2 is greater than
                         gcd x                       -- gcd(x,lambda input)
                                        !!(f(n-1)-1) -- access the
                                                     -- f(n-1)-th 1-indexed prime
\$\endgroup\$
0
\$\begingroup\$

Wonder, 23 bytes

p\.{1\2@:^(- p -#0 1)1P

1-indexed. Usage:

p\.{1\2@:^(- p -#0 1)1P}; p 3

Explanation

p\.{                #. Pattern matching syntax
  1\2               #. Base case p(1)=2
  @:^(- p -#0 1)1P  #. Other cases p(n)=nthprime(p(n-1)-1)
                    #. nthprime is 0-indexed
}                   #. Trailing bracket is optional in this case
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 4 bytes

ÎF<Ø

Try it online!

Explanation

ÎF<Ø
Î    # Push 0 and input
 F   # Do input times...
  <   # Decrement
   Ø  # Get the nth prime (0-indexed) with n being the top of the stack
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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