20180107, 19:09  #232  
Aug 2006
3^{2}×5×7×19 Posts 
Quote:
If the number is prime, your algorithm takes (n3)/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. 

20180108, 05:23  #233 
Romulan Interpreter
Jun 2011
Thailand
11·853 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 gophone algorithm...

20180112, 04:38  #234  
Feb 2017
165_{10} Posts 
Quote:
At least I am getting free math lessons, at the higest levels :) 

20180119, 04:51  #235 
Feb 2017
3×5×11 Posts 
Lucky Polynomials
Hi Everybody
We know that the polynomials of Euler/Legendre x^2+x+41 and x^2x+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^23x+43 x^2+5x+47 and x^25x+47 x^2+7x+53 and x^27x+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 20180119 at 04:55 Reason: Correction to number of polynomials generating Euler numbers 
20180119, 05:44  #236 
Aug 2006
3^{2}×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(x2), f(x+2), f(x3), f(x+3), and f(x4).

20180119, 07:44  #237 
Apr 2012
Brady
5·7·11 Posts 
See also:
Franz Lemmermeyer, "Binary Quadratic Forms", November 8, 2010, p.42 Theorem 1.47 
20180217, 03:53  #238 
Feb 2017
3·5·11 Posts 
Trivial Poll
How many contributers consider the distribution of prime numbers to be "random" or "psuedorandom" 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 Psuedorandom (2) Regular, or (3) Neither Last fiddled with by gophne on 20180217 at 03:57 Reason: To give poll options 
20180217, 04:02  #239 
"Curtis"
Feb 2005
Riverside, CA
4737_{10} 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". 
20180217, 04:08  #240 
Feb 2017
A5_{16} Posts 
LOL..."yes" is not a poll option!

20180217, 05:40  #241 
Romulan Interpreter
Jun 2011
Thailand
11·853 Posts 
Prime numbers are very regular and orderly distributed. The order in which they are distributed is called "random order".

20180217, 06:19  #242 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}×1,531 Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2696  20210418 17:48 
GQQ: a "deterministic" "primality" test in O(ln n)^2  Chair Zhuang  Miscellaneous Math  21  20180326 22:33 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"New primality proving test from Alex Petrov"  ewmayer  Math  11  20070423 19:07 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 