20261014

This release is mostly about correctness: several bugs have been fixed that could cause results to be missed or wrongly reported, some of them long-standing, so everyone is recommended to upgrade. Recovery from log files has also been substantially reworked and tested, and there are some significant speed-ups. Below are some highlights.

Because of the number of correctness bugs found, I plan to rerun all previous proofs of minimality. I think the chance of any of those results turning out to be wrong is small.

The README and D(n,k)-calculation have been updated, and the full list of pcoul options is now at pcoul options.

Windows 10/11 build: pcoul-windows-9dbe910.zip
Windows 7 build: pcoul-windows7-9dbe910.zip

Bugfixes:

• Pell solver could miss solutions
• Factorization could wrongly accept or reject some values
• Null allocations could cause valid cases to be missed
• -fr skipped some batches
• Some -I patterns used wrong residues for a square
• Modular constraint error, mostly affecting k=1 with -j4
• Fixes for -W
• Fixes for the -a4 batch listing
• Batch ids of 2^31 or more
• Truncation of values of 2^32 or more
• Other minor bugfixes

Recovery:

• Recovery reworked for all strategies, and for -W
• A candidate can be appended to a log

Build process:

• The Windows executables are built with Math-Prime-Util-GMP v0.54
• • and are tested as they are built
• The executable knows and logs its version
• • builds now record the git version of their sources
• • perl is required at build time
• CHECK_OVERFLOW is now enabled by default
• Builds now default to -march=native

Runtime options:

• Command-line options -g and -G behave differently with a fixed square
• The search stays committed after a candidate
• -a4 lists a fully allocated value as one short batch
• Debug options -dw<n> and -dW<n> now stop the search
• Command-line options -a and -b show the LCM of each batch
• Command-line option -b stops after its last batch
• New debug option -dL to log every progress line
• A candidate is no longer reported repeatedly

New optimizations:

• Faster rejection of primes, and faster primality tests
• New optimization FLIP_PQSQ for pairs of squares
• Assorted smaller speed-ups

Backward-incompatible changes:

• Windows executables now order some work as Linux builds do
• Debug options -dv, -dV renamed to -dc, -dC
• Log file format changes

Bugfixes

Pell solver could miss solutions:
When two values are forced to be squares we solve the resulting Pell equation to find candidates. The solver could miss some classes of solutions: for example 2 x^2 - 5 y^2 = -3 gave (1, 1) and (49, 31) but not (11, 7) or (419, 265). In a test of 2888 equations of the shapes that pcoul generates, it missed 83 of the 935 solutions with x up to 3000.
The new solver follows the convergents of a continued fraction directly as far as the limit, which finds every solution and is also faster for large D.

Factorization could wrongly accept or reject some values:
There were several errors in deciding whether tau(n^e) = t once more than one prime above the trial division limit was involved, mostly where what remained was a power of a prime. The most serious has been present since 2022: a value was wrongly rejected whenever the factoring ladder found its other primes first and was left with the square of a prime, for example 64013.100003^2 with tau 6. Other cases could wrongly accept a value, such as 64271^2.378067243^2 with tau 6.

Null allocations could cause valid cases to be missed:
When we applied a null power (p^0) for a forced prime (a "tail batch"), that prime was wrongly marked as unavailable. As a result mintau() could return too high a value, causing us to skip valid cases. This skipped only cases requiring the highest allocations so it is unlikely this missed any solutions, but it cannot be ruled out.

-fr skipped some batches:
With -fr, a power with no cap was treated as capped at 0, so no forced prime could take it as its highest power. A plain -p<max> sets no cap on powers p^1, p^3, p^7 and so on, so every batch in which the highest power of some forced prime was one of those was skipped: 32% of the batches of ./pcoul -f13 -p72 -x5e80 -fr 36 14. With no cap at all, -fr failed with a 406 error.
Any run using -fr where such a power was available covered fewer batches than it should have.

Some -I patterns used wrong residues for a square:
Where -I forces a square without giving the power of 2, as in ./pcoul -I"7^3 . . . ." 36 5, the residues of the square were calculated wrongly when a batch for p=2 reached it. Such a search could miss solutions, and could report false ones as if verified.

