4
$\begingroup$

Let's say 2 is the only prime. But we add 1 to get 3, which is also prime, so there are two primes: 2 and 3. Multiply them and add 1 to get 7. So our set of primes is now 2, 3, 7. Multiply them and 1 to get 43, then multiply those and add 1 to get 13 and 139 (the prime factors of 1807).

To put it algebraically, start with $p = \{2\}$ and have $\mathcal{L} = 1$ represent the length of this set. Compute $$1 + \prod_{i = 1}^\mathcal{L} p_i,$$ determine its prime factors, append those to $p$ (or sort them into $p$ if you prefer) and increment $\mathcal{L}$ by the appropriate amount. Wash, rinse, repeat.

Surely it follows from Euclid's proof that there are infinitely many primes that each prime will eventually come up with this algorithm. It's just that some small primes will come up after a gazillion steps, while some largish primes will come up after only a few steps (e.g., 38709183810571, but I have yet to find 17 this way).

$\endgroup$
  • 3
    $\begingroup$ I don't see why Euclid guarantees that each prime will appear. Can you expand on that? $\endgroup$ – John Brevik Mar 6 '15 at 19:23
  • $\begingroup$ @JohnBrevik Maybe not as the smallest prime factor. When we get 1807, I say we add both 13 and 139 to the set $p$. If instead we "forget" 139 at this point, I have no idea when or if ever we would find it again. $\endgroup$ – Robert Soupe Mar 6 '15 at 19:49
  • 4
    $\begingroup$ A variant of this sequence is called the Euclid-Mullin sequence (we only append the smallest prime factor): see en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence and oeis.org/A000945. It's an open question whether every prime occurs this way, and according to Wikipedia the smallest prime that isn't known to occur this way is $41$. $\endgroup$ – Qiaochu Yuan Mar 6 '15 at 20:05
  • $\begingroup$ Unless and until you generate a product-plus-one number $P_n = 1 + \prod_{i = 1}^\mathcal{L} p_i$ that is not square-free, each $P_n \equiv 43 \bmod 84$ ($n>3$ obviously). Did you come across any repeated factors in your investigation of $P_n$ so far? $\endgroup$ – Joffan Mar 7 '15 at 18:22
  • 2
    $\begingroup$ What you're essentially looking for is the order primes appear in the factorization of numbers in Sylvester's sequence oeis.org/A000058 $1807$ gives us $13$ and $139$; $3263443$ is prime; $10650056950807$ gives us $547$, $607$, $1033$, $31051$; etc. $\endgroup$ – Bill Thomas Mar 7 '15 at 22:19
4
$\begingroup$

As Bill Thomas observes in the comments, this process is equivalent to computing successive terms of Sylvester's sequence and waiting for a prime to appear. So we have:

$a_0 = 2$

$a_n = a_{n-1}^2 - a_{n-1} + 1$

and for some prime $p$ we want to find the smallest $n$ with $a_n$ divisible by $p$, if one exists.

Now this sequence is eventually periodic mod $p$ and it can be easily computed mod $p$ by reducing at each step. All we have to do is iterate it until we find the cycle and then we can check if it ever equals $0$.

Trying this for some small primes I have found that $5$, $11$, $17$, $23$, and $29$ will never appear.

$\endgroup$
3
$\begingroup$

The smallest prime guaranteed never to appear is $5$, as simple modular arithmetic will confirm. The smallest one not known to appear is probably some prime greater than $97$, as I believe the first thirty or so primes have surely been tested with congruences.

The crucial difference between this sequence and the Euclid-Mullin sequence is that each prime factor is kept track of, not just the smallest of each successive number obtained by the multiply and add process. The upside of "forgetting" the larger prime factors is that the sequence does not grow as quickly and is thus slightly more manageable.

I looked up 2, 3, 7, 43, 13, 139 in the OEIS and found A126263. As a matter of fact, that entry was updated a couple of weeks ago. After $21430986826194127130578627950810640891005487$ and a prime much larger than that, Ray Chandler added $73$ to the B-file. Hans Havermann probably knows some other small primes appear at certain positions, but these are probably separated by primes much greater than $10^{10}$.

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