Euclid famously proved that the set of primes $P$ is infinite by showing that for any finite list of primes, you can multiply them together and add $1$ to get a number divisible by a prime not on the list. Naturally, this suggests a method of generating an infinite set of primes: start with a set of primes, multiply them all together and add $1$, add all primes that divide that new number to the set, and repeat.
Let's see what happens if we do this starting with the empty set. Define the sequence of sets $S_n$ by \begin{align} S_0 &= \emptyset \\ S_{n+1} &= S_n\cup\left\{p\in P: p \big | \left(1 +\prod S_{n}\right)\right\} \\ S_\omega &= \bigcup_{n\in \mathbb N} S_n. \end{align} We have $S_1 = \{2\}$, $S_2 = \{2,3\}$, $S_3 = \{2,3,7\}$, $S_4 = \{2,3,7,43\}$, $S_5 = \{2,3,7,13,43,149\}$, etc. While playing around with this, I came up with two questions:
- Is $S_\omega = P$?
- Is $5\notin S_\omega$?
Obviously a positive answer to one implies a negative answer to the other, but it could be the answer to both is no. In the last case, I'm curious what the properties of primes in $P\setminus S_\omega$ are.
One bit of progress I made is that if $1 +\prod S_{n}$ is squarefree, then the prime factors it adds to the list multiply out to itself, so $\prod S_{n+1} = (\prod S_{n})(1+\prod S_{n})$. A number of the form $n(n+1)$ cannot be $-1\mod 5$, so $5\in S_\omega$ requires $1+\prod S_n$ be divisible by a square for some $n$. The problem is that while it seems unlikely such a number would be divisible by a square, I'm not sure how to prove that.
In case you weren't aware, this is Sylvester's sequence (OEIS), or a variation thereof.
I didn't see it just now, but as I recall it is believed that Sylvester's likely includes every prime as you take that set to infinity; there is also a conjecture that the sequence is squarefree, but last I checked, that too remained an open question.