D(n,k) calculation

This page describes how pcoul searches for $v = D(n,k)$, the least $v$ such that $\tau(v+i) = n$ for every $i$ with $0 \le i < k$. It is written for users who want to understand what the main options do, and as a starting point for reading the code.

It describes the code on the master branch as of 2026-10-13 (commit 028e0b3). Details change often; the overall method changes rarely.

Note that A292580 refers instead to $T(n,k)$, with the identity $T(m,k) = D(2m,k)$.

These terms are used throughout this page, and in the code and its output.

• position, value: the $k$ consecutive numbers $v_i = v + i$, $0 \le i < k$. Position $i$ is the index; $v_i$ is the value there.
• allocation: the choice to search only those $v$ for which $p^{x-1}$ exactly divides $v_i$. It contributes a factor $x$ to $\tau(v_i)$, so $x$ must divide $n$. The search tries every possible allocation in turn, so each one selects a part of the search space; it is not a claim that the solution has that form.
• remaining tau ($t_i$): the part of $n$ not yet supplied by allocations at position $i$.
• $q_i$: the product of the prime powers allocated at position $i$.
• $a_q$, $r_q$: every allocation is a congruence on $v_0$; combining them all by the Chinese Remainder Theorem gives $v_0 \equiv r_q \pmod{a_q}$.
• forced prime: a prime $p \le k$. Such a prime can divide more than one of the values, so the powers of it at all positions are decided together (with one exception, see "Forced primes and batches").
• unforced prime: a prime that is allocated at one position only, without regard to the others. Every prime $p > k$ is unforced; some primes $p \le k$ may be unforced at some positions (see below).
• batch: one way of placing the powers of every forced prime. The search runs one batch after another.
• recurse: make one more allocation, then continue the search from there.
• walk: stop allocating, and instead test directly every $v_0 \equiv r_q \pmod{a_q}$ up to the maximum.
• walk-or-recurse decision: the choice, made repeatedly during the search, between recursing further and walking now (called the "gate" in the code).
• gain ($g$, option -g): a multiplier that the user can set to shift the walk-or-recurse decision towards recursing (larger $g$) or towards walking (smaller $g$).
• square: when the unallocated part of $v_i$ must be an $h$'th power for some $h > 1$, we say position $i$ needs a square. A walk can then be made much shorter.
• candidate: a value $v$ found to satisfy all the conditions. Unless -X is given, each candidate lowers the maximum for the rest of the search.

If $p^e$ exactly divides $v$, then $e + 1$ divides $\tau(v)$. The search therefore allocates prime powers to the values in every possible way, so that each value gets the right number of divisors. It does this recursively: each step of the recursion makes one allocation.

Each allocation increases $a_q$, and so reduces the number of values of $v_0$ still to be tested, at the price of trying each possible allocation in turn. At some point it is always cheaper to test each member of the residue class up to the maximum (to walk) than to allocate further. The art lies in deciding when to stop allocating.

In outline, the search runs in these stages:

1. Allocate the forced primes, one batch at a time.
2. Optionally (option -W), for each batch, first handle all cases that involve one large prime with a separate fast sweep.
3. Allocate unforced primes, one at a time, until the walk-or-recurse decision says to walk.
4. Walk: test each $v_0$ in the remaining residue class.

The recursion is in recurse(), and the main walk is in walk_v().

A prime $p \le k$ always divides at least one of the $k$ values, and may divide several. For each such prime, prep_forcep() lists in advance every consistent way to place its powers across the positions. For example, if $p^2$ divides $v_i$, then $p$ divides $v_{i+p}$ but $p^2$ does not. Each consistent placement is one choice for that prime.

The forced primes are taken in increasing order. One choice for every forced prime together makes a batch. Option -a lists the valid batches, each with an id and the LCM ($a_q$) of the allocations it makes; option -b runs only the given batch or range of batches. A batch with a larger LCM leaves fewer values to test, and is usually quicker to finish.

For a prime $k/2 < p \le k$, some positions have no other position at distance $p$; there $p$ can divide only that one value. We have a choice in such cases:

• treat $p$ as forced at that position too, trying each of its powers there as a separate batch; or
• leave it to be allocated later as an unforced prime. All such cases for $p$ are then grouped into one final tail batch for that prime.

pcoul takes the first option when $p \le f$ (set by -f), or when $n \equiv 2 \pmod 4$; otherwise it takes the second.

• Example: for $D(12, 9)$ and $p=7$, we must force $p$ at $v_0, v_1, v_7, v_8$, but can leave it unforced at $v_2, \ldots, v_6$. Forced there, the search will try in turn each of $7^2, 7^5, 7^{11}, 7^1, 7^3$ at each of those positions. Unforced, it would normally try only $7^2, 7^5, 7^{11}$, the powers $p^e$ where $e + 1$ is divisible by an odd prime: a $7^1$ or $7^3$ there would be found by factorization during a walk (see "Order of powers" below).
• Which is faster depends on how many positions are affected, and on how strongly the extra allocation constrains the search. If it leaves only a square or a prime still to find at that position, forcing is much more likely to help.

With -W<P>, once a batch is complete the search first handles every case in which some unforced prime $p > P$ is allocated. For each position and power where such a prime could fit below the maximum, it works through the primes $p > P$ from the largest down, allocates $p^{x-1}$ at that position, and walks at once, without any further recursion. After that, the normal search for the batch continues as if -p<P> had been given: it allocates no unforced prime above $P$.

This is much faster than reaching the same cases by recursion, which would make many allocations that leave almost nothing to test. Choosing $P$ well can give a large speedup (see "Example: choosing options" below). The sweep is done by walk_midp().

When a batch is complete (and after any -W sweep), the search continues with unforced primes. At each step:

1. best_v() chooses the position to allocate at next. The strategy for that choice is set by -j (see below). If no position has anything left that recursion would allocate, we walk.
2. For that position, we try each permitted power $x$ in turn.
3. For each power, we try each prime $p$ in increasing order, up to a limit $\lim_p$. Above $\lim_p$, $q_i \cdot p^{x-1}$ times the smallest possible contribution of the remaining tau would exceed the maximum. limit_p() calculates this limit.

Before trying the primes for a new power, the search makes the walk-or-recurse decision (see below). Each time a new candidate lowers the maximum, the limits of the steps still in progress are recalculated.

To make sure each combination is tried only once, the powers at a position are allocated in a fixed order. The next power allocated, $p^{x-1}$, always has $x$ a multiple of the highest prime dividing $t_i$; powers with the same highest prime are allocated in ascending order; and two allocations of the same power use increasing primes.

Powers $p^{x-1}$ with $x$ a power of 2 (that is, $p^1$, $p^3$, $p^7$, ...) are the exception. By default recursion does not allocate them at all: when each $t_i$ is a power of 2, the search walks, and finds those factors by factorization. Under -j4 (or a fixed order given with -js) recursion does allocate them, in increasing order of $p$.

• -j0: choose the position with the highest $t_i$.
• -j1: choose the position whose $t_i$ has the highest prime factor.
• -j2: choose the position with the lowest $t_i$.
• -j3: like -j0, but if the last unforced allocation at some position was the square root of its remaining tau, choose that position again.
• -j4: like -j1, but if every candidate position has a power of 2 as its $t_i$, choose the one with the smallest range; also allocate powers of 2 as described above.
• -js<list>: allocate at the positions in the order given, one allocation per entry, starting again after each batch. When the list runs out, the search walks. This is expected to be useful only when running an individual batch with -b.

The default is -j1 if $n$ has at least two distinct odd prime factors, otherwise -j0. In practice -j4 is usually needed when $n$ is a power of 2, and often helps when $n$ is divisible by a high power of 2.

When the search is about to start a new power $x$ at position $i$, gate_walk() compares two rough costs:

• the cost of walking now: the number of steps in the walk, $w \approx v_{max} / a_q$;
• the cost of recursing: the number of primes still to try at this step, approximately $\lim_p - p$.

