help with prime pairs code
Jabari Zakiya
jzakiya at gmail.com
Sat Feb 8 21:24:07 UTC 2025
On Wednesday, 5 February 2025 at 21:24:51 UTC, Jabari Zakiya
wrote:
> On Tuesday, 4 February 2025 at 17:17:42 UTC, Jabari Zakiya
> wrote:
>> On Monday, 3 February 2025 at 04:59:43 UTC, monkyyy wrote:
>>> On Monday, 3 February 2025 at 04:15:09 UTC, Jabari Zakiya
>>> wrote:
>>>>
>>>> I translated this Ruby code:
>>>>
>>
>>
>> FYI.
>> This code finds all the prime pairs that sum to n for all even
>> integers n > 2.
>> It (Ruby code) is included in a paper I just released (Feb 2,
>> 2025) on Goldbach's Conjecture (1742) and Bertrand's Postulate
>> (1845). For those interested in Prime|Number Theory check it
>> out. A lot of new, good, stuff is in it!
>>
>> **Proof of Goldbach's Conjecture and Bertrand's Postulate
>> Using Prime Generator Theory (PGT)**
>>
>> https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_
>
> I updated the code to make entering data easier.
> It now mimics the Ruby|Crystal code and takes "humanized" data
> strings.
> You can now run the code as: `$ ./primes_pair_lohi_u32
> 123_456_780`
>
> I also created two versions, one for u32 input values, and one
> for u64.
> Unless you have lots of memmory, the u32 version is best to use.
>
> Here's the u32 input size version.
>
> // Compile with ldc2: $ ldc2 --release -O3 -mcpu native
> prime_pairs_lohi_u32.d
> // Run as: $ ./prime_pairs_lohi_u32 123_456_780
>
> module prime_pairs;
>
> import std;
> import std.datetime.stopwatch : StopWatch;
>
> void prime_pairs_lohi(uint n) { // inputs can be of size
> u32
> if ((n&1) == 1 || n < 4) { return writeln("Input not even
> n > 2"); }
> if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]);
> writeln([n/2, n/2]); return; }
>
> // generate the low-half-residues (lhr) r < n/2
> auto ndiv2 = n/2; // llr:hhr midpoint
> auto rhi = n-2; // max residue limit
> uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) ==
> 1).array;
>
> // store all the powers of the lhr members < n-2
> uint[] lhr_mults; // for lhr values not
> part of a pcp
> foreach(r; lhr) { // step thru the lhr
> members
> auto r_pwr = r; // set to first power of r
> if (r > rhi/r_pwr) break; // exit if r^2 > n-2, as
> all others are too
> while (r < rhi/r_pwr) // while r^e < n-2
> lhr_mults ~=(r_pwr *= r); // store its current
> power of rA
> }
>
> // store all the cross-products of the lhr members < n-2
> foreach(i, r; lhr) {
> auto ri_max = rhi / r; // ri can't multiply r
> with values > this
> if (lhr[i+1] > ri_max) break; // exit if product of
> consecutive r’s > n-2
> foreach(ri; lhr[i+1..$]) { // for each residue in
> reduced list
> if (ri > ri_max) break; // exit for r if
> cross-product with ri > n-2
> lhr_mults ~= r * ri; // store value if < n-2
> } }
>
> // convert lhr_mults vals > n/2 to their lhr complements
> n-r,
> // store them, those < n/2, in lhr_del; it now holds
> non-pcp lhr vals
> auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ?
> n - r_del : r_del).array;
> lhr_del.sort!("a < b");
> lhr = setDifference(lhr, lhr_del).array;
>
> writeln([n, lhr.length]); // show n and pcp prime
> pairs count
> writeln([lhr[0], n-lhr[0]]); // show first pcp prime
> pair of n
> writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime
> pair of n
> }
>
> void main(string[] args) { // directly recieve input
> from terminal
> string[] inputs = args[1..$]; // can include '_':
> 123_456
> auto nums = inputs.map!(i => i.filter!(n => n != '_'));
> auto n = nums.map!(f => f.to!uint())[0];
>
> auto timer = StopWatch(); // create execution timer
> timer.start(); // start it
> prime_pairs_lohi(n); // run routine
> writeln(timer.peek()); // show timer results
> }
I've updated the code to make it shorter|simpler.
```
module prime_pairs;
import std;
import std.datetime.stopwatch : StopWatch;
void prime_pairs_lohi(uint n) { // inputs can be of size u32
if ((n&1) == 1 || n < 4) { return writeln("Input not even n >
2"); }
if (n <= 6) { writeln([n, 1]); writeln([n/2, n/2]);
writeln([n/2, n/2]); return; }
// generate the low-half-residues (lhr) r < n/2
auto ndiv2 = n/2; // llr:hhr midpoint
auto rhi = n-2; // max residue limit
uint[] lhr = iota(3, ndiv2, 2).filter!(e => gcd(e, n) ==
1).array;
// store all powers and cross-products of the lhr members < n-2
uint[] lhr_mults; // lhr multiples, not part of a
pcp
foreach(i, r; lhr) {
auto rmax = rhi / r; // ri can't multiply r with
values > this
if (r < rmax) lhr_mults ~= r*r; // for r^2 multiples
if (lhr[i+1] > rmax) break ; // exit if product of
consecutive r’s > n-2
foreach(ri; lhr[i+1..$]) { // for each residue in reduced
list
if (ri > rmax) break; // exit for r if cross-product
with ri > n-2
lhr_mults ~= r * ri; // store value if < n-2
} }
// convert lhr_mults vals > n/2 to their lhr complements n-r,
// store them, those < n/2, in lhr_del; it now holds non-pcp
lhr vals
auto lhr_del = lhr_mults.map!((r_del) => r_del > ndiv2 ? n -
r_del : r_del).array;
lhr_del.sort!("a < b");
lhr = setDifference(lhr, lhr_del).array; // lhr now contains
just pcp primes
writeln([n, lhr.length]); // show n and pcp prime pairs
count
writeln([lhr[0], n-lhr[0]]); // show first pcp prime pair of
n
writeln([lhr[$-1],n-lhr[$-1]]); // show last pcp prime pair of
n
}
void main(string[] args) { // directly recieve input from
terminal
string[] inputs = args[1..$]; // can include '_': 123_456
auto nums = inputs.map!(i => i.filter!(n => n != '_'));
auto n = nums.map!(f => f.to!uint())[0];
auto timer = StopWatch(); // create execution timer
timer.start(); // start it
prime_pairs_lohi(n); // run routine
writeln(timer.peek()); // show timer results
}
```
More information about the Digitalmars-d-learn
mailing list