Modular constraint error, mostly affecting k=1 with -j4:
A check added in release 20260115 missed a division, so that in rare cases we could require the final prime p to satisfy p == 0 (mod 2) rather than p == 1 (mod 2). For example ./pcoul -x48188059920 -j4 3200 1 failed to find its result.
The affected code is called only in relatively extreme circumstances, except that for k=1 with -j4 it will nearly always be called. I'm about as sure as I can be that no recorded results were affected.

Fixes for -W:
The comparison used to sort the ranges for -W could give the wrong answer when two limits differed by 2^31 or more, in which case some primes would never be tried for the ranges that reach further. It is unlikely that this affected any prior runs, but some effort will be required to rule it out.
We also now skip primes that have already been allocated (batch primes, or those set with -I). This is needed for correctness, but we don't usually expect to see it with typical -W values.
A search with no forced primes (k=1, or k=2 with 4 | n and no -f) made no -W walk at all, and so found only what -p alone would find: ./pcoul -W3 -x1e4 12 2 reported 819 where f(12, 2) = 735. Such a search is now processed as a single batch, b0.
A -W sweep through primes that all failed to apply showed no progress, and logged no recovery point, for as long as that took; it can now show progress for any allocation tried.

Fixes for the -a4 batch listing:
Under -a4, a batch that fully allocated some value lost track of the residues of a value forced to be a square. So among such batches the listing included some that should have been rejected and missed others, and ./pcoul -f13 -p72 -x5e80 -a6 36 14 died with SIGFPE. Only the -a4 listing was affected: without it such a batch is tested on the spot.

Batch ids of 2^31 or more:
Batch ids were held in a 32-bit integer. From 2^32 batches the id shown wrapped to 0, as seen in a -a2 listing for D(48,24). From 2^31 batches, an open-ended range -b<n>: stopped after batch 2^31 - 1 and reported as if the search was complete, -b<n> with n >= 2^31 acted as -a, and recovery could count a batch twice.

Truncation of values of 2^32 or more:
In several places a 64-bit value passed through a 32-bit variable. A minimum prime of 2^32 or more was reduced mod 2^32 in the walks, and a -P cap of 2^32 or more led to poor recurse/walk decisions.
-I accepted an unfactored entry only below 2^32, and silently mishandled larger ones. It now factorizes an entry of any size, including a composite base with an exponent (6^2 was taken as the prime 6). It also now fails with an error if a prime factor is 2^64 or more, or for a missing or zero number, which used to be ignored.

Other minor bugfixes:

• Fixed squares could report solutions that did not qualify, if the square value(s) had the wrong tau.
• We could read beyond the allocated part of an array used by mintau().
• factor_one() now fails cleanly if it runs out of ways to factorize, where before it would loop indefinitely.
• The roughness check requested with -h now properly checks for overflow.
• The prime iterator had several memory access errors, and would return garbage rather than fail on reaching 2^64.
• Under -I, a pattern whose batch did not fit below the maximum went on to search the batches after it; it now searches nothing.
• We could occasionally report solutions smaller than the specified -x minimum, and could crash if the -x range became negative.
• We now fail at startup if k > 66, or if more than 32767 small primes would be needed. Neither limit is new, but previously they were not checked, and exceeding them could give wrong results.

Recovery

Recovery reworked for all strategies, and for -W:
Recovering a run with -r now has tests covering every strategy (-j0 to -j4 and -js) and the special-case strategies, and that turned up a lot to fix:

• with -j4, after a new candidate was found the order of allocations could differ on recovery, giving either a "failed to inject" error or, worse, silently continuing with the wrong allocation order;
• recovery with -js was broken, and would mostly fail with a panic;
• recovery during -W processing could lose count of the batch id, and could repeat parts of the search;
• recovery during -W processing now continues the walk in progress from where it left off, rather than restarting it;
• the special-case strategy for n == 2 (mod 4) and the new FLIP_PQSQ optimization can now be recovered;
• a candidate logged after the last progress line could make recovery stop with an error; it is now applied once the rest of the log has been restored.

