Infinitely many primes

Since Euclid, we have known that there are infinitely many primes. The argument is by contradiction: If there are only finitely many, let's say $$\p_1,p_2,...,p_n\$$, then surely $$\m:=p_1\cdot p_2\cdot...\cdot p_n+1\$$ is not divisible by any of these primes, so its prime factorization must yield a new prime that was not in the list. So the assumption that only finitely primes exist is false.

Now let's assume that $$\2\$$ is the only prime. The method from above yields $$\2+1=3\$$ as a new (possible) prime. Applying the method again yields $$\2\cdot 3+1=7\$$, and then $$\2\cdot 3\cdot 7+1=43\$$, then $$\2\cdot 3\cdot 7\cdot 43+1=13\cdot 139\$$, so both $$\13\$$ and $$\139\$$ are new primes, etc. In the case where we get a composite number, we just take the least new prime. This results in A000945.

Challenge

Given a prime $$\p_1\$$ and an integer $$\n\$$ calculate the $$\n\$$-th term $$\p_n\$$ of the sequence defined as follows:

$$p_n := \min(\operatorname{primefactors}(p_1\cdot p_2\cdot ... \cdot p_{n-1} + 1))$$

These sequences are known as Euclid-Mullin-sequences.

Examples

For $$\p_1 = 2\$$:

1 2
2 3
3 7
4 43
5 13
6 53
7 5
8 6221671
9 38709183810571


For $$\p_1 = 5\$$ (A051308):

1 5
2 2
3 11
4 3
5 331
6 19
7 199
8 53
9 21888927391


For $$\p_1 = 97\$$ (A051330)

1 97
2 2
3 3
4 11
5 19
6 7
7 461
8 719
9 5


JavaScript (ES6),  45  44 bytes

Takes input as (n)(p1), where $$\n\$$ is 0-indexed.

n=>g=(p,d=2)=>n?~p%d?g(p,d+1):--n?g(p*d):d:p


Try it online!

Commented

n =>                // n = 0-based index of the requested term
g = (             // g is a recursive function taking:
p,              //   p = current prime product
d = 2           //   d = current divisor
) =>              //
n ?             // if n is not equal to 0:
~p % d ?      //   if d is not a divisor of ~p (i.e. not a divisor of p + 1):
g(p, d + 1) //     increment d until it is
:             //   else:
--n ?       //     decrement n; if it's still not equal to 0:
g(p * d)  //       do a recursive call with the updated prime product
:           //     else:
d         //       stop recursion and return d
:               // else:
p             //   don't do any recursion and return p right away


05AB1E, 6 bytes

This produces and infinite output stream.

λλP>fW


Try it online! (link includes a slightly modified version, λ£λP>fW, which instead outputs the first $$\n\$$ terms)

Explanation

Very straightforward. Given $$\p_1\$$ and $$\n\$$, the program does the following:

• Starts with $$\p_1\$$ as an initial parameter for the infinite stream (which is generated using the first λ) and begins a recursive environment which generates a new term after each interation and appends it to the stream.
• The second λ, now being used inside the recursive environment, changes its functionality: Now, it retrieves all previously generated elements (i.e. the list $$\[\lambda_0, \lambda_1, \lambda_2, \ldots, \lambda_{n-1}]\$$), where $$\n\$$ represents the current iteration number.
• The rest is trivial: P takes the product ($$\\lambda_0\lambda_1\lambda_2 \cdots \lambda_{n-1}\$$), > adds one to this product, and fW retrieves the minimum prime factor.

J, 15 bytes

-10 bytes thanks to miles!

Returning the sequence up to n (zero-indexed) – thanks to @miles

