Infinitely many primes

Question

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

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

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

Michael Hardy · Accepted Answer · 2019-09-07 17:16:02Z

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.

Galen Ivanov · Accepted Answer · 2019-09-05 09:23:40Z

6

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!

edited Sep 5, 2019 at 9:23

answered Sep 5, 2019 at 9:06

Galen Ivanov

21.5k3 gold badges26 silver badges62 bronze badges

1

\$\begingroup\$ (,0({q:)1+*/)^: for 15 bytes, returning the sequence up to n (zero-indexed) \$\endgroup\$

miles
– miles

2019-09-05 09:20:36 +00:00
Commented Sep 5, 2019 at 9:20
\$\begingroup\$ 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. \$\endgroup\$

Jonah
– Jonah

2019-09-06 01:43:58 +00:00
Commented Sep 6, 2019 at 1:43
1

\$\begingroup\$ @Jonah it's a trick I learned from golfing. I think it's one of the older parsing rules that's still valid \$\endgroup\$

miles
– miles

2019-09-08 22:08:27 +00:00
Commented Sep 8, 2019 at 22:08
\$\begingroup\$ @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. \$\endgroup\$

Jonah
– Jonah

2019-09-08 23:45:49 +00:00
Commented Sep 8, 2019 at 23:45

Add a comment |

ovs · Accepted Answer · 2019-09-05 18:27:00Z

5

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!

edited Sep 5, 2019 at 18:27

answered Sep 5, 2019 at 9:05

ovs

61.2k3 gold badges49 silver badges164 bronze badges

\$\begingroup\$ I just started with Python, but do you need int(input()) otherwise i is a str? \$\endgroup\$

Anthony
– Anthony

2019-09-05 15:37:36 +00:00
Commented Sep 5, 2019 at 15:37
2

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

ovs
– ovs

2019-09-05 15:48:17 +00:00
Commented Sep 5, 2019 at 15:48
\$\begingroup\$ How does this terminate after n steps? \$\endgroup\$

sintax
– sintax

2019-09-06 20:12:10 +00:00
Commented Sep 6, 2019 at 20:12
\$\begingroup\$ @sintax it outputs the sequence for a given p1 indefinitely, as allowed by the default sequence rules. \$\endgroup\$

ovs
– ovs

2019-09-06 22:29:14 +00:00
Commented Sep 6, 2019 at 22:29

Add a comment |

Jonathan Allan · Accepted Answer · 2019-09-05 12:02:14Z

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

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

3

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)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Sep 5, 2019 at 7:58

Kevin Cruijssen

136k14 gold badges155 silver badges394 bronze badges

\$\begingroup\$ 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! \$\endgroup\$

Mr. Xcoder
– Mr. Xcoder

2019-09-05 08:21:41 +00:00
Commented Sep 5, 2019 at 8:21
\$\begingroup\$ @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.£).. \$\endgroup\$

Kevin Cruijssen
– Kevin Cruijssen

2019-09-05 08:27:47 +00:00
Commented Sep 5, 2019 at 8:27
\$\begingroup\$ 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). \$\endgroup\$

Mr. Xcoder
– Mr. Xcoder

2019-09-05 08:31:39 +00:00
Commented Sep 5, 2019 at 8:31
\$\begingroup\$ @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). \$\endgroup\$

Kevin Cruijssen
– Kevin Cruijssen

2019-09-05 08:33:56 +00:00
Commented Sep 5, 2019 at 8:33

Add a comment |

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

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

Neil · Accepted Answer · 2019-09-06 09:22:38Z

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.

Endenite · Accepted Answer · 2019-09-05 08:13:55Z

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

Nahuel Fouilleul · Accepted Answer · 2019-09-05 09:19:34Z

2

bash +GNU coreutils, 89 bytes

IFS=\*;n=$1;shift;for((;++i<n;));{ set $@ `factor $["$*+1"]|cut -d\ -f2`;};echo ${@: -1}

TIO

edited Sep 5, 2019 at 9:19

answered Sep 5, 2019 at 8:19

Nahuel Fouilleul

8,6571 gold badge11 silver badges19 bronze badges

Add a comment |

histocrat · Accepted Answer · 2019-09-05 22:14:41Z

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
– Value Ink, Commented Sep 5, 2019 at 21:21

Sherlock9 · Accepted Answer · 2019-09-09 01:50:11Z

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.

recursive · Accepted Answer · 2019-09-05 17:27:35Z

1

Stax, 9 bytes

é|G╝╓c£¼_

Run and debug it

Takes p₀ and (zero-indexed) n for input. Produces p_n.

answered Sep 5, 2019 at 17:27

recursive

10.5k21 silver badges36 bronze badges

Add a comment |

wastl · Accepted Answer · 2019-09-08 18:34:32Z

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

Jo King · Accepted Answer · 2019-09-13 11:32:15Z

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

alephalpha · Accepted Answer · 2022-04-14 11:25:16Z

1

Pari/GP, 45 bytes

(p,n)->s=p;for(i=2,n,s*=p=divisors(s+1)[2]);p

Try it online!

edited Apr 14, 2022 at 11:25

answered Sep 5, 2019 at 13:03

alephalpha

51.9k7 gold badges75 silver badges196 bronze badges

Add a comment |

Jo King · Accepted Answer · 2019-09-13 12:17:10Z

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

Dominic van Essen · Accepted Answer · 2022-04-14 16:42:16Z

Husk, 8 bytes

!¡ö←p→Π;

Try it online!

For input m,n outputs the n-th term in the sequence starting with m.

Drop the initial ! (for 7 bytes) to output the entire infinite sequence (this link selects the first 10 elements from the infinite list).
If both input & output are flexible enough (input: list of just the first term, output: infinite sequence) we could get down to 6 bytes.

Stack Exchange Network

Infinitely many primes

Challenge

Examples

18 Answers 18

JavaScript (ES6), 45 44 bytes

Commented

05AB1E, 6 bytes

Explanation

J, 15 bytes

J, 25 bytes

Python 2, 56 bytes

Commented

Jelly, 8 bytes

How?

05AB1E, 8 bytes

Japt, 12 11 bytes

Retina, 56 bytes

JavaScript (Node.js), 54 bytes

bash +GNU coreutils, 89 bytes

Ruby 2.6, 51 bytes

APL (Dyalog Extended), 15 bytes

Stax, 9 bytes

C (gcc), 54 53 bytes

Perl 6, 33 32 bytes

Explanation:

Pari/GP, 45 bytes

Haskell, 49 bytes

Explanation:

Husk, 8 bytes

Hot Network Questions

Infinitely many primes

Challenge

Examples

18 Answers 18

JavaScript (ES6), 45 44 bytes

Commented

05AB1E, 6 bytes

Explanation

J, 15 bytes

J, 25 bytes

Python 2, 56 bytes

Commented

Jelly, 8 bytes

How?

05AB1E, 8 bytes

Japt, 12 11 bytes

Retina, 56 bytes

JavaScript (Node.js), 54 bytes

bash +GNU coreutils, 89 bytes

Ruby 2.6, 51 bytes

APL (Dyalog Extended), 15 bytes

Stax, 9 bytes

C (gcc), 54 53 bytes

Perl 6, 33 32 bytes

Explanation:

Pari/GP, 45 bytes

Haskell, 49 bytes

Explanation:

Husk, 8 bytes

Related

Hot Network Questions