mersenneforum.org "New" primality test/check
 Register FAQ Search Today's Posts Mark Forums Read

2018-01-07, 19:09   #232
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by axn So your algorithm: Take odd N (which we're checking if it is prime or composite) For all odd n = 1,3,... < N, check if gcd(n, n+2*N) > 1. if so, you found a factor of N, and it is composite, otherwise it is prime. Trial division algortihm: Take odd N (which we're checking if it is prime or composite) For all odd prime n = 3,5,7,.. < sqrt(N), check if n divides N. if so, you found a factor of N, and it is composite, otherwise it is prime.
Let's compare performance. If the number is composite, the time both take depends on their smallest prime factor p. Your algorithm takes (p-1)/2 steps, while trial division takes pi(p) - 1 steps (we're assuming an odd number), which is asymptotically p/log p. In the worst case p = sqrt(n) so yours takes O(sqrt(n)) operations and trial division takes O(sqrt(n)/log n) operations (including the cost of sieving). But gcd is more expensive than division, so really the algorithms differ by a factor more like log^2 n.

If the number is prime, your algorithm takes (n-3)/2 divisions which is O(n). Trial division needs only O(sqrt(n)/log n).

So for composites your algorithm is worse, but it's not too bad. But it's catastrophically bad on primes.

 2018-01-08, 05:23 #233 LaurV Romulan Interpreter     Jun 2011 Thailand 9,371 Posts In that case, we need an amendment: we first do an AKS test to see if the number is prime. If it is not prime, then we do the go-phone algorithm...
2018-01-12, 04:38   #234
gophne

Feb 2017

3·5·11 Posts

Quote:
 Originally Posted by 10metreh I don't think you've taken on board what axn meant by this: The point is that, if n is odd, then gcd(n, n+2N) = gcd(n, N) and so you are just checking if n has any common factors with N. But if N is not prime, then the smallest n that has a common factor with N is the smallest prime factor of N, so in fact when you first find n such that gcd(n, n+2N) > 1, that n is a factor of N. So you're just doing inefficient trial division. I guess that technically counts as a "primality test" in that it does correctly determine primality or otherwise of N. But it's easy to come up with useless primality tests. Here's one: if N>4, then N is prime if and only if N does not divide (N-1)!. Unlike trial division, it's got only one step, so what could possibly go wrong...? As for why gcd(n, n+2N) = gcd(n, N), it's time for another basic number theory lesson: Suppose d divides n and n+2N. Then d must divide their difference, which is 2N. But d divides n, which is odd, so d is odd, and thus d must divide N. Conversely, suppose d divides n and N. Then clearly d divides n+N+N = n+2N. So the sets of common factors of (n, n+2N) and (n, N) are exactly the same, and in particular gcd(n, n+2N) = gcd(n, N).
Love this!

At least I am getting free math lessons, at the higest levels :)

 2018-01-19, 04:51 #235 gophne   Feb 2017 3×5×11 Posts Lucky Polynomials Hi Everybody We know that the polynomials of Euler/Legendre x^2+x+41 and x^2-x+41 generate the series of primes called Euler numbers; 41 43 47 53 61 71 83 97 113 131 151 173 197 223 251 281 313 347 383 421 461 503 547 593 641 691 743 797 853 911 971 1033 1097 1163 1231 1301 1373 1447 1523 1601 for the first 40 terms. Question, is it also commonly known that these values are also apparently generated by the polynomials; x^2+3x+43 and x^2-3x+43 x^2+5x+47 and x^2-5x+47 x^2+7x+53 and x^2-7x+53........ That is each new polynomial being f(x)=x^2+ x+41 plus 2x+2, f(x)=x^2+3x+43 plus 2x+4 f(x)=x^2+5x+47 plus 2x+6 f(x)-x^2+7x+53 plus 2x+8....... At least for the next +-36 polynomials as well. i could not find these "derived' polynomials mentioned anywhere, except the Euler/Legendre forms of the polynomial. Caveat: Not sure if similar derived polynomials have been published/discussed else where. Not encountered in my searches for same in Wikipedia. Last fiddled with by gophne on 2018-01-19 at 04:55 Reason: Correction to number of polynomials generating Euler numbers
 2018-01-19, 05:44 #236 CRGreathouse     Aug 2006 32·5·7·19 Posts Yes, this is known -- they are shifts of the polynomial. With f(x)=x^2+ x+41, your polynomials are f(x+1), f(x-2), f(x+2), f(x-3), f(x+3), and f(x-4).
 2018-02-17, 03:53 #238 gophne   Feb 2017 3·5·11 Posts Trivial Poll How many contributers consider the distribution of prime numbers to be "random" or "psuedo-random" vs contributers who consider prime numbers to be very orderly distributed in the set of natural numbers? Poll to be closed on 16/03/2018 (Would appreciate somebody that could summarize the poll results :)) "There are two facts about the distribution of prime numbers. The first is that, [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision." - Don Zagier, as quoted in Elementary Number Theory: Primes, Congruences, and Secrets -William Stein, January 23, 2017 Poll options; (1) Random or Psuedo-random (2) Regular, or (3) Neither Last fiddled with by gophne on 2018-02-17 at 03:57 Reason: To give poll options
 2018-02-17, 04:02 #239 VBCurtis     "Curtis" Feb 2005 Riverside, CA 473710 Posts I don't think you have any idea what "regular" and "random" mean. This is a math forum. Be precise. You've worded your question so vaguely that in its present form I'm pretty sure the answer is "yes".
 2018-02-17, 04:08 #240 gophne   Feb 2017 3·5·11 Posts LOL..."yes" is not a poll option!
 2018-02-17, 05:40 #241 LaurV Romulan Interpreter     Jun 2011 Thailand 9,371 Posts Prime numbers are very regular and orderly distributed. The order in which they are distributed is called "random order".
2018-02-17, 06:19   #242
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

611910 Posts

Quote:
 Originally Posted by gophne ... there are laws governing their behavior, and that they obey these laws with almost military precision."
There are no laws governing their (primes) behaviour. Instead the "laws" are formulated from their behaviour. Primes don't obey anyone or anything, they are what they are, without any concern for how humans like to categorise them. You can't make a new set of laws and expect the primes to follow just because you say they should.

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2695 2021-04-07 21:50 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 ewmayer Math 11 2007-04-23 19:07 James Heinrich Software 2 2005-03-19 21:58

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

Sat Apr 17 12:29:18 UTC 2021 up 9 days, 7:10, 0 users, load averages: 2.78, 2.32, 2.12