# Euclides' sieve

This is probably a well-known problem. Given a set or multiset of natural numbers let us construct its "Euclides" closure: on each step we take all possible products $P_i$ of the elements in the set, and add to the set those of $P_i+1$ who are primes. The question is whether this closure is finite or not.

For example, if we take $\{1\}$ as the initial set, then we add $2=1+1$, then we add $3=2+1$, then we add $7=2\cdot 3+1$, then we add $2\cdot 3\cdot 7+1=43$ and that is all. All other products of the elements of $\{1,2,3,7,43\}$, increased by 1 are composite numbers.

But if we start with the multiset $\{2,2\}$ then computations are much harder. We add $3=2+1,5=2\cdot2+1, 7=2\cdot3+1,11=2\cdot5+1,13=2\cdot2\cdot3+1,23=2\cdot 11+1$ and many many others.

Is "Euclides'"closure of $\{2,2\}$ finite?

Equivalent question: does there exist a positive integer $n$ such that whenever $p-1$ divides $4n$ for a prime number $p$, $p$ itself divides $2 n$.

• Starting from the multiset $\{2,2\}$, do you add $3$ to the multiset twice or just once? – Greg Martin Apr 13 '18 at 19:24
• I'm not convinced that the "equivalent question" is actually equivalent. Some data though: starting with $\{2,3,5\}$ (which is a subset of the $\{2,2,3,5\}$ that is one step after $\{2,2\}$), after only three iterations one has a set with over 10,000 elements, the largest of which has 34 digits. – Greg Martin Apr 13 '18 at 19:31
• @GregMartin, we add each element only once. Thank you for the data! I did not compute so many numbers, but still, it seems that the set is infinite... Concerning the equivalent question: If such a set is finite, take n= the product of all odd primes in it. – Nikita Kalinin Apr 13 '18 at 21:13
• Greg, each prime other than 2 is added only once. – Fedor Petrov Apr 14 '18 at 10:25