# Efficient Prime Number Generation

Posted 2 months ago
566 Views
|
7 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 _
7 Replies
Sort By:
Posted 2 months ago
 Dear @Christopher Wolfe, welcome to Wolfram Community!Please make sure you know the rules and how to make posts: https://wolfr.am/READ-1ST (besides other things it also explains how to easily add Wolfram Language code to the post). This forum permits only subjects related to Wolfram Technologies. Could you please click EDIT on your post and add the complete self-sufficient info including the Wolfram Language code.
Posted 2 months ago
 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?
Posted 2 months 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) &] 
Posted 2 months 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 2 months 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...
 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 you 1s 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.