On the Infinity of Twin Prime and other K-tuples

[bsquared]

Originally Posted by jzakiya

If you can, compile/test the Nim and Rust versions (Rust just released 1.46). They should be faster, especially with 16 cores.

I've downloaded the code from https://github.com/jzakiya/SSoZ, but I don't know how to compile it. Any pointers?

[jzakiya]

What's even more impressive is that Pascal (the author) was not a Java programmer. He saw my Nim gist version and started posting to me about it. He wanted to try a Java version to give him a reason to learn it. This was in 2019, and he would ask me questions about Java, which I know nothing of, but forged ahead to get better and better versions. So I hadn't seen his final version (I assume this is his latest) until now, and haven't run it yet. I'm sure a Java guru can make it better (which he humbly kept saying) so I hope he gets the recognition for its implementation, especially from where he started.

[jzakiya]

Originally Posted by bsquared

I've downloaded the code from https://github.com/jzakiya/SSoZ, but I don't know how to compile it. Any pointers?

The best thing to do is follow these instruction from rust-lang.org

https://www.rust-lang.org/learn/get-started

I created a project folder called twinprimes_ssoz, which should create the necessary file structure. Just put the source file in the /src folder, and follow the compilation instruction in the file. It will download a bunch of crates, so you need internet access. Once compiled, the exe will be in /target/release. The instructions explain all of this, which is easier than it sounds.

The Nim version is actually easier to compile, because all you have to do is install Nim and compile the file per its internal instructions, from wherever you place it.

https://nim-lang.org/
https://nim-lang.org/install.html

The Rust source code was significantly improved by the Rust gurus on its forum from where it started. What would be really interesting is to use Rust to generate a Wasm version. There are so many things than can be done with it given sufficient resources and time.

[jzakiya]

Originally Posted by bsquared

I've downloaded the code from https://github.com/jzakiya/SSoZ, but I don't know how to compile it. Any pointers?

Use these versions.

Rust
https://gist.github.com/jzakiya/b96b...eb3f35eb437225

Nim
https://gist.github.com/jzakiya/6c7e...dd62e3e3b2341e

[bsquared]

I'm afraid I'm running into problems, probably because of my ignorance of the rust build process. I tried running cargo.exe build in the top level of the SSoZ repository and got this

error[E0277]: `[usize; 8]` is not an iterator
   --> src\sieve.rs:179:19
    |
