20251121

It has been a while, so there are multiple changes both small and large. Here are some highlights.

Compile-time options:

• New compile-time option TRACK_STATS

Build process:

• Use github actions to make Windows executable
• • see the attached file pcoul-windows-08eeb7f.zip, suitable for Windows 10 and 11
• Support Windows 7
• • see the attached file pcoul-windows7-a6eac20.zip, suitable for Windows 7, 10 and 11

Runtime options:

• New command-line option -P to work with -p
• New command-line option -G, like -g but for squares only
• New command-line option -o to skip slow factorizations
• New command-line option -j4 allows allocation of powers 2^x-1
• New command-line option -js to specify the strategy completely
• New command-line option -jp to avoid Pell short-circuit
• New command-line option -Ld to end after specified time
• Extended command-line option -a

Significant optimizations:

• Special-case strategy for n == 2 (mod 4)
• Accurate mintau()
• Faster quadratic sieve

Backward-incompatible changes:

• Batches honour modular constraints
• Don't show batch id as 4294967295
• Command-line option -I is slightly more sensible

Compile-time option TRACK_STATS:
New compile-time option TRACK_STATS will record and display statistics on how many elements of a tested sequence were found to have the correct number of divisors before a test failed. Analysis of these can give a hint how soon a complete sequence is likely to be found. (Windows builds have this enabled.)

Use github actions to make Windows executable:
With help from DemiS and from AI (Claude), we can now build the executable for Windows 10 and 11 automatically. See the attached file pcoul-windows-08eeb7f.zip.

Support Windows 7:
The pcoul-windows7 zip file provides an executable that should work on Windows 7, 10 and 11. See the attached file pcoul-windows7-a6eac20.zip.

Command-line option -P:
This option specifies a cap on the effective maximum prime used in the calculation that determines whether to recurse further or walk what we have. It is independent of gain (-g).
The intention is to allow, for example, a pair of runs with -p50 and -p50:100 to test all the same cases that a single -p100 run would test. If both are run with -P50 and other options are kept the same through all runs, I think they should be guaranteed to do so.
The -P value for all runs should be no larger than the least -p value in any run, ie 50 in the example above.

Command-line option -G:
This option specifies the gain in the same way as -g, used only when one of the values still requires an odd number of divisors (and is therefore a square). It is common to want a much smaller gain in those cases - setting -G1000: is usually a cheap win.

Command-line option -o:
Specify a bit-size beyond which factorization should give up early. On giving up, we report details of the current target and each of the numbers that are still to be factorized (along with their index in the sequence, and the number of divisors required).
Running with -o200, for example, gives up testing at the point it would start a quadratic sieve for any number of more than 200 bits (about 60 decimal digits).

Command-line option -j4:
Strategy j4 allows allocation not only of powers x-1 such that x is divisible by an odd prime, but also those for which x is a power of 2. This is useful for cases where n is divisible by high powers of 2: in tests, it was a big win for n=192, but barely an improvement for n=96 and definitely worse for n=48.
Interaction with -p and -P is imperfect, do not rely on such combinations to give full coverage when using j4.

Command-line option -js:
Instead of a numbered strategy, you can specify exactly which value should be allocated at each level with e.g. -js0,1,1,0,3. The specified locations are used for the optional allocations in order, once the mandatory allocations for the current batch have been applied. If the end of the list is reached, we will walk rather than recurse further.
Note that indexes start from 0. This is probably only sensible to use when also specifying a single batch to work on.

Command-line option -jp:
By default we make an early call to walk_v() as soon as we see two values forced to be squares, to take advantage of the resulting Pell equation; when '-jp' (defer_pell) is specified we don't call walk_v() until we have a full batch.
As a result this also honours the usual constraints of -a and -b options to avoid walking at all, and allows for better detection of the case that no valid arrangement is possible. You probably want to use this option only in special cases.

Command-line option -Ld<seconds>:
When specified, the process will terminate cleanly the first time progress is displayed after at least <seconds> has passed. This can be useful, for example, to compare progress after a fixed time with different options.

Extended command-line option -a:
The option '-a' now takes an optional numeric argument (default 1). If bit-value 1 is set, as before, we list all batches, skipping most processing; if bit-value 2 is set, we provide extended output of the batch information in CSV form and skip all other output; if bit-value 4 is set we skip even the processing that is normally done in passing, eg for patterns where a value is fully allocated, or where multiple squares result in a Pell equation.
The extended CSV form adds a CSV header, the LCM (least common multiple), and for each d dividing n shows how many elements still have d divisors not yet accounted for.

Special-case strategy for n == 2 (mod 4):
When n == 2 (mod 4), if a chain has values n_0 == 0 (mod 8) and n_2 == 2 (mod 8) then we require n_2 = 2_x_^2 => n_0 = 2(x-1)(x+1), which strongly restricts the possible factors of n_0. The new strategy (STRATEGY_6X) takes advantage of this, and is automatically used whenever the conditions apply, temporarily replacing the selected strategy.

