mersenneforum.org yet another 'proof' of the legendary conjecture
 Register FAQ Search Today's Posts Mark Forums Read

2017-12-31, 06:09   #45
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by guptadeva step 3 of the aks-test (see attachment above) is in fact a classical sieve. the reason for aks being vastly faster than a full sieve is the existence of the parameter r in step 2, so that the sieve only has to run until min(r,n-1) ... yet in the (relatively rare) case, that r>=n-1 a full sieve is executed.
Ah — I understand — you’re not actually familiar with AKS. (Not a problem.)

Checking for primes up to r is nothing like sieving. Given a nice small number to prove prime, with just (say) 80 digits, r would almost surely be less than 50, while “sieving” (what you meant was trial division, I think) would require you to go to 10^40. That’s microseconds of effort on one core vs. all computers on earth calculating for the age of the universe. Big difference.

It’s actually more like checking that the base of a Fermat test is relatively prime to the number being tested: you’re just ruling out a few pathological cases.

2017-12-31, 10:09   #46

Dec 2017

2×52 Posts

Quote:
 Originally Posted by CRGreathouse Ah — I understand — you’re not actually familiar with AKS. (Not a problem.) Checking for primes up to r is nothing like sieving. Given a nice small number to prove prime, with just (say) 80 digits, r would almost surely be less than 50, while “sieving” (what you meant was trial division, I think) would require you to go to 10^40. That’s microseconds of effort on one core vs. all computers on earth calculating for the age of the universe. Big difference. It’s actually more like checking that the base of a Fermat test is relatively prime to the number being tested: you’re just ruling out a few pathological cases.
i am here to learn

what place is better to ask questions about primes as in a forum where the density of number theorists, mathematicians, computer gurus and prime number enthusiasts can be described by a dirac delta function ?

also according to the ancient saying of aristotleles (?):
better to ask a question, than to eternally remain in ignorance ...

are there some known (exact) primality tests for a number n requiring less than pi(n) steps other using a lookup table or wilsons theorem?

please note that i'm not interested in speed or computational complexity just the number of steps needed.

what i'm looking for is some analogue idea to "the existence of an algorithm to find the n'th digit of the number pi written hexadecimally without the knowledge of the previous digits".

https://en.wikipedia.org/wiki/Bailey...louffe_formula

truelly wonderful indeed - but the catch is, that determining the m'th 'corresponding' base 10 digit(s) would require the knowledge of the previous hexadecimal digits ...

and yes, of cause i take my words back that the aks-test is a sieve in disgiuse

Last fiddled with by guptadeva on 2017-12-31 at 10:31 Reason: including wilsons theorem in the question

2017-12-31, 12:29   #47
axn

Jun 2003

52·211 Posts

Quote:
 Originally Posted by guptadeva let me ask: are there some known (exact) primality tests for a number n requiring less than pi(n) steps other using a lookup table or wilsons theorem? please note that i'm not interested in speed or computational complexity just the number of steps needed.
My underline.

So basically, you ask a question, but you don't want the answer.

2017-12-31, 13:14   #48

Dec 2017

2×52 Posts

Quote:
 Originally Posted by axn So basically, you ask a question, but you don't want the answer.
just forget the phrase "computational complexity" in context with "i'm not interested" for the moment - i am sorry to have formulated the question in a silly manner.

and yes i truelly want an answer and know that computational complexity is THE measure to describe computational steps needed - but i would like to know some answer in terms of logical steps too if possible.

i believe, that you understand my question anyway:

do you know a "simple", and possibly "beautiful" formula for p(i) not including all p(j) with j<i ?

if we take the resulting numbers left after applying the sieve of eratosthenes to be the "definition" of prime numbers, then the answer would be no as we can prove, that such a formula can not exist on that base.

if on the other hand we stick with the original definition of a prime number, then i cannot see any arguments why such a formula should not exist ?

also you may drop the terms "simple" and "beautiful" from the question - any positive answer or existense of such a formula would automatically be beautiful and hopefully simple

