Efficient Prime Number Generation

Ideas
1

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.

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

And thank you Wolfram for making such an awesome product!

Chris
_

2

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.

3

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

pQ.png
pQ.png495×132 7.75 KB

Where am I wrong?

4

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 :frowning: 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) &]
5

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]

pQ1.png

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}}   *)
6

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…

7

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.

8

OK, I see, interesting!

9

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: A271116 - OEIS