"New" primality test/check

[CRGreathouse]

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.

[LaurV]

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...

[gophne]

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 :)

[gophne]

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.

[CRGreathouse]

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).

See also:

Franz Lemmermeyer, "Binary Quadratic Forms", November 8, 2010, p.42 Theorem 1.47

[gophne]

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

[VBCurtis]

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".

[gophne]

LOL..."yes" is not a poll option!

[LaurV]

Prime numbers are very regular and orderly distributed. The order in which they are distributed is called "random order".

[retina]

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.