Last fiddled with by guptadeva on 2017-12-31 at 13:20

2017-12-31, 13:39   #49
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by guptadeva just forget the phrase "computational complexity" in context with "i'm not interested" for the moment - i am sorry to have formulated the question in a silly manner. and yes i truelly want an answer and know that computational complexity is THE measure to describe computational steps needed - but i would like to know some answer in terms of logical steps too if possible. i believe, that you understand my question anyway: do you know a "simple", and possibly "beautiful" formula for p(i) not including all p(j) with j
Gcd with sqrt(n)#, # meaning primoial.

Last fiddled with by science_man_88 on 2017-12-31 at 13:40

2017-12-31, 14:05   #50

Dec 2017

2×52 Posts

Quote:
 Originally Posted by robtaylor501 Thank you. Helpful hints indeed. Time for a pot of tea and a new perspective!
maybe you can get some inspiration from the following illustrations

legendrepatterns.pdf

they are very simple and should be self-explanatory.
please also note, that the numbers are arranged according to

1 2
3 4

1 2 3
4 5 6
7 8 9

1 2
3 4

1 2 5
3 4 6
7 8 9

where all squares are positioned on the diagonal line

many number-theorists prefer the first set of arrangements because of the following reasons:

1) the legendre conjecture may be interpreted geometrically as
the last two lines contain at least one prime (red box)

2) the formulation of the oppermann conjecture may be interpreted as
the last line and the line following contain at least one prime each

3) in each illustration you can easily find the representation of a number x in the base n by simply looking at the column- and row-numbers of x

4) other "patterns" - each being some conjecture about the prime-numbers emerge automatically given some time

example: the conjecture that to each n and each i<n^2-n there is a prime between i+1 and i+n is wrong - as can be seen visually (counter-example: n=12 and i=113)
this illustrates the well-known gap of length > n between two consecutive primes < n^2

2017-12-31, 14:13   #51

Dec 2017

1100102 Posts

Quote:
 Originally Posted by science_man_88 Gcd with sqrt(n)#, # meaning primoial.
"Surely You're Joking, Mr. Feynman!" - is a very good book

2017-12-31, 14:18   #52
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by guptadeva "Surely You're Joking, Mr. Feynman!" - is a very good book
You said steps not computational complexity.

2017-12-31, 14:30   #53

Dec 2017

2·52 Posts

Quote:
 Originally Posted by science_man_88 You said steps not computational complexity.
"Surely You're Joking, Mr. Feynman!"
i actually had many discussions with richard feynman one or two years before he passed away ... what a true inspiration he was - he managed to make you grasp even the most complicated problems in his own brilliant way ...

2017-12-31, 15:19   #54
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by guptadeva "Surely You're Joking, Mr. Feynman!" i actually had many discussions with richard feynman one or two years before he passed away ... what a true inspiration he was - he managed to make you grasp even the most complicated problems in his own brilliant way ...
Except it's one step maybe 2 if you count the comparison to 1. It may be complex if you assume no look up table. But it is definitely 2 steps. 1 do the computation, 2 compare the result to 1.

2017-12-31, 15:30   #55

Dec 2017

2×52 Posts

Quote:
 Originally Posted by science_man_88 Except it's one step maybe 2 if you count the comparison to 1. It may be complex if you assume no look up table. But it is definitely 2 steps. 1 do the computation, 2 compare the result to 1.
step 1 implies the knowledge of all prime numbers <= sqr(x)

 Similar Threads Thread Thread Starter Forum Replies Last Post R.D. Silverman Math 6 2019-04-22 00:03 Steve One Miscellaneous Math 21 2018-03-08 08:18 Arxenar Miscellaneous Math 1 2013-09-07 09:59 Carl Fischbach Miscellaneous Math 7 2009-06-24 05:52 vector Miscellaneous Math 5 2007-12-01 14:43

All times are UTC. The time now is 12:23.

Fri Jan 28 12:23:22 UTC 2022 up 189 days, 6:52, 2 users, load averages: 1.16, 1.30, 1.32