5
$\begingroup$

I've thought of the following algorithm to find the entire list of prime numbers:

Take a prime number $p$ to your list.

$1.$ Multiply all the numbers in your list and call the number you get $P$.

$2.$ Add the new primes that divide $P+1$ to your list.

Repeat ad infinitum.

The question is:

For which $p$ (if any) will this algorithm create a list of all the prime numbers?

$\endgroup$
  • 1
    $\begingroup$ Starting with $p=2$ looks as though $5$ is skipped for a while, along with $11...41$ at least initially $\endgroup$ – abiessu Sep 30 '14 at 15:43
  • $\begingroup$ @abiessu I feel that this whole question is a bit too difficult to ask here, but it'll suffice to answer some part of this question, or a special case, or show that this is an open problem, etc. Anything that is known about something similar to this. $\endgroup$ – user26486 Sep 30 '14 at 15:46
  • 1
    $\begingroup$ As an algorithm, it's hopelessly, stupendously inefficient. (But the question is a good one.) $\endgroup$ – TonyK Sep 30 '14 at 16:20
  • 1
    $\begingroup$ @DanUznanski Well, the Euclid-Mullin sequence isn't created by the same algorithm I've shown here. It only takes into account the least prime number that divides $P$. If it were the least 'not in the list' prime divisor, then it'd be a proof, but now it doesn't seem to be one. $\endgroup$ – user26486 Sep 30 '14 at 17:01
  • 1
    $\begingroup$ See oeis.org/A126263 for this sequence starting with 2 (or 3, if you flip the first two terms, or 7 if you rearrange the first three terms, etc.). $\endgroup$ – Charles Oct 2 '14 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.