The search walks if $w$ is less, and recurses otherwise. These are crude estimates, so the gain $g$ is applied as a further factor: the search actually walks if $g \cdot w < \lim_p - p$. A higher gain therefore means more recursion and shorter walks.

When a square is available (see below), the walk is much shorter and its cost is estimated differently. By default the same gain is used for these walks; -G overrides it for them.

The decision is made once, when a new power is started. After that the search stays with it, even if the maximum is later lowered by a new candidate. The best gain varies a lot from case to case, and choosing it well can make a large difference to the run time; see the example below.

For each position $i$ let $Q_i = a_q / q_i$, and $o_i = (r_q + i) / q_i$. At step $j$ of the walk (variable ati in the code) we have $v_0 = r_q + j a_q$, and so $v_i = q_i (o_i + j Q_i)$. We need $o_i + j Q_i$ to be coprime to $q_i$, and to have exactly $t_i$ divisors.

Before the walk starts, walk_v() prepares:

• for each prime $p$ dividing $q_i$, the residue of $j \pmod p$ that would make $p$ divide $o_i + j Q_i$. Any such $j$ can be rejected at once.
• a list of positions with $t_i = 2$ (which need a prime), and a list of the others.

At each step it checks the residues first, then the positions that need a prime, then the others, stopping at the first failure. Within each list the values are tested side by side: the cheap tests are applied to every value before any of the expensive ones. If all tests pass, we have a candidate.

If $t_i$ is odd, the unallocated part of $v_i$ must be a square. More generally, if $h \mid r - 1$ for every prime $r$ dividing $t_i$, it must be an $h$'th power; the search uses the largest such $h$, $h = \gcd{r - 1 : r \text{ prime}, r \mid t_i}$.

During recursion the search keeps the list of $h$'th roots of $r_q + i \pmod{a_q}$ for such a position. With one square, the walk then visits only the $h$'th powers in those residue classes, which is far fewer steps than the ordinary walk.

With two or more squares, the first two give a generalized Pell equation, which pell.c solves; the walk then visits only its solutions.

If an allocation would leave $t_i = 1$, then $v_i$ is fully determined by it, and hence so is $v_0$. Instead of recursing, the search tests each such value directly (walk_1(), walk_1_set()).

Two special cases have their own methods. You only need to know about them to understand some progress lines.

• the flip: when $p^{z-1}$ has left $t_i = 2z$, and no larger prime fits as $q^{z-1}$, the remaining work for this power is searched the other way round, which is cheaper (run_flip_pqsq()).
• 6X: when $n \equiv 2 \pmod 4$ and $v_{i+2}$ is forced to the form $2z^2$, then $v_i$ must be $2(z-1)(z+1)$; a special search uses that relation (walk_6x()). It switches on automatically.

Option	Effect
-f<p>	force all primes up to $p$ at every position (when $4 \mid n$)
-j<s>	strategy for choosing the next position
-g<g>	gain for the walk-or-recurse decision
-G<g>	gain for that decision when a square is available (default: same as -g)
-W<P>	sweep cases with an unforced prime $p &gt; P$ separately
-p<min>:<max>	allocate only primes $p \le max$, including at least one $p &gt; min$ (a partial search)
-a, -b<id>	list batches, or run only some of them

See pcoul options for the full list of options and their syntax.

The graph shows the CPU time of a full run of $D(12,9)$, with -x15724736975643 (its known value), for a range of -g and -W, with -f5 (left) and -f7 (right).¹

• Without -W, the gain matters a lot: too low a gain can more than double the run time. Here the best gain is about 16, and higher gains slowly get worse again.
• A well-chosen -W makes the run faster, and the gain much less critical. With -f5 -W3e3, every gain from 2 to 64 is within 10% of the best.
• The best -W depends on -f. With -f5, a -W between 3e3 and 1e4 halves the run time; with -f7, every -W tried makes it slower.
• So the options interact, and should be tuned together rather than one at a time. The best here is -f5 -W3e3 -g8, at about half the time of the best run without -W.

1: Each point is a single run on one machine, so small differences should not be relied on.