20171231, 06:09  #45  
Aug 2006
5,987 Posts 
Quote:
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. 

20171231, 10:09  #46  
Dec 2017
2×5^{2} Posts 
Quote:
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: 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 akstest is a sieve in disgiuse Last fiddled with by guptadeva on 20171231 at 10:31 Reason: including wilsons theorem in the question 

20171231, 12:29  #47  
Jun 2003
2^{2}·3^{2}·151 Posts 
Quote:
So basically, you ask a question, but you don't want the answer. 

20171231, 13:14  #48 
Dec 2017
2·5^{2} Posts 
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 20171231 at 13:20 
20171231, 13:39  #49  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:
Last fiddled with by science_man_88 on 20171231 at 13:40 

20171231, 14:05  #50  
Dec 2017
2×5^{2} Posts 
Quote:
legendrepatterns.pdf they are very simple and should be selfexplanatory. 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 numbertheorists 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 rownumbers of x 4) other "patterns"  each being some conjecture about the primenumbers emerge automatically given some time example: the conjecture that to each n and each i<n^2n there is a prime between i+1 and i+n is wrong  as can be seen visually (counterexample: n=12 and i=113) this illustrates the wellknown gap of length > n between two consecutive primes < n^2 

20171231, 14:13  #51 
Dec 2017
32_{16} Posts 

20171231, 14:18  #52 
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 

20171231, 14:30  #53 
Dec 2017
32_{16} Posts 
"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 ... 
20171231, 15:19  #54 
"Forget I exist"
Jul 2009
Dartmouth NS
8418_{10} Posts 
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.

20171231, 15:30  #55 
Dec 2017
2×5^{2} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Claimed proof of the ABC conjecture (Zha, 2009)  R.D. Silverman  Math  6  20190422 00:03 
Collatz Conjecture Proof  Steve One  Miscellaneous Math  21  20180308 08:18 
The Beal Conjecture Proof  Arxenar  Miscellaneous Math  1  20130907 09:59 
A proof for the Twin Prime Conjecture  Carl Fischbach  Miscellaneous Math  7  20090624 05:52 
Proof of Goldbach Conjecture  vector  Miscellaneous Math  5  20071201 14:43 