mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-12-31, 06:09   #45
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by guptadeva View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-12-31, 10:09   #46
guptadeva
 
Dec 2017

2·52 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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 ...

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 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
guptadeva is offline   Reply With Quote
Old 2017-12-31, 12:29   #47
axn
 
axn's Avatar
 
Jun 2003

123658 Posts
Default

Quote:
Originally Posted by guptadeva View Post
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.
axn is offline   Reply With Quote
Old 2017-12-31, 13:14   #48
guptadeva
 
Dec 2017

3216 Posts
Default

Quote:
Originally Posted by axn View Post
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
guptadeva is offline   Reply With Quote
Old 2017-12-31, 13:39   #49
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by guptadeva View Post
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
Gcd with sqrt(n)#, # meaning primoial.

Last fiddled with by science_man_88 on 2017-12-31 at 13:40
science_man_88 is offline   Reply With Quote
Old 2017-12-31, 14:05   #50
guptadeva
 
Dec 2017

2·52 Posts
Default

Quote:
Originally Posted by robtaylor501 View Post
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

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

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
guptadeva is offline   Reply With Quote
Old 2017-12-31, 14:13   #51
guptadeva
 
Dec 2017

2×52 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Gcd with sqrt(n)#, # meaning primoial.
"Surely You're Joking, Mr. Feynman!" - is a very good book
guptadeva is offline   Reply With Quote
Old 2017-12-31, 14:18   #52
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by guptadeva View Post
"Surely You're Joking, Mr. Feynman!" - is a very good book
You said steps not computational complexity.
science_man_88 is offline   Reply With Quote
Old 2017-12-31, 14:30   #53
guptadeva
 
Dec 2017

2·52 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 ...
guptadeva is offline   Reply With Quote
Old 2017-12-31, 15:19   #54
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by guptadeva View Post
"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.
science_man_88 is offline   Reply With Quote
Old 2017-12-31, 15:30   #55
guptadeva
 
Dec 2017

628 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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)
guptadeva is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Claimed proof of the ABC conjecture (Zha, 2009) R.D. Silverman Math 6 2019-04-22 00:03
Collatz Conjecture Proof Steve One Miscellaneous Math 21 2018-03-08 08:18
The Beal Conjecture Proof Arxenar Miscellaneous Math 1 2013-09-07 09:59
A proof for the Twin Prime Conjecture Carl Fischbach Miscellaneous Math 7 2009-06-24 05:52
Proof of Goldbach Conjecture vector Miscellaneous Math 5 2007-12-01 14:43

All times are UTC. The time now is 07:48.


Thu May 26 07:48:33 UTC 2022 up 42 days, 5:49, 0 users, load averages: 1.49, 1.25, 1.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