16
$\begingroup$

It occured to me that the Sieve of Eratosthenes eventually generates the same prime numbers, independently of the ones chosen at the beginning. (We generally start with 2, but we could chose any finite set of integers >= 2, and it would still end up generating the same primes, after a "recalibrating" phase).

If I take 3 and 4 as my first primes, starting at 5:

  • 5 is prime,
  • 6 is not (twice 3),
  • 7 is prime,
  • 8 is not,
  • 9 is not,
  • 10 is not,
  • etc.

Eventually, I will find all the primes as if I had started with 2 only.

To me, it means that we can generate big prime numbers without any knowledge of their predecessors (until a certain point). If I want primes higher than 1000000, then I can generate them without any knowledge of primes under, say, 1000. (It may not be as effective computationnally, but I find this philosophically interesting.)

Is this result already known ?

Are there any known implications ?

Edit

The number from which we are assured to get the right primes again is after the square of the last missing natural prime.

That is, if I start with a seed set containing only the number 12, the highest missing natural prime is 11, so I'll end up having 121 as my last not-natural prime. Non-natural primes found are 12,14,15,16,18,20,21,22,25,27,33,35,49,55,77 and 121.

This is a bit better than what I thought at first (namely, as stated below, somewhere under the square of the highest seed).

Improve this question
$\endgroup$
8
  • $\begingroup$ If you start from something $>2$, then all powers of 2 will be left as primes. Do you wish to call them prime? :-) $\endgroup$
    – Wadim Zudilin
    Commented Jun 14, 2010 at 9:24
  • $\begingroup$ Nope let's say 8 is counted as a prime, then 16 is not anymore (twice 8). Then all the other powers of two are expressible as a certain number of 8's. $\endgroup$
    – glmxndr
    Commented Jun 14, 2010 at 9:41
  • 1
    $\begingroup$ For related results, check out the "math" part (Part II? I think Part I is pedagogy, Part II is math, and Part III is physics) of Sanjoy Mahajan's thesis. $\endgroup$
    – Theo Johnson-Freyd
    Commented Jun 14, 2010 at 16:44
  • 3
    $\begingroup$ As a professional number theorist, I found this observation sufficiently novel and interesting to upvote the question. $\endgroup$
    – Pete L. Clark
    Commented Jun 14, 2010 at 18:21
  • 1
    $\begingroup$ This suggests to me a lattice-theoretic version of the Frobenius problem. Look at the positive integers with a lt b iff a divides b. (I will use < for the usual ordering also.) Then the process starts at some number and removes ideals from the lt-lattice in "numerical order". For the example starting with 12, notice all even numbers between 12 and 22 are processed in this list. Perhaps one can look at representable numbers in the postage-stamp problem this way to some benefit. Gerhard "Ask Me About System Design" Paseman, 2010.06.16 $\endgroup$
    – Gerhard Paseman
    Commented Jun 16, 2010 at 17:30

4 Answers 4

Reset to default
15
$\begingroup$

So, let's see if I can precisify your claim. We start with a finite "seed set" that we assert to be Ghi-Om-prime (the seed set must not contain 1). Numbers smaller than the largest seed we completely ignore. Now for numbers larger than any seed prime, we run the Seive. You claim that there is some cut-off, depending of course on the seed set but hopefully not growing too quickly, so that after that cut-off, the primes match the primes in the seed set.

Recall how the Seive works. A number is GO-prime iff it is not divisible by any smaller GO-prime. Conversely, the GO-composites are precisely those numbers that are divisible by some smaller number that is either in your seed set or larger than the largest number in the seed set. In particular, every GO-composite is a true composite. So suppose there is a true composite that is not GO-composite. Then all its proper divisors are less than the largest seed. But every non-prime has a proper divisor that is at least as large as its square root. So the largest true composite that is not GO-composite is strictly less than the square of the largest seed.

This proves your claim, with the bound you suggested in the comment to Noldorin.

In any case, some remarks. First, if we state the rules for the Sieve correctly, and in particular disallow 1 as either prime or composite, then the true primes are precisely the GO primes where the seed set is empty.