(,0({q:)1+*/)^:


Try it online!

J, 25 bytes

Returns the n th item

_2{((],0{[:q:1+*/@])^:[])


Try it online!

• (,0({q:)1+*/)^: for 15 bytes, returning the sequence up to n (zero-indexed) – miles Sep 5 '19 at 9:20
• @miles Thank you! – Galen Ivanov Sep 5 '19 at 9:24
• Very nice. @miles what exactly is happening there grammatically? we put a verb and a conjunction together and get a dyadic verb back. I thought verb conj produced an adverb. – Jonah Sep 6 '19 at 1:43
• @Jonah it's a trick I learned from golfing. I think it's one of the older parsing rules that's still valid – miles Sep 8 '19 at 22:08
• @miles I just realized it is an adverb (or adnoun). It modifies the noun to its left, which "attaches" to the right of the ^:, and then that becomes a verb that applies to the right arg. I think that's what's happening grammatically. – Jonah Sep 8 '19 at 23:45

Python 2, 56 bytes

i=input();k=1
while 1:
k*=i;print i;i=2
while~k%i:i+=1


Try it online!

Commented

i=input() # the initial prime
k=1       # the product of all previous primes
while 1:  # infinite loop
k*=i     # update the product of primes
print i  # output the last prime
i=2      # starting at two ...
while~k%i: # find the lowest number that divides k+1
i+=1
# this our new prime


Try it online!

• I just started with Python, but do you need int(input()) otherwise i is a str? – Anthony Sep 5 '19 at 15:37
• In Python 3 this would be true as input() always returns strings. In Python 2 input() tries to evaluate the input. I'm using Python 2 in this case because the resulting code is slightly shorter. For real code you should try to use Python 3 as it is the newer and more supported version of Python. – ovs Sep 5 '19 at 15:48
• How does this terminate after n steps? – sintax Sep 6 '19 at 20:12
• @sintax it outputs the sequence for a given p1 indefinitely, as allowed by the default sequence rules. – ovs Sep 6 '19 at 22:29

Jelly, 8 bytes

P‘ÆfṂṭµ¡


A full program (using zero indexing) accepting $$\P_0\$$ and $$\n\$$ which prints a Jelly representation of the list of $$\P_0\$$ to $$\P_n\$$ inclusive. (As a dyadic Link, with n=0 we'll be given back an integer, not a list.)

Try it online!

How?

P‘ÆfṂṭµ¡ - Link: integer, p0; integer n
µ¡ - repeat the monadic chain to the left n times, starting with x=p0:
P        -   product of x (p0->p0 or [p0,...,pm]->pm*...*p0)
‘       -   increment
Æf     -   prime factors
Ṃ    -   minimum
ṭ   -   tack
- implicit print


05AB1E, 8 bytes

GDˆ¯P>fß


First input is $$\n\$$, second is prime $$\p\$$.

Try it online or very some more test cases (test suite lacks the test cases for $$\n\geq9\$$, because for $$\p=2\$$ and $$\p=5\$$ the builtin f takes too long).

Explanation:

G         # Loop (implicit input) n-1 amount of times:
Dˆ       #  Add a copy of the number at the top of the stack to the global array
#  (which will take the second input p implicitly the first iteration)
¯      #  Push the entire global array
P     #  Take the product of this list
>    #  Increase it by 1
f   #  Get the prime factors of this number (without counting duplicates)
ß  #  Pop and only leave the smallest prime factor
# (after the loop: implicitly output the top of the stack as result)

• I had λλP>fW (6 bytes) with output as an infinite list and λ£λP>fW (7 bytes) for the first $n$ terms. However getting the $n^{\text{th}}$ should be 9 bytes... If only we had a flag like £ but for the last element! – Mr. Xcoder Sep 5 '19 at 8:21
• @Mr.Xcoder "If only we had a flag like £ but for the last element!", like .£? ;) EDIT: Actually, it doesn't work exactly like £ for lists.. using a list like [1,2] with .£ results in two loose items with the last 1 and 2 items (i.e. 12345 becomes [5,45] instead of [45,3] or [3,45], with 12S.£).. – Kevin Cruijssen Sep 5 '19 at 8:27
• Umm, no, I don't see how λ.£ should work. I used flag as in additional function associated with λ (see this conversation with Adnan). I basically want some flag è such that when running λè...} it would generate the n-th element rather than the the infinite stream (just like λ£ would work for generating the first n elements). – Mr. Xcoder Sep 5 '19 at 8:31
• @Mr.Xcoder Ah sorry, you've used the £ for the recursive environment. Yeah, then λ.£ is indeed not gonna work, my bad. Nice 6-byter regardless. Now you just have to wait for @flawr's response whether it's allowed or not (it probably is). – Kevin Cruijssen Sep 5 '19 at 8:33

Japt, 12 11 bytes

Struggled to get this one right so may have missed something that can be golfed.

Takes n as the first input and p1, as a singleton array, as the second. Returns the first n terms. Change h to g to return the nth 0-indexed term instead.

@Z×Ä k Î}hV


Try it

@Z×Ä k Î}hV     :Implicit input of integer U=n & array V=[p1]
@               :Function taking an array as an argument via parameter Z
Z×             :  Reduce Z by multiplication
Ä            :  Add 1
k          :  Prime factors
Î        :  First element
}       :End function
hV     :Run that function, passing V as Z, and
: push the result to V.
: Repeat until V is of length U


Retina, 56 bytes

