A prime numbers sieve that unravels as periodic sequence of co-primes of an ever growing set of prime generator numbers that depicts the periodic distribution of prime numbers.
Fourier analysis and number theory article below suggest ”the existence of some kind of mysterious dynamical system underlying (or "lurking behind" as N. Snaith put it in her Ph.D. thesis) the distribution of prime numbers.”.
It’s my hope that this sieve can prove this dynamic from the inside out as it generates the set of primes by means of composite periodic sequences of probable-primes. As the set of generator prime numbers tends to infinity so does the sequence period.
All prime numbers (ℙ) are contained in the sequence:
Skipping |G|
between 26 and 94:
See example below. This enables us to expand Pn
to the limits of available RAM (and data structures), while continue to increase accuracy of the sequence’s primes locations prediction for very big numbers.
TODO.
As |P|
grows exponentially, in order to make the most use of RAM a BitMap representation is used to address as many bits as possible with the least overhead. The programing language of choice is Java and the data structure that most align with this is BitSet, java.util.BitSet
although in it’s API it only allows for int
values used as indexes, which limits the addresses to INTEGER_MAX_VALUE
while the (implementation dependent) underlying data-store is long[]
. In order to store the most number of bits, java.util.BitSet
was modified to allow for long
typed indexes, code for LongBitSeg
is stored under my account on github.
A basic implementation of the sieve is published on github Here. Executing main()
method in current revision produces, for |G| = 6
:
* Computing Co-Primes Finished in 6.762224 ms.
With Value:
=> |P| = 5760 ; T(P) = 30030 ; [G] = [2, 3, 5, 7, 11, 13]
* Eliminating non-primes from [P] (except 1) Finished in 2.878282 ms.
With Value:
=> Incomplete Harmonic has
T(iP) = 166589903787325219380851695350896256250980509594874862046961683989710 = 1.665E+69
Allows to evaluate primality of integers in intervals [ n × T(iP) ± 30030 ]
With Generator primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173]
* sieveOfEratosthenes Finished in 4.354895 ms.
Primes in sieveOfEratosthenes:3248
Primes in Harmonics Sieve: 3248
A version of sieve of Eratosthenes that also uses LongBitSet
is used as precision benchmarking.
For |G| = 10
(current memory limit), output trimmed for space:
* Computing Co-Primes Finished in 3282.685708 ms.
With Value:
=> |P| = 1021870080 ; T(P) = 6469693230 ; [G] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
* Eliminating non-primes from [P] (except 1) Finished in 21541.873628 ms.
With Value:
=> Incomplete Harmonic has
T(iP) = 28165847668170109...490685420551205570 = 2.816E+34777
Allows to evaluate primality of integers in intervals [ n × T(iP) ± 6469693230 ]
With Generator primes: [2, 3, 5, 7, 11, ..., 80407, 80429]
* sieveOfEratosthenes Finished in 107445.191176 ms.
Primes in sieveOfEratosthenes:300369796
Primes in Harmonics Sieve: 300369796
This implies that with 10 generator primes [2, …, 29]
, we can generate an incomplete Pi
sequence with period Ti = 2.816E+34,777
with much more accurate prediction of probable primes than Pn
in the vicinity of:
For an accessible (though inefficient) Javascript implementation see here
Update March 26th, 2025
Visualization of the sieve and contained primes up to T= 30030; G = [2, 3, 5, 7, 11, 13]
I recently found out about the sieve of Pritchard, or Wheel sieve, which is basically the same algorithm I came up with, but it has never been (to my knowledge) used to understand prime numbers behavior. periodicity or "fractality" and Implications with the most interesting aspects of the sieve:
* Twin prime locations: nT+-1 (T being the primordial of generator primes, n is integer)
* The gaps, grow with T, and reside by the sides of twins. i.e. nT+-i (i integer <= max generator)
* Fractal expansion. (see animation up to g=13 or T = 30,030 ) The animation shows the periodic pattern expanding in the x axis until previous to last two iterations. Then the last two expansions are done vertically for digestibility.
* Grey shows composite or removed generator prime
* Half and half shows removed multiple of newly selected generator prime.
* Blue is part of the periodic pattern.
* Red is prime, also included in the pattern (some blue change to red after primality test).
* To show fractal nature of expansion I boxed each iteration in a square of black borders.
You can clearly see the barcode shape that forms, the fractal nature of the pattern, the twins and the growing gaps.