Second, although I haven't seen this particular variation of the Sieve before, as I said in the comments to the question, you should check out Sanjoy Mahajan's thesis (PDF). In the last chapter, he proposes the following probabilistic variation of the Sieve. Namely, let's define the probability that $p$ SM-divides $n$ to be $1/p$. Then the probability that $n$ is SM-prime is $$ \prod_{p < \sqrt n} (\text{probability that $p$ is SM-prime})\times (\text{probability that $p$ does not SM-divide $n$})$$ The point is that SM-primality is nicely smooth, rather than exhibiting the strange jumps in the true prime spectrum, but still approximates the spectrum well for certain types of estimates. Sanjoy also considers a few other probabilistic models (whether to stop the product at $\sqrt n$ or $n$, for example), including some where he seeds the model with some early assertions of SM-primality. Sanjoy is a physicist, and so does not work at mathematicians' level of rigor, and says as much: the point of his model is to lead to new conjectures about distribution of true primes.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Theo, your reasoning is a lot cleaner than the one I had to prove my square-of-the-highest thing. I'll have a look at the thesis you link. I came to this result by thinking the primes in terms of rolling wheels ; each prime has its own wheel doing cycles and each time there is no wheel arriving to the end of its cycle, add a new wheel with cycle equal to the number of the iteration. Primes are really funny things. Thanks a bunch for your time ! $\endgroup$
    – glmxndr
    Commented Jun 14, 2010 at 17:56
  • $\begingroup$ I accepted this question as a 'no' to "Is this already known ? " and 'no' also to "Are there any known implications ?", which seem to reflect the other answers' and comments' insights as well. $\endgroup$
    – glmxndr
    Commented Jun 16, 2010 at 10:05
4
$\begingroup$

By missing out only the first prime (2), your statement is indeed correct, but it is a special case. This is because all even numbers > 4 are guaranteed to have a divisor > 2 (i.e. in the set of tested numbers). Likewise, all odd numbers that are not primes will have a divisor within your set, since you start with the lowest odd number > 1.

You claim:

We generally start with 2, but we could chose any finite set of integers >= 2, and it would still end up generating the same primes, after a "recalibrating" phase

Yet if you consider the simple case of starting with 4 and 5 now, you immediately run into problems. Given your method, 6 and 7 would be resolved as primes, since there are no divisors within your set!

I believe I've understood your statement correctly, and hopefully this should clarify why it actually fails in general. Let me know if you think I've missed any point, however.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Hi Noldorin. Indeed if you take 4 and 5 as you initial primes, 6 and 7 will be counted primes, and 9 too. But eventually (I believe at most at the square of your highest seed-prime, here 25), you will get all the "natural" primes again. The 6, 7, 9 "false positives" are part of the recalibrating phase I talked about. $\endgroup$
    – glmxndr
    Commented Jun 14, 2010 at 11:32
  • $\begingroup$ I see. This would take a fair amount of analysis, but I believe the point is the probability that a given number generated by your method is a prime tends towards (but never reaches) 1 and you take more and more numbers. The problem is however, I suspect, by the time you've generated enough numbers to be reasonably sure that the next one is a prime, you may as well as have started from 2 anyway, from a computational stand-point. $\endgroup$
    – Noldorin
    Commented Jun 14, 2010 at 11:35
  • $\begingroup$ No, after some number, all the primes are exactly the sames than the natural ones, and this number is computable. I did compute how long it takes to have a match, I think it was under the squared highest of the seed set, but I'm not sure and have not my notes right here. It would be computationally silly, though, I admit completely ! $\endgroup$
    – glmxndr
    Commented Jun 14, 2010 at 11:47
  • $\begingroup$ Yes, it seems you are correct... I don't think it changes the computational feasability significantly (as you say), due to the fact you have to reach the square of the largest seed before you get true primes, but it is a worthwhile observation from a number-theoretical perspective. I wouldn't know enough about the other implications really. $\endgroup$
    – Noldorin
    Commented Jun 16, 2010 at 11:57
3
$\begingroup$

This is not exacly what you are asking for, but it's relevant enough to mention : lucky numbers.

Improve this answer
$\endgroup$
0
$\begingroup$

There is a branch of literature that goes under the name of Generalized Primes. I remember spending some time with a book by Knopfmacher?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .