Re: FW: [PrimeNumbers] recurrence/iterative definition of prime numbers ?
- hi !
Gregory J. McClure wrote:
> Yann,and I believe the same as you,
> It is my understanding that no formula has ever been found that produces
> ONLY primes. If that is true,
> then how can one find a formula (I believe in the sensewell, not necessary a formula (I prefer algorithms)
> that you are asking) that will find P(n+1) from P(n) recursively?
and recursivity (as understood in programming) is not necessary,
it's just that I often mistake recurrence and recursion (sorry).
(AFAIK certain classes of algorithms can easily be converted
from iterative to recursive and vice versa).
Anyway, I concede that I don't use recursivity for this subject.
I should have written "recurrence", I think. it's the lack of sleep,
It is my understanding that no formula has ever been found that produces
If that is true, then how can one find a formula (I believe in the sense
that you are asking)
that will find P(n+1) from P(n) recursively?
> Hello and thank you for your answer, even if it's not what I expected,from.
>since it falls in the "classic" definitions bucket that I try to escape
>Kermit Rose wrote:
>> primenumbers@ <mailto:primenumbers%40yahoogroups.com> yahoogroups.com
>>> recursive definition of prime numbers ?precedent >primes,
>>> I'm digging the subject of how primes can be defined,
>>> recursively or iteratively. All Google shows me is
>>> "recursive prime numbers", not what I want.
>>> I know the classic definitions but wonder if anyone
>>> has ever been able to define P(n+1) from the value(s)
>>> of P(n) (and eventually any prime down to 2).
>> The sieve program for finding primes is a recursively or iteratively
>> definition of primes.
>> Very simply,
>> p(n+1) is the next integer after p(n) that is not divisible by any of
>> p1,p2,p3,p4,.... pn.
>> Of course improvements on this basic definition can be made.
>sure but one has to find "p(n) that is not divisible by any of" the
>which requires further nested iteration loops with divides/remaindersprime >is x"
>I'm more interested by algos that tell me for sure that "the following
>instead of "let's see if the following number is prime"...little >hint
>> We can stop testing as soon as we reach the smallest prime whose square
>> The most efficient way to make these tests is of course by either the
>> classical prime number sieve, or by the more efficient modern
>The issue that I have with these methods is that they don't give me any
>of the kind that I need. They just say "this number is not a prime" with
>about why or how... As if one needs an "oracle" (in the cryptography sense)asked other
>know that n is in /P/. I want to get rid of this oracle (that can take many
>I seem to have found an answer to my questions but it looks so "not
>my first reaction was to doubt about my method. I've worked very hard >and
>people to see where I could be wrong, with no success.of p(i)
>Now my question is "am I the first to think about this, or is everybody
>a few details that seem obvious to me ?"
>So I am probing the wisdom and knowledge of the group.
>Here is my rephrased question :
>Does someone know an algo that gives the next prime p(i+1) from the >value
>- without trials or "scan until the next satisfying answer"satisfying
>- without division/multiplies/sqrt/remainder (that is : the "oracle")
>- without doubt (not a statistical method)
>- without encoded or hidden constants (I can start with only "1")
>- some auxiliary and generated data are allowed though :-)
>Pritchard's work on the wheel sieves is almost there but it's not
>because it's still too "classical" (in the sense that it's just anotherform
>of sieve, so it does not tell me "why" things are as they are, just"how"...)
>> Kermit Rose
>(unreachable from tomorrow until the 2009-08-20)
[Non-text portions of this message have been removed]