179 |         for ri in res {
    |                   ^^^ borrow the array with `&` or call `.iter()` on it to iterate over it
    |
    = help: the trait `std::iter::Iterator` is not implemented for `[usize; 8]`
    = note: arrays are not iterators, but slices like the following are: `&[1, 2, 3]`
    = note: required by `std::iter::IntoIterator::into_iter`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.
error: could not compile `SSoZ`.

If I try to run rustc.exe on the twinprimes_ssoz.rs file you pointed to, I get this:

PS C:\projects\ssoz> rustc.exe .\twinprimes_ssoz.rs
error[E0463]: can't find crate for `rayon`
  --> .\twinprimes_ssoz.rs:37:1
   |
37 | extern crate rayon;
   | ^^^^^^^^^^^^^^^^^^^ can't find crate

error: aborting due to previous error

[EDIT]

Ok, I've learned to add dependencies to cargo.toml. Now I've reached this point and have no more ideas for things to try.

error[E0432]: unresolved import `SSoZ::sieve::largest_twin_prime_before`
 --> src\main.rs:2:5
  |
2 | use SSoZ::sieve::largest_twin_prime_before;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no `largest_twin_prime_before` in `sieve`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0432`.
error: could not compile `SSoZ`.

[EDITEDIT]

ok, I figured it out. copied the cargo.toml file with its list of dependencies to a new folder with a src/ subfolder. moved the twinprimes_ssoz.rs file into the src/ subfolder. Renamed the file to main.rs. Then build --release worked.

This is a different computer (i7-7800X). Now I get:

primesieve-7.4, 12 threads, 10^11
3.61 sec

twinprimes_ssoz.rs, 12 threads, 10^11
2.34 sec

Twin counts match. Kudos!

[bsquared]

Originally Posted by bsquared

This is a different computer (i7-7800X). Now I get:

primesieve-7.4, 12 threads, 10^11
3.61 sec

twinprimes_ssoz.rs, 12 threads, 10^11
2.34 sec

Twin counts match. Kudos!

Looks like you still have some work to do at higher offsets though:

primesieve-7.4 10^14 to 10^14+10^11
6.08 sec

twinprimes_ssoz.rs, 10^14 to 10^14+10^11
13.2 sec

primesieve-7.4 10^16 to 10^16+10^11
8.41 sec

twinprimes_ssoz.rs, 10^16 to 10^16+10^11
92.8 sec

[jzakiya]

On my System76 i7 4C|8T 3.5GHz laptop, at least upto 2x10^14 twinprimes_ssoz is faster. But the larger the ranges the more mem|time it takes to run and tweak, and I couldn't dedicate that laptop to doing that (I have a life, and this is a hobby). I could try some of the tricks primesieve uses for large ranges, but then I would have to rearchitect the code, which doesn't interest me right now.

Primesieve is actually 3 different algorithms, for small, medium, and large ranges. He does some really artful stuff to precompute table of primes, memory management, etc, for large ranges. Check out his code, its nice. But like I said, he's been at it for years and is an expert C++ programmer.

However, what this single file of < 300 loc shows is the prime generator based algorithm is inherently faster, for the reasons I presented in that paper, and is much simpler to code. It gives you the best ROI for the least cost (development time, hardware, mem needs, etc).

Also, being the ultimate fastest implementation isn't always the highest priority goal. I give you for free the value of the last twin in the range. In the Nim version (I left it out for Rust) I provide code to display the twins (mid values).

Consider my code a reference proof of concept implementation.
Now that you have working code you can do whatever you want to apply it to different environments and check those results against it.

I've been trying to get people in some universities, who have the $$ and student workers, to do a distributed network to find the next largest Twins, and also Cousins and Sexy primes, because all you have to do is change which residue pairs to use, but the algorithm is exactly the same.

And this is what people should really start to appreciate, one generic algorithm can be used to find prime pairs for any gap size just by picking the appropriate residue pairs for a given Prime Generator.

[mart_r]

Could this code be used to search for gaps between prime twins? It seems it has the potential to be faster than the code I'm using.

[jzakiya]

Originally Posted by mart_r

Could this code be used to search for gaps between prime twins? It seems it has the potential to be faster than the code I'm using.

I assume you mean what are the spacings between pairs of twinprimes?

That's already known depending on the Prime Generator (PG). Once you pick a generator all the residues spacings are determined. For example, using P3, all the twins are of form 6n+/- 1. For P5 you have 3 twinpair residues, and know the spacing between them, etc, etc, if that's what you mean.

But here's how to create an implementation to find the largest Twins.

In my paper I give the residue pairs the current largest known Twin exists on for two different PGs. All you have to do to find all larger ones is to pick some large generator, say P19, which has (p19 - 2)# twinpair residues. Parametize it to find its resgroup k value and twinpair residues, then use that as the starting point for searching. Then any twinpair(s) greater than this are the next largest ones.

Thus, we can reduce the code to very small ranges that can fit in cache, or whatever the optimum memory structure of the system (since we only need the equivalent of bitarrays), and stop only if we find any twins in a range. Then we can numerate their parameters to get their values. This can be done in a GIMPS like network shipping out these independent ranges to as many workers as possible, and whoever finds an occupied range then that's a new unknown Twin pair. Piece of cake!

Once you understand the theory you'll soon realize the potential power you have for finding any kind of primes.

FYI. Yesterday I emailed the author of a paper I had stored in my cache of prime papers, who did extensive numerical analysis to actually count the gaps in primes up to large numbers. I asked if he had histograms of data of the accumulative distributions of the gaps, and he did! and he sent me a zip file of his data. And sure enough, his data confirms exactly what my paper stated, Sexy Primes are the most abundant, followed by Twins and Cousins, and the gaps have an oscillating nature, etc. He even sent me the updated 2018 version (mine was 2011), link to his paper below.

Some heuristics on the gaps between consecutive primes
https://arxiv.org/pdf/1102.0481.pdf

I hope I answered the question you meant.

[LaurV]

Originally Posted by mart_r

Could this code be used to search for gaps between prime twins?

I thought that is always 2...

[mart_r]

Originally Posted by jzakiya

In my paper I give the residue pairs the current largest known Twin exists on for two different PGs. All you have to do to find all larger ones is to pick some large generator, say P19, which has (p19 - 2)# twinpair residues. Parametize it to find its resgroup k value and twinpair residues, then use that as the starting point for searching. Then any twinpair(s) greater than this are the next largest ones.

Thus, we can reduce the code to very small ranges that can fit in cache, or whatever the optimum memory structure of the system (since we only need the equivalent of bitarrays), and stop only if we find any twins in a range. Then we can numerate their parameters to get their values. This can be done in a GIMPS like network shipping out these independent ranges to as many workers as possible, and whoever finds an occupied range then that's a new unknown Twin pair. Piece of cake!

Once you understand the theory you'll soon realize the potential power you have for finding any kind of primes.

I wrote two different programs, one in Excel/VBA and one in Pari, both of those were about or almost half as fast as the Perl program I was using at the time (which was not mine; I'm not yet familiar with coding in Perl or C and won't be in the forseeable future). I used a generator array of the size of P23 in VBA, and possibly there could've been some optimizations within the code, but I hardly got any replys to the codes I posted. I could even go up to P29, it probably would cost me a day of some rewriting, but the program would still only be about half as fast as the program I'm using to search the gaps.

My problem is not the theory, it's the efficient implementation in a language close to the hardware.

Originally Posted by LaurV

I thought that is always 2...

Mock me why don't you... after doing most of the computation work in the last few months