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?

$\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 Jan 22 '19 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 Jan 22 '19 at 4:10
  • 1
    $\begingroup$ This sequence may be oeis.org/A126263 $\endgroup$ – Gerry Myerson Jan 22 '19 at 11:29
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.

$\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 Jan 22 '19 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 Jan 22 '19 at 7:13

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.