# Efficient Prime Number Generation

Posted 1 year ago
1896 Views
|
8 Replies
|
0 Total Likes
|
 Hey everyone, I've been doing some number theory during all this Covid downtime and I think I've discovered an pretty interesting (if not novel) algorithm for detecting primality. I posted my writeup on my LinkedIn page, you don't have to signup or anything.https://www.linkedin.com/pulse/efficient-prime-number-generation-christopher-wolfe/I just want to know if this technique is already known, because it's quite fast (constant time) and pretty compact in size. I did a deeper dive a while back which you can read on my blog.http://jasuto.com/ideas/primes/It would be great to get some feedback and to verify that this is new. I have quite a bit more to release, but thought I would start light :)And thank you Wolfram for making such an awesome product!Chris _
8 Replies
Sort By:
Posted 2 months ago
 You might look at OEIS A271116. It also generates all primes and some pseudoprimes to base 3. I don't know how the timing /efficiency compares to your method, but you can see the Mathematica code there. Ref: https://oeis.org/A271116
Posted 1 year ago
 https://oeis.org/A001567OK, I see, interesting!
Posted 1 year ago
 There is a more interesting form: E^((4 I Pi (1 + 2^x x)) / (-3 + (-1)^x - 2 x)) which doesn't require floor's and gives you1s for primes: {1, 1, 1, E^((2*I*Pi)/3), 1, 1, E^((2*I*Pi)/5), 1, 1, E^((2*I*Pi)/7), 1, E^(-((4*I*Pi)/5)), E^((8*I*Pi)/9), 1, 1, E^((2*I*Pi)/11), E^((16*I*Pi)/35), 1, E^((2*I*Pi)/13), 1, 1, E^(-((2*I*Pi)/3)), 1, E^((4*I*Pi)/7), E^((2*I*Pi)/17), 1, E^(-((14*I*Pi)/55)), E^((2*I*Pi)/19), 1, 1, E^((2*I*Pi)/21), E^((6*I*Pi)/13), 1, E^((2*I*Pi)/23), 1, 1, E^((22*I*Pi)/25), E^((16*I*Pi)/77), 1, E^((26*I*Pi)/27), 1, E^((6*I*Pi)/17), E^((2*I*Pi)/29), 1, E^(-((8*I*Pi)/13)), E^((2*I*Pi)/31), E^(-((84*I*Pi)/95)), 1, E^(-((28*I*Pi)/33)), 1} This was found by replacing floor with the equivalent Fourier derived square-wave, aligned on the integer line.
Posted 1 year ago
 try: Select[{#, pQ[# - 1] == Boole[PrimeQ[#]]} & /@ Range[1, 1000, 2], (! Last[#]) &] you will get all primes plus Fermat's little friends in the form of: PowerMod[2, (n - 1), n ] == 1 eg: 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705 the trick is subtracting them at the correct cadence, or an easier method is to find a function that approximates the sarrus sequence and perform a full primality check then, the frequency of these additions is quite low...
Posted 1 year ago
 Oh, this I did not notice. OK, my complete code for your function now reads: pQ[0] = pQ[1] = 0; (* not prime *) pQ[2] = 1; (* prime *) pQ[k_] := If[OddQ[k], With[{n = k - 1}, -Floor[(2 (-1 + 2^n n))/(3 - (-1)^n + 2 n)] + Floor[(2 (1 + 2^n n))/(3 - (-1)^n + 2 n)]], 0] Looks great! But if you try more numbers, I am afraid it does not work, e.g.: Select[{#, pQ[#] == Boole[PrimeQ[#]]} & /@ Range[1000], (! Last[#]) &] (* Out: {{341,False},{561,False},{645,False}} *) 
Posted 1 year ago
 Hi, the form you are using for pQ is shifted by 1 relative to PrimeQ, here is how you can make them equivalent: (PrimeQ[Range[3, 100, 2]] // Boole) == pQ[Range[3, 100, 2] - 1] I had posted some Python code here but it was against the site policy - sorry about that :( just need to convert it to WL, here is how to generate primes (along with Fermat's friends): Select[Range[1, 100, 2], (pQ[# - 1] == 1) &] 
 Chris,in the link to "linkedin.com" you gave you are talking about "primality testing" - this is a test for prime numbers, right? But using your formula I cannot see any correlation with prime numbers: pQ[n_] := -Floor[(2 (-1 + 2^n n))/(3 - (-1)^n + 2 n)] + Floor[(2 (1 + 2^n n))/(3 - (-1)^n + 2 n)] Where am I wrong?