mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > gophne

Reply
 
Thread Tools
Old 2018-01-07, 19:09   #232
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by axn View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-08, 05:23   #233
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25·5·59 Posts
Default

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...
LaurV is offline   Reply With Quote
Old 2018-01-12, 04:38   #234
gophne
 
Feb 2017

3·5·11 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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 :)
gophne is offline   Reply With Quote
Old 2018-01-19, 04:51   #235
gophne
 
Feb 2017

2458 Posts
Default 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
gophne is offline   Reply With Quote
Old 2018-01-19, 05:44   #236
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

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).
CRGreathouse is offline   Reply With Quote
Old 2018-01-19, 07:44   #237
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Brady

17A16 Posts
Default

See also:

Franz Lemmermeyer, "Binary Quadratic Forms", November 8, 2010, p.42 Theorem 1.47
jwaltos is offline   Reply With Quote
Old 2018-02-17, 03:53   #238
gophne
 
Feb 2017

2458 Posts
Default 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
gophne is offline   Reply With Quote
Old 2018-02-17, 04:02   #239
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

52·191 Posts
Default

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".
VBCurtis is offline   Reply With Quote
Old 2018-02-17, 04:08   #240
gophne
 
Feb 2017

16510 Posts
Default

LOL..."yes" is not a poll option!
gophne is offline   Reply With Quote
Old 2018-02-17, 05:40   #241
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25×5×59 Posts
Default

Prime numbers are very regular and orderly distributed. The order in which they are distributed is called "random order".
LaurV is offline   Reply With Quote
Old 2018-02-17, 06:19   #242
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10111111111002 Posts
Default

Quote:
Originally Posted by gophne View Post
... 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.
retina is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2706 2021-05-02 21:40
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"New primality proving test from Alex Petrov" ewmayer Math 11 2007-04-23 19:07
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58

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

Sun May 9 01:12:31 UTC 2021 up 30 days, 19:53, 0 users, load averages: 1.78, 1.82, 1.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.