26
\$\begingroup\$

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

17 Answers 17

10
\$\begingroup\$

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

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ (,0({q:)1+*/)^: for 15 bytes, returning the sequence up to n (zero-indexed) \$\endgroup\$ – miles Sep 5 at 9:20
  • \$\begingroup\$ @miles Thank you! \$\endgroup\$ – Galen Ivanov Sep 5 at 9:24
  • \$\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 Sep 6 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 Sep 8 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 Sep 8 at 23:45
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I just started with Python, but do you need int(input()) otherwise i is a str? \$\endgroup\$ – Anthony Sep 5 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 Sep 5 at 15:48
  • \$\begingroup\$ How does this terminate after n steps? \$\endgroup\$ – sintax Sep 6 at 20:12
  • \$\begingroup\$ @sintax it outputs the sequence for a given p1 indefinitely, as allowed by the default sequence rules. \$\endgroup\$ – ovs Sep 6 at 22:29
4
\$\begingroup\$

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

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)
\$\endgroup\$
  • \$\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 Sep 5 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 Sep 5 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 Sep 5 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 Sep 5 at 8:33
3
\$\begingroup\$

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

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.

\$\endgroup\$
2
\$\begingroup\$

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

bash +GNU coreutils, 89 bytes

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

TIO

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – Value Ink Sep 5 at 21:21
2
+100
\$\begingroup\$

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

Pari/GP, 47 bytes

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

Try it online!

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

Stax, 9 bytes

é|G╝╓c£¼_

Run and debug it

Takes p0 and (zero-indexed) n for input. Produces pn.

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

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

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ -+^[*](@_) saves a byte. \$\endgroup\$ – nwellnhof Sep 13 at 11:21
0
\$\begingroup\$

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