help with prime pairs code

[Jabari Zakiya]

On Sunday, 2 February 2025 at 21:17:39 UTC, Jabari Zakiya wrote:
> On Sunday, 2 February 2025 at 10:26:56 UTC, Sergey wrote:
>>
>> So after those updates the time improved
>> ```bash
>> [1000000, 5402]
>> [17, 999983]
>> [499943, 500057]
>> 81 ms, 144 μs, and 7 hnsecs
>> ```
>
> Here's the D code with the suggested changes, and other updates.
> Note, I make the source code look like Ruby|Crystal for my 
> esthetics.
>
> ```
> // Compile with ldc2: $ ldc2 --release -O3 -mcpu native 
> prime_pairs_lohi.d
> // Run as: echo 100000 | ./prime_pairs_lohi
> // Update: 2025/02/02
>
> module prime_pairs;
>
> import std;
> import std.datetime.stopwatch : StopWatch;
>
> void prime_pairs_lohi(uint n) {
>   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
>   int[] 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 
> r
>   }
>
>   // 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() {
>   int n;
>   readf("%s", &n);                // get input to n from 
> terminal
>   auto timer = StopWatch();       // create execution timer
>   timer.start();                  // start it
>   prime_pairs_lohi(n);            // run routine
>   writeln(timer.peek());          // show timer results
> }
> ```
>
> The D version is now faster than Crystal.
> ```
> D (LDC2 2.40)
> ➜  ~ echo 100000000 |./prime_pairs_lohi
> [100000000, 291400]
> [11, 99999989]
> [49999757, 50000243]
> 7 secs, 422 ms, 641 μs, and 9 hnsecs
>
> Crystal (1.15)
> ➜  ~ ./prime_pairs_lohi 100_000_000
> [100000000, 291400]
> [11, 99999989]
> [49999757, 50000243]
> 00:00:10.454055301
> ```
>
> I'll eventually do a Rust version, maybe C++, et al.
>
> I want to think everybody for the help.
> If you find more performance improvements please post them.

I am really impressed!
D is phenomenally  memory efficient with this code.
I just ran the D code for some really large n values.
On my older Lenovo Legion 5, using Linux (June 2024) w/16GB
I was able to go up to n = 1,000,000,0000 and it took up ~14.4GB 
max, out of ~14.9GB usable.
I got a new, fast TUXEDO Gen 3, w/64GB (Jan 2025), so I'm going 
to how high I can go on it.

Here are some results on the Lenovo Legion 5.

```
➜  ~ echo 500000000 |./prime_pairs_lohi3
[500000000, 1219610]
[7, 499999993]
[249999877, 250000123]
43 secs, 402 ms, 950 μs, and 3 hnsecs
➜  ~
➜  ~ echo 900000000 |./prime_pairs_lohi3
[900000000, 4132595]
[37, 899999963]
[449999993, 450000007]
36 secs, 135 ms, 163 μs, and 6 hnsecs
➜  ~
➜  ~ echo 1000000000 |./prime_pairs_lohi3
[1000000000, 2274205]
[71, 999999929]
[499999931, 500000069]
1 minute, 32 secs, 87 ms, 624 μs, and 8 hnsecs
➜  ~
➜  ~ echo 1500000000 |./prime_pairs_lohi3
[1500000000, 6543613]
[43, 1499999957]
[749999927, 750000073]
1 minute, 6 secs, 205 ms, 381 μs, and 5 hnsecs
➜  ~
```