2
$\begingroup$

Let $A$ be a set of prime numbers, generated by the following procedure. Let $A_0 = \{2\}$. Let $A_n$ be generated by setting $x_n = (\prod_{p_i \in A_{n-1}}p_i) + 1$, and adding all the prime factors of $x_n$ to $A_{n-1}$. Let $A=\bigcup_{n\in \mathbb{N}} A_n$.

Clearly, $A$ does not contain all primes. Is there any other way to characterize the elements of $A$? What's the computational complexity of determining whether a prime belongs to $A$? What's the density of $A$ in the set of primes?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Why do you say that $A$ "clearly" does not contain all primes? I'm pretty sure that that is a long-standing open problem. Similarly if you adjoin to $A_{n-1}$ only the smallest prime dividing $x_n$, which is maybe more in the spirit of Euclid's original proof that there are infinitely many primes. $\endgroup$
    – Joe Silverman
    Commented Jan 22, 2019 at 3:23
  • 1
    $\begingroup$ Maybe this is a bit of a tangent, but is any purpose served by writing $\left( \prod_{p_i \, \in \, A_{n-1}} p_i \right) + 1$ instead of $\left( \prod_{p \, \in \, A_{n-1}} p \right) + 1 \text{ ?} \qquad$ $\endgroup$
    – Michael Hardy
    Commented Jan 22, 2019 at 4:10
  • 1
    $\begingroup$ This sequence may be oeis.org/A126263 $\endgroup$
    – Gerry Myerson
    Commented Jan 22, 2019 at 11:29

1 Answer 1

Reset to default
3
$\begingroup$

The related problem where only the minimum prime divisor of $x_n$ is added to the list $A_{n-1}$ is open as pointed out by @JoeSilverman. This sequence of primes is called the Euclid-Mullin sequence. See the following links:

https://math.stackexchange.com/questions/272958/are-all-primes-euclid-primes

OEIS link

Now, your sequence has more members than the Euclid-Mullin sequence. Thus it would be at least as hard, if not harder, to prove that some prime is missing in your sequence, given that no one has been able to prove that such a prime is missing in theEuclid-Mullin sequence.

Edit: Thanks to Francois Brunault for pointing out that containment is needed for the above claim to hold. The difficulty of your problem is possibly still similar to Euclid-Mullin. Thanks to Greg Martin for the further reference.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The Euclid-Mullin sequence is not a priori contained in the sequence in the OP, because $x_n$ is not the same. $\endgroup$
    – François Brunault
    Commented Jan 22, 2019 at 7:01
  • 2
    $\begingroup$ See also Section 5 and beyond of this paper of Booker and Pomerance, as well as the references it describes at the end of the introduction. $\endgroup$
    – Greg Martin
    Commented Jan 22, 2019 at 7:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .