## Re: FW: [PrimeNumbers] recurrence/iterative definition of prime numbers ?

Expand Messages
• hi ! ... and I believe the same as you, ... well, not necessary a formula (I prefer algorithms) and recursivity (as understood in programming) is not
Message 1 of 2 , Aug 2, 2009
• 0 Attachment
hi !

Gregory J. McClure wrote:
> Yann,
>
> It is my understanding that no formula has ever been found that produces
> ONLY primes. If that is true,
and I believe the same as you,

> 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?
well, not necessary a formula (I prefer algorithms)
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
Message 2 of 2 , Aug 2, 2009
• 0 Attachment
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 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,
>since it falls in the "classic" definitions bucket that I try to escape
from.
>but anyway...

>Kermit Rose wrote:
wrote:
>>> 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.
>
>sure but one has to find "p(n) that is not divisible by any of" the
precedent >primes,
>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 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
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
>people to see where I could be wrong, with no success.
>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)

.

<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]
Your message has been successfully submitted and would be delivered to recipients shortly.