q1 — exhaustive search for short straight-line programs

Decides whether an integer $N$ has a straight-line program of length $L$ (OEIS A173419 / A217032; Smale 1998, Problem 4, integer form).

Files

Definitions

A program is $x_0=1$, $x_k=x_i\circ x_j$ with $i,j<k$ and $\circ\in\{+,-,\times\}$; $\tau(N)$ is the least $k$ with $x_k=N$. Subtraction is allowed in either order and $i=j$ is allowed. This is the convention of OEIS A173419, of the 2013 contest, and of Markström; Shub–Smale and Smale use the same one.

Normalisation

If $N>0$ has a program of length $k$, it has one of length at most $k$ whose values are pairwise distinct and strictly positive. Replace every value by its absolute value: $|x_i x_j|=|x_i||x_j|$, and $|x_i\pm x_j|$ is either $|x_i|+|x_j|$ or the positive difference of $|x_i|$ and $|x_j|$, so the new sequence is again a program. A zero can only arise as a difference of equal values; a repeated value can be dropped after redirecting later references to its first copy. (Markström, arXiv:1306.3091, Appendix A, states the same.)

Canonical order

Let $S_d=\{1,v_1,\dots,v_d\}$ be the values of a normalised program prefix. The queue $Q(S_d)$ lists every positive integer derivable in one step from $S_d$ and not in $S_d$, in blocks: block 0 holds the values derivable from $\{1\}$, block $i$ the values first derivable once $v_i$ is present, each block in a fixed generation order and without repetition. Positions in the queue depend only on the prefix.

Rule: the next value $v_{d+1}$ must sit in $Q(S_d)$ at a position strictly larger than the position of $v_d$ in $Q(S_{d-1})$.

Every normalised program has exactly one valid order that satisfies the rule. Among all orderings of its value set that are programs (each value derivable from the earlier ones), take the one whose sequence of queue positions is lexicographically least. If two consecutive values had non-increasing positions, the later one would lie in an earlier block, hence be derivable without the former; swapping the two gives a program with a smaller position sequence. For an optimal program the target is the only value not used later, so it is last in every ordering. This is the "pending queue" order described by Rokicki in the OEIS A217032 digest; the count mode reproduces Markström's reached-set sizes exactly, which is the empirical check of exhaustiveness.

Endgame

For length $L$ the search enumerates prefixes of $L-3$ steps and asks whether $N$ is derivable in at most three more steps. Write $S$ for the prefix set, $Q$ for its queue, and $y_1,y_2$ for the new values (each new, positive, and used later).

• 0 or 1 step: $N\in S$ or $N\in Q$.
• 2 steps: $N=y_1\circ b$ with $b\in S$ or $b=y_1$, so $y_1\in\{N-b,\,N+b,\,b-N,\,N/b\}\cup\{N/2,\sqrt N\}$ and $y_1\in Q$.
• 3 steps, last step uses $y_1$: $N=y_2\circ y_1$ with $y_1\in Q$; either $y_2\in Q$, or $y_2=y_1\circ c$ with $c\in S\cup\{y_1\}$, which is solved for $c$ (for instance $N=(y_1+c)+y_1$ gives $c=N-2y_1$).
• 3 steps, last step does not use $y_1$: $N=y_2\circ z$ with $z\in S\cup\{y_2\}$, so $y_2$ is one of at most $4|S|+2$ candidates, and $y_2=y_1\circ c$ with $c\in S\cup\{y_1\}$, $y_1\in Q$. Divisibility $c\mid y_2$ is decided from residues $N\bmod c$ and $b\bmod c$ without division.

Any hit is turned into an explicit program and re-verified in Python. brute_check.py compares the endgame with a direct three-step expansion on random prefixes.

Filters

• Markström's bound: with $r$ steps left, values stay below $M^{2^r}$ where $M$ is the current maximum.
• Leaf bound: in three steps the only ways to exceed $M^5$ are $N=y_2^2$ and $N=y_1^3$. Factorials and primorials are never perfect powers, so a leaf with $M^5<N$ is skipped for that target.
• Range checks before every lookup: a value must lie between the minimum and maximum of the set it is claimed to belong to.

Arithmetic is exact: values below $2^{128}$ are native, larger ones use limbs; the arena is asserted, never truncated.

Replay

./run_all.sh            # build, controls, decisions at 11 and 12 steps, verify
./run_all.sh --full     # also the 13-step decision (hours on 8 threads)