The intention is that every progress line written to the log is a usable recovery point. To support this the log has a new line type 315, and progress lines may have extra annotations: see "Log file format changes" below.

A candidate can be appended to a log:
As a consequence of the last change above, you can copy a 202 candidate line found by another run (for example another shard of the same search) to the end of a log, and recover from it: the search continues with that candidate as its new maximum. If the candidate is at or below the run's -x minimum, the recovered run finishes at once with it as the result.

Build process

The Windows executables are built with Math-Prime-Util-GMP v0.54:
The Windows executables were previously built from the simpqs-full branch of my fork of Math-Prime-Util-GMP; they are now built from the v0.54 release (MPUGMP_VER=39982f872b), which is also now the default when you build pcoul yourself. This loses the quadratic sieve speed-ups of the simpqs-full branch for now, but gains faster trial division (a whole band of primes is tested with a single gcd) and a bunch of other improvements. The next version of Math-Prime-Util-GMP will bring back the QS speed-ups and more.
Each Windows build now also runs the full test suite before it is published.

The executable knows and logs its version:
For both divrep and Math-Prime-Util-GMP, the Makefile now finds the last commit to change any of the files pcoul is built from, and whether any of them have uncommitted changes. This is shown at the end of the 001 line as sha=<divrep>;<mpugmp>, with a * after either to mark uncommitted changes.
The Makefile runs a perl script to find this, so perl is now needed to build pcoul; no additional perl modules are required. You do not have to build from a git checkout, but if you don't then the git status will be empty.

CHECK_OVERFLOW is now enabled by default:
This compile-time option returns early whenever the modular constraints on v_0 show that it would have to exceed the limit. It was left off when added four years ago because it appeared to cost more than it saved, but recent tests show it can now offer a big saving. (Windows builds also have this enabled.)

Builds now default to -march=native:
Previously this was requested with NATIVE=1. It is now the default, so if you build pcoul yourself the executable is optimized for your machine and may not work on a different type of machine: build with PORTABLE=1 to avoid that. The Windows executables are built with PORTABLE=1.

Runtime options

Command-line options -g and -G behave differently with a fixed square:
The calculation that decides whether to recurse further or walk now did not correctly count the number of cases a walk will test when a value is forced to be a square (or higher power): it could greatly overestimate the cost of the walk. This helps to explain why we usually wanted a gain orders of magnitude lower for those cases, which also prompted the addition of -G.
That has been corrected, so a -G value chosen for an earlier release (such as -G1000:) will probably now be much too low, causing us to walk far too early. For new runs I suggest starting without -G, so that the -g value is used for the square cases as well, and tuning from there. If you were using -g alone, the best value for that may also have changed.
The hope is that the best gain will now be much more consistent between square and non-square cases, reducing the need to care about the distinction.

The search stays committed after a candidate:
When a candidate lowers the maximum, the search used to reconsider whether to walk or recurse at the level in progress. It now keeps the choice it made, and only recalculates the limit, which is what recovery does; that is what makes every progress line recoverable. Results are unchanged, and a run that finds no candidate does the same work as before.
This may make a noticeable difference if solutions are found that reduce the maximum by many orders of magnitude (eg by a factor over 10^20). It is probably a good idea to restart the run with the lower maximum when this occurs.

-a4 lists a fully allocated value as one short batch:
A value fully allocated by the forced primes fixes all k integers, so it leaves no choice for the remaining forced primes. Under -a4 such a batch is now listed at the point the value is fully allocated, rather than once for each placement of the remaining forced primes: for ./pcoul -f13 -p72 -x5e80 -a6 36 14 there are now 380810 of them where there were 11223481. This changes the listing, and so the batch numbering, under -a4.

Debug options -dw<n> and -dW<n> now stop the search:
When a count is given with -dw<n> or -dW<n> (or the new -dL<n>), we used to turn the debug option off after n iterations and leave the search to run to its natural conclusion. We now stop at that point with the message 301 Stopping: debug count exhausted.
If you want to continue such a run (with or without debugging), remove the 301 line from the end of the log file before recovering.

Command-line options -a and -b show the LCM of each batch:
The 203 line shown for each batch under -a or -b now includes [aq=...], the LCM of the batch, as a guide to its cost. Note that this changes the format of those lines: see "Log file format changes" below.

Command-line option -b stops after its last batch:
When run with -b<id> or -b<min>:<max> we now stop as soon as we pass the last requested batch. Previously we would continue to enumerate the remaining batches without testing them.
The 203 line for each selected batch is now shown as it starts.

New debug option -dL:
Writes a progress line to the log at every opportunity, permitting fine control for automated testing. Like -dW it takes an optional count, eg -dL100 to limit this to the first 100 iterations.

A candidate is no longer reported repeatedly:
On finding a candidate we used to set the new upper limit to the candidate itself, so the same value could be found several times. The limit is now set to one less than the candidate. It is still possible to see repeated solutions when running with -X.

New optimizations

Faster rejection of primes, and faster primality tests:
Nearly every prime tried at a level of recursion is rejected because the least value it allows is above the maximum. We now make that test in native 64-bit (and where possible 32-bit) arithmetic before doing the full calculation. And what trial division leaves of a value, when it fits in 64 bits, is now tested for primality with a native BPSW test, about six times faster than before.
Measured separately on batches from two long-running searches, D(48,10) and D(96,8), these gave between 2% and 40% each; on the batches measured, together they make those searches roughly 1.5 to 1.7 times as fast.

New optimization FLIP_PQSQ for pairs of squares:
For example with n=18, allocating p^2 at some position leaves tau of 6 to find, satisfied by q^2.r with q > p or by q^5. When p is high enough that no q > p can fit, only the q^5 cases remain; we detect that, and instead try each way of allocating p^5. There are far fewer of those to consider, and each leaves a square, so many can be rejected immediately.
This can apply only when the q^2 allocation would be looked for immediately after the p^2 allocation, so in most cases only with -j2. It is mostly useful when n is of the form 2 p^k, but will occasionally trigger for other n such as n=150.
For ./pcoul -x87574012724275 -f3 -j2 -g27 54 3 it gives a 15% overall improvement.

Assorted smaller speed-ups:

• walk_1() does less work for each prime tested.
• Modular inverses and the Chinese Remainder calculation for a single prime power are faster.
• We copy less state at each level of recursion.
• -W processing skips positions that the walks already cover.
• Two errors that caused unintended extra work in factorization are fixed.

Backward-incompatible changes

Windows executables now order some work as Linux builds do:
In a few places pcoul relied on the order in which the C library's sort leaves elements that compare equal. Linux and Windows libraries differ in this, so for some n the Windows executables tried powers in a different order, numbered batches differently, and ordered the -W sweep differently from Linux builds. Results were not affected. The order no longer depends on the library, and is the one Linux builds have always used.
For affected n, the batch numbers shown by earlier Windows executables differ from those shown by this release, and a log written by an earlier Windows executable should not be recovered with this one.

Debug options -dv, -dV renamed to -dc, -dC:
These show information about modular constraints, mostly relevant only in conjunction with the -c options.

Log file format changes:
Several changes may affect anything that parses terminal output or log files.

• The 203 line shown for a batch now ends with the elapsed time, and under -a or -b that is preceded by the LCM of the batch, as 203 <batch> [aq=<LCM>] (<time>s).
• The new 315 line is an expanded form of the 305 progress line, used whenever an allocation is not where the strategy would now choose to put it, and marking the allocations affected; it is written only to the log file, not to the terminal.
• Progress lines may end with an annotation 6X(p,vi,a) (STRATEGY_6X) or F(vi,oldp) (FLIP_PQSQ) when the relevant special-case is in effect.
• A search with no forced primes shows b0 in its progress lines where it showed b*.
• The 001 line now shows the -o option if given, and the git status of the build.
• New fatal errors 517, 518 and 519 report -I patterns that cannot be handled.

Log files from earlier releases can still be recovered (except as noted above for Windows), but earlier releases will not be able to recover from a log that has 315 lines or these annotations.