- primenumbers@yahoogroups.com wrote:
> There is 1 message in this issue.

The sieve program for finding primes is a recursively or iteratively

>

> Topics in this digest:

>

> 1. recursive definition of prime numbers ?

> From: Yann GUIDON

>

>

> Message

> ________________________________________________________________________

> 1. recursive definition of prime numbers ?

> Posted by: "Yann GUIDON" whygee@... yasep16

> Date: Fri Jul 31, 2009 10:28 am ((PDT))

>

> 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

>

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.

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.

Kermit Rose - Hello and thank you for your answer, even if it's not what I expected,

since it falls in the "classic" definitions bucket that I try to escape from.

but anyway...

Kermit Rose wrote:> primenumbers@yahoogroups.com wrote:

sure but one has to find "p(n) that is not divisible by any of" the precedent primes,

>> recursive definition of prime numbers ?

>>

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

which requires further nested iteration loops with divides/remainders etc...

I'm more interested by algos that tell me for sure that "the following prime is x"

instead of "let's see if the following number is prime"...

> We can stop testing as soon as we reach the smallest prime whose square exceeds pn.

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

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

of the kind that I need. They just say "this number is not a prime" with little hint

about why or how... As if one needs an "oracle" (in the cryptography sense) 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 asked other

people to see where I could be wrong, with no success.

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 of p(i)

- without trials or "scan until the next satisfying answer"

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

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)