Star and \(l^0\) Chains

For mathematical definitions see the top-level Addition Chains.

We defined a star step of a chain as one that uses the prior element. We define a star chain as an addition chain where all steps use the prior element:

\(1=a_0<a_1<...<a_r, a_i=a_{i-1}+a_j,i>j\ge 0\)

This leads naturally to the definition of \(l^*(n)\) as the length of the shortest star chain for \(n\).
For those wanting data we have the \(l^*(n)\) for \(1\le n\le 2^{30} \) encoded as 4 values per byte. 2 bits per value. Using the encoding \(l^*(n)-\lambda(n)-\lceil \log_2(v(n))\rceil \) here:

addSt30.bits.gz

We also defined Hansen or \(l^0\) chains. We encode the same range of data for \(l^0(n)\) in the same way:

addl030.bits.gz

To make comparison easier we have the same range for \(l(n)\):

add30.bits.gz

There is an interesting deviation if we look at \(c(r)\) and define \(c^*(r)\) in the natural way. We find \(c(r)=c^*(r)\) for most tested cases with \(r\le 37\).
The exceptions being \(c(30)=14143037,c^*(30)=14110655,c(35)=298695487,c^*(35)=296221919\).

The first 20 non-Hansen (\(l^0(n)>l(n)\)) numbers are shown in this table:

These numbers are of interest as these are the known cases where the Scholz-Brauer conjecture (\(l(2^n-1)\le l(n)+n-1\)) is in doubt. The numbers marked in red, and blue have been checked and shown to not violate the Scholz-Brauer conjecture. Blue entries are continuations of other red entries. For example \(5784689\cdot2=11569378\). See my known chains on the repair page: Repair

I thought I would show this chain as it's different from the first non-Hansen which can be seen on the home page. We fail to underline when constructing 32 since when we constructed \(25=17+8\) it forced us to underline 17.
\(32=16+16\) though would require 17 not be underlined.

1, 2, 4, 8, 16, 17, 25, 32, 64, 89, 178, 356, 712, 1424, 2848, 5696, 11392, 22784, 45568, 45585, 91170, 182340, 364680, 729360, 1458720, 2917440, 5834880, 11669760, 11669785