# Find Recursively Prime Primes

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

# 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!

# Mathematica, 16 bytes

Nest[Prime,1,#]&


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

# 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


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

• You don't need the ⁸. Feb 21, 2017 at 18:57
• @Dennis So does ¡ only accept nilads as repetitions and default to input if none are found? Feb 21, 2017 at 19:15
• <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. Feb 21, 2017 at 19:59

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

# 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)


# 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)
 127

f(10)        ### takes almost a minute... YIKES!!!
 648391

• You can shave a little off by doing a<-ifelse(m==0,j,f(m-1,j))
– smci
Feb 22, 2017 at 0:31
• 74 bytes Oct 7, 2017 at 19:23
• @Giuseppe, you should post that as an answer... that is a considerable decrease!!! I have never seen if used like that before... pretty cool!! Oct 7, 2017 at 21:11
• @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). Oct 7, 2017 at 22:01

# 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


# Husk, 6 bytes

!¡!İp2


Try it online!

Explanation:

!¡!İp2
¡           Make an infinite list by repeatedly applying a function
2       Starting with 2
İp        From the sequence of prime numbers
!          Get the element at the given index (the previous number in the sequence)
!            Get the element at index (implicit input) in that infinite list


# 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  # APL (Dyalog Extended), 10 8 bytes Saved 2 bytes thanks to Adám ⌂pco⍣⎕⊢1  Try it online! ⍣ applies the function ⌂pco (nth prime) to 1 n times (n is taken through STDIN (⎕)). ## Another previous solution, 10 bytes ⊢∘⌂pco/⍴∘2  Try it online! ⍴∘2 makes a vector of n 2's, then / reduces using the train ⊢∘⌂pco. ⊢ ignores its left argument, pco finds the nth prime, given n on the right. More generally, ⊢∘f/n⍴s applies f n-1 times to s. • ⍭ may help with making this shorter. Dec 24, 2020 at 2:32 • @Razetime I did try that, but it appears to be the same length. I wish it used a positive number instead of -2 :( – user Dec 24, 2020 at 15:10 • Hm, that would be a good idea, but it would mess with older solutions. Let's ask about it in the orchard. Dec 24, 2020 at 17:48 • Full program. – Adám Mar 10, 2021 at 6:46 • @Adám Thanks, I didn't think of making a tradfn! – user Mar 10, 2021 at 16:29 # Vyxal, 5 bytes 1$(‹ǎ


Try it Online!

1\$    # Push 1 and the input
(   # Input times
‹ǎ # Decrement and get nth prime


# 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


# Husk, 10 bytes

?K2ȯ!İp₀←ε


Try it online!

A recursive function.

# Factor + math.primes.lists, 57 bytes

: p ( m -- n ) [ 2 ] [ 1 - p 1 - lprimes lnth ] if-zero ;


Try it online!

## Explanation

Returns the 0-indexed member of the recursively-prime prime sequence.

• : p ( m -- n ) ... ; Start a new word definition named p with stack effect ( m -- n ), declaring it takes one thing from the data stack and leaves one thing on the data stack.
• [ 2 ] [ ... ] if-zero Is the input 0? Then return 2. Otherwise, do ....
• 1 - p Apply p to the input minus one.
• 1 - lprimes lnth Return the nth prime number.

# 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