Accurate mintau():
We regularly ask "what is the least value with d divisors that is not divisible by any of the currently allocated primes" - this is used to determine limits, which also affects the transition between recursion and walking. The code for this function (mintau()) originally had hand-coded implementations for small d, and a simple and fast (inaccurate but safe) implementation for all other d.
The new implementation now calculates the value exactly for all d, and caches each calculated result. This gives a significant speed improvement for n > 100, since we don't waste lots of time allocating primes much higher than we need.
The new implementation also adds support for "what is the least value with d divisors that is not divisible by any of the currently allocated primes, and avoiding any of this restricted list of powers". This allows a further signficant speedup for n divisible by repeated odd primes, such as n=54 or n=100.
Note that this will use more memory for the cached values, but it should not be significant except for very large n (eg n > 1000).

Faster quadratic sieve:
I have been using this code for a couple of years, and I now have high confidence in its correctness. It is 2 to 3 times faster than the original code in Math-Prime-Util.

Batches honour modular constraints:
When modular constraints are specified with -m, only batches satisfying those constraints are generated. Note that this will affect the batch id numbers.

Don't show batch id as 4294967295:
If trying to show progress before the first official batch, show it as b* instead of as 2^32-1.

Command-line option -I changes:
Use of -I is incompatible with certain -m and -c options, we reject such combinations. (Previously we rejected all use of -I, because we were not sure which cases were incompatible.)
Use of -I is ignored if we are recovering from a log file and -R has not been specified. (Previously we always acted as if -R had been specified if we saw -I.)

20230413

Bug fixes:

• in walk_1_set, correctly check whether we have already satisfied any minimum prime requirement (#4);
• in walk_1_set, correctly test any values required to be squares (#4);
• detect certain impossible cases to exit with a clean error message.

Thanks DemIS for the Windows build.

20230303 (provisional)

New options:

• prime constraints specified for -p and -W are expanded:
  • -p50 means to allocate no prime p greater than 50 for any power;
  • -p50^2 means to allocate no prime power $p^e$ greater than $50^2$ for any power;
  • new options -px, -Wx allow specific powers to be targeted, comma separated like -p50^2,20^5;
  • -p and -W constraints affect all powers not explicitly overridden by -px, -Wx.
• new debug options -dw -dW -db -dB -dx
  • -dw is equivalent to the legacy -d, showing progress at every change (except during linear walks);
  • -dW is equivalent to the legacy -d -d, showing progress at every change (including during linear walks);
  • -db shows the current batch (203) just before normal progress lines (305) if it has changed since the previous 305;
  • -dB shows the current batch (203) each time it changes;
  • -dx shows the full list of prime power constraints at the start of the run.

New capabilities:

• progress lines include batch number; recovery uses that (if present) to determine the current batch, so a range of batches can correctly be recovered.
• if no batch number is present, the previous logic is used: recovering a run that specifies a batch or a range of batches will assume we are currently at the first batch specified; if no batch is specified, it will assume batch 0.

Bug fix:

• fixed some cases that recovery can fail during -W.

Thanks to DemIS for the Windows build.

20230208 (provisional)

Note: the format of progress lines when handling -W is changed, so this version will not be able to recover from a log file generated by the previous version if the last "305" line has a "W" in it - continue running with the previous version until it has logged a progress line without "W".

There are quite a lot of new features, please keep an eye out for possible new bugs.

New features:

• -j3 is a new strategy intended specifically for cases with a significant squared factor. For example with $n=36$, after allocating an unforced $p^5$ the only remaining allocation possible at the same spot is another $q^5$ - but that's not a square, so our residue filter does not kick in. Under strategy j3, for such cases we always return the affected location as the best, which will then be handled efficiently.
• -F<p> avoids creating batches where all powers are of the form $2^x - 1$, for primes $&gt; p$; such cases are instead handled by a single tail batch.
• restrictions on the use of -W are removed.
• -I"... pattern ..." allows a specific pattern to be tested (and it does not necessarily have to be one that will normally be generated). Format is the same as the "305" progress lines; the trailing timestamp is optional.
• • Note: recovery is not currently supported with -I.
• -m<m>=<v> restricts solutions to those where the first value $v_0$ satisfies $v_0 \equiv v \pmod{m}$.
• • This is used to initialize the CRT result, but is not further analysed for possible effects on valid solutions.

New optimizations:

• allocating $p^e$ at some position for all valid $p$, when exactly $e+1$ divisors are still needed at that position, is much faster.

Thanks Demis for the Windows build, attached here as pcoul-20230208.zip.

v20221220

There are quite a few changes here, please let me know if you see any problems.

New options -WW, -Ls, -Lf, -R:

• -WW<threshold> is the same as -W<threshold>, but stops after completing the first stage;
• -Ls<time> requests progress updates to the screen every <time> seconds, or no updates if time=0;
• -Lf<time> requests progress updates to the log file every <time> seconds, or no updates if time=0;
• -R disables recovery even if the log file already exists, useful to append runs for several patterns to the same file.

Selected bug fixes:

• Pell-like equations of the form x^2 - Dy^2 = N were not correctly solved if N had squared factors;
• extracting higher roots from lower roots (root_extract()) could return the wrong list of roots;
• minimum prime, maximum prime and -W threshold were all stored as 32-bit instead of 64-bit;
• -W was not correctly run for "tail" batches (which can be generated if -f is not set to the maximum possible).

New program pcaul:

• this is like pcoul but aimed at OEIS sequences A165498 and A165499 where the arithmetic progression has difference n instead of 1.

Thanks DemIS for the Windows build, attached as pcoul_20221220.zip.

v20221202

Bug fix release:

• Recovery should work correctly even for a run with -W in the first stage.
• Progress should be reported promptly even for runs with -W and a fixed square.

Previous release:

New option "-W"

• If "-W100" is specified with "-p200", it will use a different process to test all possible cases involving p^2 with 100 < p <= 200, and then continue with the normal process as if "-p100" had been specified. This option is only available when n=12, we are running over a single batch (see "-b" below), and the limit is high enough that we won't miss any possible allocations of p^5. Within those constraints, this can give a very substantial speed improvement.
• For D(12,11), the slowest patterns (LCM=554400) appear to benefit from a value no higher than "-W5e5" (and maybe lower). For faster patterns it seems fastest to provide the minimum possible value, "-W21817". Total run times for a batch are more than 3x faster.
• Thanks (again) to Dmitry Petukhov for the idea behind this.

New build option DEBUG_ALL for pcoul

• If built with DEBUG_ALL, every value tested by linear search is printed to the log file.

Small speedup for sq12

• Skip values that are not in the range (32x-7, ..., 32x+7), since they cannot be part of any relevant chain.

Thanks DemIS for the Windows build, attached as pcoul_20221202.zip.

v20221201

New option "-W"

• If "-W100" is specified with "-p200", it will use a different process to test all possible cases involving p^2 with 100 < p <= 200, and then continue with the normal process as if "-p100" had been specified. This option is only available when n=12, we are running over a single batch (see "-b" below), and the limit is high enough that we won't miss any possible allocations of p^5. Within those constraints, this can give a very substantial speed improvement.
• For D(12,11), the slowest patterns (LCM=554400) appear to benefit from a value no higher than "-W5e5" (and maybe lower). For faster patterns it seems fastest to provide the minimum possible value, "-W21817". Total run times for a batch are more than 3x faster.
• Thanks (again) to Dmitry Petukhov for the idea behind this.

New build option DEBUG_ALL for pcoul

• If built with DEBUG_ALL, every value tested by linear search is printed to the log file.

Small speedup for sq12

• Skip values that are not in the range (32x-7, ..., 32x+7), since they cannot be part of any relevant chain.

Thanks to DemIS for preparing the 64-bit Windows build, in the attached file pcoul_20221201.zip.

v20221123

Recovery is more reliable on restarting

• In some cases, attempting to continue an interrupted run would immediately exit with an error "could not apply_single". This is intended to spot corrupted data, but was treating some valid cases as invalid.

New option "-X"

• By default, whenever a solution is found we change the maximum value, so we only search for improvements to the best solution found. If "-X" is specified, the maximum is not changed, so you can look for all solutions in a specified range.

New procedure

• Based on an idea from Dmitry Petukhov, we can speed things up substantially by handling large primes separately.
• For the calculation of D(12,11), I will take responsibility for handling large primes; contributors should run pcoul with the appropriate "-p" option. I will send email about the recommended settings, which may change from time to time, but it is already safe to run with "-p4e7" which should give substantial speed improvements.
• Using this release it should be safe to stop currently running processes and restart them with the additional -p option.
• See the new wiki page D(12,k) calculation if you are interested in the full details of how it works.

Thanks to DemIS for preparing the 64-bit Windows build, in the attached file pcoul_24112022.zip.

v20221113

When run with the new option '-v', pcoul will also update the window title with abbreviated progress information, showing the batch number and the first few primes being iterated. This also affects what is shown when the window is minimized.

Also some fixes to the output with '-a': this could sometimes crash (on Windows only), that should hopefully be fixed. The lines starting with "203" will also now be written to a log file if one was selected.

Thanks to CorporalTermit for creating the Windows build attached.

v20221109

Replacing next_prime() with iterators makes things faster.

How much faster will depend on the pattern; slower patterns should gain a bigger percentage improvement.

Note when running with this version, please replace the option "-g3" with the option "-g16" to get the full advantage of the speed. (The "-g" option controls how much time we spend in recursion and how much in a linear search. Since this change makes recursion faster, we want to spend more time there, and less time in linear search.)

Thanks to CorporalTermit for preparing the 64-bit Windows build, in the attached file pcoul_09112022.zip.