Find Recursively Prime Primes

Question

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 code-golf 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

Adnan · Accepted Answer · 2017-02-21 18:32:52Z

16

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!

edited Feb 21, 2017 at 18:32

answered Feb 21, 2017 at 18:24

Adnan

44.5k6 gold badges82 silver badges246 bronze badges

Add a comment |

LegionMammal978 · Accepted Answer · 2017-02-21 18:23:26Z

10

Mathematica, 16 bytes

Nest[Prime,1,#]&

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

answered Feb 21, 2017 at 18:23

LegionMammal978

18k4 gold badges25 silver badges57 bronze badges

Add a comment |

user45941user45941 · Accepted Answer · 2017-02-21 18:21:55Z

8

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

answered Feb 21, 2017 at 18:21

user45941

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

6

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 21, 2017 at 18:45

PurkkaKoodari

17.9k2 gold badges35 silver badges91 bronze badges

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

Add a comment |

ETHproductions · Accepted Answer · 2017-02-21 19:21:22Z

5

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.

edited Feb 21, 2017 at 19:21

answered Feb 21, 2017 at 19:13

ETHproductions

50.1k6 gold badges94 silver badges240 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

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)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 21, 2017 at 18:38

Luis Mendo

105k9 gold badges135 silver badges372 bronze badges

Add a comment |

Joseph Wood · Accepted Answer · 2017-02-22 01:28:53Z

3

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

edited Feb 22, 2017 at 1:28

answered Feb 21, 2017 at 20:49

Joseph Wood

2011 silver badge4 bronze badges

1

\$\begingroup\$ You can shave a little off by doing a<-ifelse(m==0,j,f(m-1,j)) \$\endgroup\$
– smci
Commented Feb 22, 2017 at 0:31
1

\$\begingroup\$ 74 bytes \$\endgroup\$
– Giuseppe
Commented 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\$
– Joseph Wood
Commented 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
Commented Oct 7, 2017 at 22:01

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 7, 2017 at 19:20

Datboi

1,3058 silver badges9 bronze badges

Add a comment |

user · Accepted Answer · 2020-11-08 17:20:52Z

3

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

answered Nov 8, 2020 at 17:20

user

3872 gold badges21 silver badges68 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 21, 2017 at 21:05

Digital Trauma

73k9 gold badges112 silver badges264 bronze badges

Add a comment |

user · Accepted Answer · 2021-03-10 16:31:43Z

2

+100

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.

edited Mar 10, 2021 at 16:31

answered Dec 23, 2020 at 20:23

user

3872 gold badges21 silver badges68 bronze badges

\$\begingroup\$ ⍭ may help with making this shorter. \$\endgroup\$
– Razetime
Commented 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
Commented 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
Commented Dec 24, 2020 at 17:48
1

\$\begingroup\$ Full program. \$\endgroup\$
– Adám
Commented Mar 10, 2021 at 6:46
\$\begingroup\$ @Adám Thanks, I didn't think of making a tradfn! \$\endgroup\$
– user
Commented Mar 10, 2021 at 16:29

Add a comment |

emanresu A · Accepted Answer · 2022-01-09 01:20:52Z

2

Vyxal, 5 bytes

1$(‹ǎ

Try it Online!

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

answered Jan 9, 2022 at 1:20

emanresu A

44.2k5 gold badges100 silver badges240 bronze badges

Add a comment |

chunes · Accepted Answer · 2022-01-09 02:04:28Z

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.

SEJPM · Accepted Answer · 2017-10-07 17:10:20Z

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

Razetime · Accepted Answer · 2020-10-10 14:49:38Z

1

Husk, 10 bytes

?K2ȯ!İp₀←ε

Try it online!

A recursive function.

answered Oct 10, 2020 at 14:49

Razetime

27.4k3 gold badges29 silver badges72 bronze badges

Add a comment |

Jordan · Accepted Answer · 2024-03-02 18:46:14Z

J-uby, 33 bytes

~(:-&(:**&(:take&Prime|:last)))&1

Attempt This Online!

Explanation

~(:- & (:** & (:take & Prime | :last))) & 1⁡‎⁪⁪⁠⁪⁪⁠‎⁪⁡⁪⁠⁪⁤⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁤⁪‏‏⁡⁠⁡‌⁢‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁣⁪‏‏⁡⁠⁡‌
               :take & Prime | :last         # ‎⁡nth prime
~(:- & (:** & (                     ))) & 1  # ‎⁢Apply to 1 input times
💎

Created with the help of Luminespire.

Mama Fun Roll · Accepted Answer · 2017-02-22 04:24:34Z

0

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

answered Feb 22, 2017 at 4:24

Mama Fun Roll

9,9281 gold badge36 silver badges46 bronze badges

Add a comment |

Mukundan314 · Accepted Answer · 2024-02-27 16:17:39Z

0

Python 3, 85 bytes

p=lambda x:[i for i in range(2,5*x**x)if all(i%j for j in range(2,i))][x and~-p(x-1)]

Try it online!

Uses 0-indexing.

answered Feb 27 at 16:17

Mukundan314

12.7k1 gold badge16 silver badges58 bronze badges

Add a comment |

138 Aspen · Accepted Answer · 2024-02-29 12:28:58Z

0

PARI/GP, 34 bytes

f(n)={r=1;for(i=1,n,r=prime(r));r}

Attempt This Online!

answered Feb 29 at 12:28

138 Aspen

6,6171 gold badge4 silver badges13 bronze badges

Add a comment |

Stack Exchange Network

Find Recursively Prime Primes

Test Cases

19 Answers 19

Oasis, 3 bytes

Mathematica, 16 bytes

Actually, 7 bytes

Jelly, 5 4 bytes

Explanation

JavaScript (ES6), 71 bytes

MATL, 6 bytes

Explanation

R, 98 93 bytes

05AB1E, 4 bytes

Explanation

Husk, 6 bytes

Bash + common utilities, 55

Bash + common utilities, 58

APL (Dyalog Extended), 10 8 bytes

Another previous solution, 10 bytes

Vyxal, 5 bytes

Factor + `math.primes.lists`, 57 bytes

Explanation

Haskell, 58 bytes

Husk, 10 bytes

J-uby, 33 bytes

Explanation

Wonder, 23 bytes

Explanation

Python 3, 85 bytes

PARI/GP, 34 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
primes
integer
or ask your own question.

Linked

Hot Network Questions

Find Recursively Prime Primes

Test Cases

19 Answers 19

Oasis, 3 bytes

Mathematica, 16 bytes

Actually, 7 bytes

Jelly, 5 4 bytes

Explanation

JavaScript (ES6), 71 bytes

MATL, 6 bytes

Explanation

R, 98 93 bytes

05AB1E, 4 bytes

Explanation

Husk, 6 bytes

Bash + common utilities, 55

Bash + common utilities, 58

APL (Dyalog Extended), 10 8 bytes

Another previous solution, 10 bytes

Vyxal, 5 bytes

Factor + math.primes.lists, 57 bytes

Explanation

Haskell, 58 bytes

Husk, 10 bytes

J-uby, 33 bytes

Explanation

Wonder, 23 bytes

Explanation

Python 3, 85 bytes

PARI/GP, 34 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Factor + `math.primes.lists`, 57 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
primes
integer
or ask your own question.