*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:

5784689 |
11568241 |
11569378 |
11669785 |
11671825 |
11682841 |
23097633 |
23105761 |
23135345 |
23136482 |

23138756 |
23139905 |
23233585 |
23339545 |
23339570 |
23343633 |
23343650 |
23365682 |
31942247 |
32364653 |

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