4 ms·

The Set of Prime Numbers (2007) [pdf]

11 points by anacleto 12y ago

deleted 12y ago
[deleted]
- ccvannorman 12y ago
  This
phkahler 12y ago
So if you have some lookup tables you can determine if a given number is prime. Up to some maximum based on the size of the tables. And apparently the time to generate the tables is quadratic in the size of n? Why is this relevant? AKS shows that determining if n is prime can be done in polynomial time - polynomial in log(n), not n. Is there something significant about these 2 sets of primes they talk about?
- wbhart 12y ago
  You mean O(sqrt(n)), not quadratic. And given that the most obvious algorithm there is (check every possible divisor up to sqrt(n)) is O(sqrt(n)) arithmetic operations, I think it is fair to say this is not an important result. I suppose it is a constant factor better than sqrt(n). But tricks along these lines go back to Gauss, at least. Edit: ah I see, they claim O(n^2). Well I've never had an O(n^2) primality test before. I will put that in my kit of "do-not-ever-use-this" tools, just in case all my other ones break.
Chinjut 12y ago
This seems like... maybe "crankery" isn't the right word, but certainly something overblown in that ballpark. The claim is made "We obtain for the first time an explicit relation for generating the full set P of prime numbers smaller than n or equal to n", but the rule ultimately boils down to just "A number is non-prime if it is either divisible by 2, or divisible by 3, or the product of two numbers which are neither divisible by 2 nor divisible by 3", which is completely trivial. (Also, the author was apparently attempting to patent this insight, as noted at the bottom of the first page. You know what? I've changed my mind. I'm going to happily call this "crankery". Well-LaTeXed crankery, but crankery nonetheless...)
- wbhart 12y ago
  They even threw in a reference to a fields medallist on page 1 just to alert everyone that it was crankery.
wbhart 12y ago
Summary of paper: All n = 0, 2, 4 mod 6 are divisible by 2. All n = 0, 3 mod 6 are divisible by 3. Thus all primes are either 1 or 5 mod 6. If n is composite and 1 mod 6, n = pq with p, q > 1 such that both p and q are both 1 or both 5 mod 6. If n is composite and 5 mod 6, n = pq with p, q > 1 such that (wlog) p is 1 mod 6 and q is 5 mod 6. What remains are the primes. You have to look a little bit deeper than arithmetic modulo 6 if you want to say something interesting about the primes!

11 points by anacleto 12y ago

deleted 12y ago

[deleted]

ccvannorman 12y ago
This

phkahler 12y ago

So if you have some lookup tables you can determine if a given number is prime. Up to some maximum based on the size of the tables. And apparently the time to generate the tables is quadratic in the size of n? Why is this relevant? AKS shows that determining if n is prime can be done in polynomial time - polynomial in log(n), not n. Is there something significant about these 2 sets of primes they talk about?

wbhart 12y ago
You mean O(sqrt(n)), not quadratic. And given that the most obvious algorithm there is (check every possible divisor up to sqrt(n)) is O(sqrt(n)) arithmetic operations, I think it is fair to say this is not an important result. I suppose it is a constant factor better than sqrt(n). But tricks along these lines go back to Gauss, at least. Edit: ah I see, they claim O(n^2). Well I've never had an O(n^2) primality test before. I will put that in my kit of "do-not-ever-use-this" tools, just in case all my other ones break.

Chinjut 12y ago

This seems like... maybe "crankery" isn't the right word, but certainly something overblown in that ballpark. The claim is made "We obtain for the first time an explicit relation for generating the full set P of prime numbers smaller than n or equal to n", but the rule ultimately boils down to just "A number is non-prime if it is either divisible by 2, or divisible by 3, or the product of two numbers which are neither divisible by 2 nor divisible by 3", which is completely trivial. (Also, the author was apparently attempting to patent this insight, as noted at the bottom of the first page. You know what? I've changed my mind. I'm going to happily call this "crankery". Well-LaTeXed crankery, but crankery nonetheless...)

wbhart 12y ago
They even threw in a reference to a fields medallist on page 1 just to alert everyone that it was crankery.

wbhart 12y ago

Summary of paper: All n = 0, 2, 4 mod 6 are divisible by 2. All n = 0, 3 mod 6 are divisible by 3. Thus all primes are either 1 or 5 mod 6. If n is composite and 1 mod 6, n = pq with p, q > 1 such that both p and q are both 1 or both 5 mod 6. If n is composite and 5 mod 6, n = pq with p, q > 1 such that (wlog) p is 1 mod 6 and q is 5 mod 6. What remains are the primes. You have to look a little bit deeper than arithmetic modulo 6 if you want to say something interesting about the primes!