25
\$\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\$
0

16 Answers 16

15
\$\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\$
9
\$\begingroup\$

Mathematica, 16 bytes

Nest[Prime,1,#]&

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

\$\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\$
6
\$\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\$
3
  • \$\begingroup\$ You don't need the . \$\endgroup\$
    – Dennis
    Feb 21, 2017 at 18:57
  • \$\begingroup\$ @Dennis So does ¡ only accept nilads as repetitions and default to input if none are found? \$\endgroup\$ Feb 21, 2017 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, 2017 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\$
4
  • 1
    \$\begingroup\$ You can shave a little off by doing a<-ifelse(m==0,j,f(m-1,j)) \$\endgroup\$
    – smci
    Feb 22, 2017 at 0:31
  • 1
    \$\begingroup\$ 74 bytes \$\endgroup\$
    – Giuseppe
    Oct 7, 2017 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\$ Oct 7, 2017 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, 2017 at 22:01
3
\$\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\$
3
\$\begingroup\$

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
\$\endgroup\$
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\$
2
+100
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ may help with making this shorter. \$\endgroup\$
    – Razetime
    Dec 24, 2020 at 2:32
  • \$\begingroup\$ @Razetime I did try that, but it appears to be the same length. I wish it used a positive number instead of -2 :( \$\endgroup\$
    – user
    Dec 24, 2020 at 15:10
  • 1
    \$\begingroup\$ Hm, that would be a good idea, but it would mess with older solutions. Let's ask about it in the orchard. \$\endgroup\$
    – Razetime
    Dec 24, 2020 at 17:48
  • 1
    \$\begingroup\$ Full program. \$\endgroup\$
    – Adám
    Mar 10, 2021 at 6:46
  • \$\begingroup\$ @Adám Thanks, I didn't think of making a tradfn! \$\endgroup\$
    – user
    Mar 10, 2021 at 16:29
2
\$\begingroup\$

Vyxal, 5 bytes

1$(‹ǎ

Try it Online!

1$    # Push 1 and the input
  (   # Input times
   ‹ǎ # Decrement and get nth prime
\$\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\$
1
\$\begingroup\$

Husk, 10 bytes

?K2ȯ!İp₀←ε

Try it online!

A recursive function.

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

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.
\$\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\$

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.