For mathematical definitions see the top-level Addition Chains.
We always have \(l(2n) \le l(n)+1\) as we can just double. On the \(l(2n) \le l(n)\) page I described numbers where doubling is free (\(l(2n)=l(n)\)) or even saves a step (\(l(2n)<l(n)\)). In small step terms, write \(n=2^k m\) with \(m\) odd. Since \(\lambda(2n)=\lambda(n)+1\) the sequence \(s(m), s(2m), s(4m), \ldots\) never increases, and a drop \(s(2^k m) < s(2^{k-1}m)\) is exactly a case where the \(k\)-th doubling costs nothing.
Altman [1, 2] proved that for every \(m\) there is a \(K\) such that \(l(2^k m)=l(2^K m)+(k-K)\) for all \(k \ge K\): the drops eventually stop. He notes that no way of computing \(K\) is known. This page describes how I arrived at a conjectured bound on \(K\), checked it against all the \(l(n)\) data I have, and proved it for every \(n\) with \(s(n) \le 5\) using the small step enumerations.
Conjecture. Let \(n=2^k m\) with \(m\) odd and \(k \ge 1\). If \(\lambda(m) < k+6\) (equivalently \(\lambda(n) < 2k+6\)) then \(l(n)=l(n/2)+1\).
So doubling \(m\) can only save a step at one of the first \(\lambda(m)-6\) doublings, which gives \(K \le \max(0,\lambda(m)-6)\).
Status:
In my crouton search a target is split as \(n=\sum a_i x_i\) and the number of terms is bounded in terms of the small step count. When the terms are added, the carry out of any bit position is less than the number of terms, so it can only travel a few bits past the last one in the terms. I wondered whether, when \(n\) has more trailing zeros than this carry gap, it would be enough to search for a chain for \(n/2\). That would say that the drops stop after a number of doublings depending only on \(s\).
The carry argument on its own doesn't work: the carry can ride on ones in the terms themselves (\(1+(2^k-1)=2^k\) has a carry of 1 through \(k\) positions). So I looked at the data.
I have \(l(n)\) for every \(n < 2^{39}\) stored one byte per number. A single pass compares \(l(2m)\) with \(l(m)+1\) for every \(m < 2^{38}\), reading the file as two sequential streams. Writing \(2m=2^k m'\) with \(m'\) odd, each shortfall is a drop at the \(k\)-th doubling of \(m'\). The table is tallied by the small step count \(s(2m)\) reached after the drop. There are no cases of \(l(2m)>l(m)+1\), which is a basic check on the data.
| \(s(2m)\) | Drops of one step | Largest \(k\) seen | Smallest \(m'\) at \(k=1\) | Smallest \(\lambda(m')-k\) |
|---|---|---|---|---|
| 3 | 753 | 1 | 191 | 6 |
| 4 | 195,039 | 15 | 6319 | 8 |
| 5 | 25,536,116 | 15 | 65131 | 8 |
| 6 | 1,174,424,276 | 14 | 7644991 | 10 |
| 7 | 1,744,113,766 | 8 | 994660991 | 22 |
| 8 | 10 | 1 | 257661019487 | 36 |
Drops of two or more steps at once (\(l(2n)<l(n)\)) occur 9,231 times reaching \(s=5\) (the first is 375494703) and 18,529 times reaching \(s=6\).
The largest \(k\) is limited by the data: \(m'\) can only be doubled while \(2^k m' < 2^{39}\).
At \(s=4\) the smallest \(m'\) with a drop at the \(k\)-th doubling follows a pattern:
| \(k\) | 9 | 10 | 11 | 12 | 14 | 15 |
|---|---|---|---|---|---|---|
| \(m'\) | 170055 | 340039 | 680007 | 1359943 | 5439559 | 10879047 |
Each is \(83\cdot 2^{k+2}+71\). So \(n=83\cdot 2^{2k+2}+71\cdot 2^k\) has \(s(n)=4\) while \(s(n/2)=5\), i.e. \(l(n)=l(n/2)=2k+12\). The chain behind it works for every \(k \ge 3\):
1, 2, 4, ..., 2^(k+1) k+1 doublings 3·2^k 2^(k+1) + 2^k 3·2^k + 1 + 1 5·2^k + 1 + 2^(k+1) 80·2^k + 16 4 doublings 83·2^k + 17 + (3·2^k + 1) 83·2^(2k+2) + 68·2^k k+2 doublings 83·2^(2k+2) + 71·2^k + 3·2^k
That is \(2k+12\) steps with 4 small steps. The element \(3\cdot 2^k+1\) carries a block at the scale of the trailing zeros and the 1 that grows into the 17, and the final shift lines both up with \(n\). With one trailing zero fewer the blocks no longer line up. For \(k=16\) the chain is:
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 196608 196609 327681 655362 1310724 2621448 5242896 5439505 10879010 21758020 43516040 87032080 174064160 348128320 696256640 1392513280 2785026560 5570053120 11140106240 22280212480 44560424960 89120849920 178241699840 356483399680 712966799360 1425933598720 1425933795328
The crouton search confirms the family continues past the data:
| \(k\) | \(n\) | Chain with 4 small steps | \(n/2\) | Chain with 4 small steps |
|---|---|---|---|---|
| 16 | 1425933795328 | found | 712966897664 | none |
| 17 | 5703725875200 | found | 2851862937600 | none |
So for a fixed small step count the drops do not stop after a fixed number of doublings, and no bound depending on \(s\) alone is possible.
The family suggests the trailing zeros have to line up with gaps inside \(m'\). The longest internal run of zeros in \(m'\) did not give a clean bound, but the length of \(m'\) does. In every row of the table in section 2 the smallest \(m'\) with a drop at the \(k\)-th doubling has \(\lambda(m') \ge k+6\). For \(s=4\) the 83 family sits at \(\lambda(m')=k+8\) at every \(k\) from 9 to 15.
Because the small \(m'\) can be doubled many times before reaching \(2^{39}\), this is not limited by the data the way the largest \(k\) is: every \(m'\) with \(\lambda(m') < k+6\) doubled \(k\) times is below \(2^{36}\) when \(k \le 15\). This is the conjecture above. In words, once the trailing zeros of \(n\) are longer than the rest of the number, less 6, doubling no longer saves a step.
The small step enumerations list, for each \(s \le 5\), every \(n\) with \(s(n) \le s\) as a union of convex sets in the format of [3] (apart from the low \(v(n)\) numbers the binary method handles). In each set the terms are listed from the most significant bit down. Take for example set 88 from the 3 small step file:
@(a)+@(a-2)+@(b)+@(b-1)+@(c)+@(c-1)+@(-a+b+c+1), -a+b+c >= 0
Halving an even member subtracts 1 from every exponent. Here that is \(a,b,c \to a-1,b-1,c-1\), because every term's coefficients sum to 1. The new values still satisfy the ordering and lowest exponent \(\ge 0\). The only thing that can fail is the condition \(-a+b+c \ge 0\), whose left side drops by 1. So the half leaves this set only when \(-a+b+c=0\), i.e. when the last term is \(2^1\). That boundary contains \(n=382\) (\(a=8,b=5,c=3\)), and there \(\lambda(n)=8=2k+6\).
In general a drop at \(n\) needs \(n\) in some set while \(n/2\) is in no set, so:
| Enumeration | Sets | Closed under halving | Sets with boundaries | Boundaries with minimum below 6 |
|---|---|---|---|---|
| \(s \le 1, 2\) | 1, 4 | all | 0 | 0 |
| \(s \le 3\) | 158 | 150 | 8 | 0 |
| \(s \le 4\) | 40,822 | 37,490 | 3,332 | 1 |
| \(s \le 5\) (27 bit counts) | 51,249,608 | 47,792,735 | 3,456,873 | 64 |
The single low boundary for \(s \le 4\) (set 1934) is covered entirely by one other set. The 64 low boundaries for \(s \le 5\) are all in the 7 to 11 bit files and were each covered with between 1 and 6 pieces. The lowest minimum among them was 2, so the covering step is doing real work. All bit counts of 12 and above have no low boundaries at all.
As a check that the method finds real drops, rerunning it with 9 in place of 6 finds exactly the eight \(s=4\) drops below \(2^{39}\) with \(\lambda(m')-k=8\), the 83 family among them. Restricted to \(\lambda(n) \ge 40\), beyond anything enumerated, it returns \(83\cdot 2^{34}+71\cdot 2^{16}\), the \(k=16\) member confirmed above.
The integer programs were solved with HiGHS through SciPy. These are floating point solvers working on small integer data, so for a formal proof the infeasibility results should be rechecked with an exact solver.
The programs used were doubling_drops.cpp (the scan of the \(l(n)\) table), doubling_enum.py (steps 1 and 2 over an enumeration file) and prove_low.py (step 3).
[1] Altman H (2014), "Internal structure of addition chains: well-ordering", arXiv:1409.1627.
[2] Altman H (2014), "Integer Complexity, Addition Chains, and Well-Ordering", PhD thesis, University of Michigan.
[3] Flammenkamp A (1991), "Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers". Diplomarbeit, Universität Bielefeld.