- 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 sense

well, 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,

maybe...

regards,

> Greg

yg

- Yann,

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 sense

that you are asking)

that will find P(n+1) from P(n) recursively?

Greg

> 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

>but anyway...

wrote:

>Kermit Rose wrote:

>> primenumbers@ <mailto:primenumbers%40yahoogroups.com> yahoogroups.com

>>> recursive definition of prime numbers ?

precedent >primes,

>>>

>>> Hello,

>>>

>>> 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).

>>>

>>> yg

>>

>> 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/remainders

prime >is x"

>etc...

>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

>exceeds pn.

>> The most efficient way to make these tests is of course by either the

>> classical prime number sieve, or by the more efficient modern

>variations.

>

>The issue that I have with these methods is that they don't give me any

>information

>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

>to

>know that n is in /P/. I want to get rid of this oracle (that can take many

>forms).

>

>I seem to have found an answer to my questions but it looks so "not

>difficult" that

>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

>overlooking

>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 another

form

>of sieve, so it does not tell me "why" things are as they are, just

"how"...)

>

.

>Best regards,

>> Kermit Rose

>YG

>(unreachable from tomorrow until the 2009-08-20)

<http://geo.yahoo.com/serv?s=97359714/grpId=2607612/grpspId=1705083388/msgId

=20706/stime=1249197099/nc1=1/nc2=2/nc3=3>

[Non-text portions of this message have been removed]