,|*
"$&"{~.+¶ $$¶_ )\b(__+?)\1* .1* 1A . \* ,  Try it online! Takes input as the number of new terms to add on the first line and the seed term(s) on the second line. Note: Gets very slow since it uses unary factorisation so it needs to create a string of the relevant length. Explanation: ,| *  Replace the commas in the seed terms with *s and append a *. This creates a Retina expression for a string of length of the product of the values. "&"{ )  Repeat the loop the number of times given by the first input. ~.+¶$$¶_  Temporarily replace the number on the first line with a $ and prepend a _ to the second line, then evaluate the result as a Retina program, thus appending a string of _s of length 1 more than the product of the values.

\b(__+?)\1*.1$*  Find the smallest nontrivial factor of the number in decimal and append a * ready for the next loop. 1A  Delete the iteration input. .$


Delete the last *.

\*
,


Replace the remaining *s with ,s.

JavaScript (Node.js), 54 bytes

f=(p,n,P=p,F=n=>-~P%n?F(n+1):n)=>--n?f(p=F(2),n,P*p):p


Try it online!

Ungolfed

F=(p,n=2)=>            // Helper function F for finding the smallest prime factor
p%n                  //   If n (starting at 2) doesn't divide p:
?F(n+1)            //     Test n+1 instead
:n                 //   Otherwise, return n
f=(p,n,P=p)=>          // Main function f:
--n                  //   Repeat n - 1 times:
?f(p=F(P+1),n,P*p) //     Find the next prime factor and update the product
:p                 //   Return the last prime


IFS=\*;n=$1;shift;for((;++i<n;));{ set$@ factor $["$*+1"]|cut -d\  -f2;};echo ${@: -1}  TIO Ruby 2.6, 51 bytes f=->s,n{[s,l=(2..).find{|d|~s%d<1}][n]||f[l*s,n-1]}  (2..), the infinite range starting from 2, isn't supported on TIO yet. This is a recursive function that takes a starting value s (can be a prime or composite), returns it when n=0 (edit: note that this means it's zero-indexed), returns the least number l that's greater than 1 and divides -(s+1) when n=1, and otherwise recurses with s=l*s and n=n-1. • You should probably mention that you're doing zero-indexed; I replaced (2..) with 2.step (just 1 byte longer) to allow it to work on TIO and everything was off by one. Try it online! – Value Ink Sep 5 '19 at 21:21 APL (Dyalog Extended), 15 bytes This is a fairly simple implementation of the algorithm which uses Extended's very helpful prime factors builtin, ⍭. Try it online! {⍵,⊃⍭1+×/⍵}⍣⎕⊢⎕  Explanation {⍵,⊃⍭1+×/⍵}⍣⎕⊢⎕ ⊢⎕ First get the first prime of the sequence S from input. { }⍣⎕ Then we repeat the code another input number of times. 1+×/⍵ We take the product of S and add 1. ⍭ Get the prime factors of product(S)+1. ⊃ Get the first element, the smallest prime factor of prod(S)+1. ⍵, And append it to S.  Pari/GP, 47 bytes (p,n)->s=1;for(i=2,n,s*=p;p=divisors(s+1)[2]);p  Try it online! Stax, 9 bytes é|G╝╓c£¼_  Run and debug it Takes p0 and (zero-indexed) n for input. Produces pn. C (gcc), 54 53 bytes p;f(x,n){for(p=x;--n;p*=x)for(x=1;~p%++x;);return x;}  Try it online! -1 byte thanks to ceilingcat Perl 6, 33 32 bytes -1 byte thanks to nwellnhof {$_,{1+(2...-+^[*](@_)%%*)}...*}


Try it online!

Anonymous code block that takes a number and returns a lazy list.

Explanation:

{                              }  # Anonymous codeblock
...*   # That returns an infinite list
\$_,                              # Starting with the input
{                     }       # Where each element is
1+(2...             )          # The first number above 2
%%*           # That cleanly divides
[*](@_)                # The product of all numbers so far
-+^                       # Plus one


Haskell, 49 bytes

g 1
g a b=b:g(a*b)([c|c<-[2..],1>mod(a*b+1)c]!!0)


Try it online!

Returns the infinite sequence as a lazy list.

Explanation:

g 1                                            -- Initialise the product as 1
g a b=                                         -- Given the product and the current number
b:                                      -- Return the current number, followed by
g                                     -- Recursively calliong the function with
(a*b)                                -- The new product
(                             ) -- And get the next number as
[c|c<-[2..],             ]!!0  -- The first number above 2
1>mod       c      -- That cleanly divides
(a*b+1)       -- The product plus one