# Efficient Prime Number Generation **URL:** \ **Category:** Ideas\ **Tags:** computer-science\ **Created:** [February 7, 2021, 12:47pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576 "2021-02-07T12:47:48Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![chris9](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/chris9/32/35151_2.png) [@chris9](https://community.wolfram.com/u/chris9)\ **Post date:** [February 7, 2021, 12:47pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/1 "2021-02-07T12:47:48Z")
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. > **[Efficient Prime Number Generation](https://www.linkedin.com/pulse/efficient-prime-number-generation-christopher-wolfe/)** > > \# Copyright 2021 Christopher Wolfe (chris@jasuto.com) > > > \# Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction,... 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/](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 \_ ---
**Author:** ![wolframcommunity](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/wolframcommunity/32/8335_2.png) [@wolframcommunity](https://community.wolfram.com/u/wolframcommunity)\ **Post date:** [February 7, 2021, 4:44pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/2 "2021-02-07T16:44:50Z")
Dear [@Christopher Wolfe](https://community.wolfram.com/web/chris9), welcome to Wolfram Community! Please make sure you know the rules and how to make posts: [https://wolfr.am/READ-1ST](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.** ---
**Author:** ![henrikschachner](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/henrikschachner/32/32119_2.png) [@henrikschachner](https://community.wolfram.com/u/henrikschachner)\ **Post date:** [February 8, 2021, 7:47pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/3 "2021-02-08T19:47:57Z")
Chris, in the link to “[linkedin.com](http://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](https://global.discourse-cdn.com/wolfram/original/3X/f/1/f161c906cb5271367c27d4ffc6836155df6c0193.png) Where am I wrong? ---
**Author:** ![chris9](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/chris9/32/35151_2.png) [@chris9](https://community.wolfram.com/u/chris9)\ **Post date:** [February 8, 2021, 8:47pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/4 "2021-02-08T20:47:10Z")
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) &] ``` ---
**Author:** ![henrikschachner](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/henrikschachner/32/32119_2.png) [@henrikschachner](https://community.wolfram.com/u/henrikschachner)\ **Post date:** [February 8, 2021, 10:05pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/5 "2021-02-08T22:05:59Z")
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](https://global.discourse-cdn.com/wolfram/original/3X/2/4/242782f2c604b1801c21c478c3476c5628c4f48b.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}} *) ``` ---
**Author:** ![chris9](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/chris9/32/35151_2.png) [@chris9](https://community.wolfram.com/u/chris9)\ **Post date:** [February 8, 2021, 10:40pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/6 "2021-02-08T22:40:48Z")
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… ---
**Author:** ![chris9](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/chris9/32/35151_2.png) [@chris9](https://community.wolfram.com/u/chris9)\ **Post date:** [February 8, 2021, 10:51pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/7 "2021-02-08T22:51:15Z")
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. ---
**Author:** ![henrikschachner](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/henrikschachner/32/32119_2.png) [@henrikschachner](https://community.wolfram.com/u/henrikschachner)\ **Post date:** [February 8, 2021, 10:59pm UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/8 "2021-02-08T22:59:24Z")
> **[A001567 - OEIS](https://oeis.org/A001567)** OK, I see, interesting! ---
**Author:** ![billmceachen](https://avatars.discourse-cdn.com/v4/letter/b/34f0e0/32.png) [@billmceachen](https://community.wolfram.com/u/billmceachen)\ **Post date:** [November 22, 2021, 3:44am UTC](https://community.wolfram.com/t/efficient-prime-number-generation/17576/9 "2021-11-22T03:44:51Z")
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](https://oeis.org/A271116)