[QUOTE=guptadeva;475510]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.[/QUOTE]

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.

[QUOTE=CRGreathouse;475544]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.[/QUOTE]

i am here to learn :smile:

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

let me ask:
[B][COLOR=Red]are there some known (exact) primality tests for a number n requiring less than pi(n) [U]steps[/U] other using a lookup table or wilsons theorem[/COLOR][/B][B][COLOR=Red]?[/COLOR]

[/B]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 [U]without[/U] the knowledge of the previous digits".

[URL="https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula"]https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula[/URL]

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 :innocent:

[QUOTE=guptadeva;475555]let me ask:
[B][COLOR=Red]are there some known (exact) primality tests for a number n requiring less than pi(n) [U]steps[/U] other using a lookup table or wilsons theorem[/COLOR][/B][B][COLOR=Red]?[/COLOR]

[/B]please note that [U]i'm not interested in[/U] speed or [U]computational complexity[/U] just the number of steps needed.[/QUOTE]

My underline.

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

[QUOTE=axn;475567]
So basically, you ask a question, but you don't want the answer.:picard:[/QUOTE]

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 [U]logical steps[/U] too if possible.

i believe, that you understand my question anyway:

[B][COLOR=Red]do you know a "simple", and possibly "beautiful" formula for p(i) not including all p(j) with j<i ?[/COLOR][/B]

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 [B]no[/B] 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 :smile:

[QUOTE=guptadeva;475568]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 [U]logical steps[/U] too if possible.

i believe, that you understand my question anyway:

[B][COLOR=Red]do you know a "simple", and possibly "beautiful" formula for p(i) not including all p(j) with j<i ?[/COLOR][/B]

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 [B]no[/B] 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 :smile:[/QUOTE]
Gcd with sqrt(n)#, # meaning primoial.

[QUOTE=robtaylor501;475524]Thank you. Helpful hints indeed. :smile: Time for a pot of tea and a new perspective![/QUOTE]

maybe you can get some inspiration from the following illustrations

[ATTACH]17435[/ATTACH]

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

instead of

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 :smile:

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

[QUOTE=science_man_88;475570]Gcd with sqrt(n)#, # meaning primoial.[/QUOTE]
"Surely You're Joking, Mr. Feynman!" - is a very good book

[QUOTE=guptadeva;475573]"Surely You're Joking, Mr. Feynman!" - is a very good book[/QUOTE]

You said steps not computational complexity.

[QUOTE=science_man_88;475574]You said steps not computational complexity.[/QUOTE]

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

[QUOTE=guptadeva;475575]"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 ...[/QUOTE]

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.

[QUOTE=science_man_88;475577]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.[/QUOTE]

step 1 implies the knowledge of [U]all[/U] prime numbers <= sqr(x)