In [1] the author makes the following conjecture:
"We show that there is a minimal length addition chain for \(n\) such that the last four steps are stars. Then we conjecture that there is a minimal length addition chain for \(n\) such that the last \(\lfloor l(n) / 2 \rfloor\)-steps are stars. We
verify that the conjecture is true for all numbers up to \(2^{18}\)."
For addition chains with a single non-star step, it seems reasonable to assume that either an addition chain or its dual have a star step early in the chain. This seems like it would break down with numbers that need two non-star steps.
The following counter example was found with the non-star steps in red:
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 1024, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 295168, 369089, 738178, 1476356, 2952712, 5905424, 5979345
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 1024, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 295168, 369089, 738178, 1476356, 2952712, 3026633, 5979345
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 1024, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 221505, 369089, 738178, 1476356, 2952712, 5905424, 5979345
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 1024, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 221505, 369089, 738178, 1476356, 2952712, 3026633, 5979345
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 641, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 295168, 369089, 738178, 1476356, 2952712, 5905424, 5979345
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 641, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 295168, 369089, 738178, 1476356, 2952712, 3026633, 5979345
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 641, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 221505, 369089, 738178, 1476356, 2952712, 5905424, 5979345
1, 2, 4, 8, 16, 32, 64, 128, 129, 256, 512, 641, 1153, 2306, 4612, 9224, 18448, 36896, 73792, 73921, 147584, 221505, 369089, 738178, 1476356, 2952712, 3026633, 5979345
1, 2, 4, 8, 16, 17, 32, 64, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 41472, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 5974144, 5979345
1, 2, 4, 8, 16, 17, 32, 64, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 41472, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 2992273, 5979345
1, 2, 4, 8, 16, 17, 32, 64, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 25937, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 5974144, 5979345
1, 2, 4, 8, 16, 17, 32, 64, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 25937, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 2992273, 5979345
1, 2, 4, 8, 16, 17, 32, 49, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 41472, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 5974144, 5979345
1, 2, 4, 8, 16, 17, 32, 49, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 41472, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 2992273, 5979345
1, 2, 4, 8, 16, 17, 32, 49, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 25937, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 5974144, 5979345
1, 2, 4, 8, 16, 17, 32, 49, 81, 162, 324, 648, 1296, 2592, 5184, 5201, 10368, 20736, 25937, 46673, 93346, 186692, 373384, 746768, 1493536, 2987072, 2992273, 5979345
Here we have \(l(n)=27\) which the conjecture suggests at least one addition chain will have 13-star steps at its end. It has at most 11 though.
We find that 5979345 matches the 13 bit expression in the 5 small step enumeration:
@(a)+@(b)+@(c)+@(-a+b+c)+@(d)+@(-a+c+d)+@(e)+@(f)+@(-a+b+e)+@(-b+d+f)+@(-a+d+e)+@(-c+e+f)+@(-b-c+d+e+f)
So we have an infinite sequence of double star step numbers of the form:
\(2^a+2^b+2^c+2^{-a+b+c}+2^d+2^{-a+c+d}+2^e+2^f+2^{-a+b+e}+2^{-b+d+f}+2^{-a+d+e}+2^{-c+e+f}+2^{-b-c+d+e+f}\)
[1] Bahig HM (2011), "Star reduction among minimal length addition chains", Computing. Vol. 91(4), pp. 335-352. Springer.