A266082 Length of shortest Fibonacci addition chain for n.

0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 8, 8, 9, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 9, 9, 9, 9, 10, 10, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 9

Offset: 1

Author

Franklin T. Adams-Watters, Dec 21 2015

Keywords

• nonn
• nice

Comments

By Fibonacci addition chain is meant an addition chain where no doubling steps are allowed. The fastest growing chains of this type are the Fibonacci numbers, as compared with the powers of 2 for an unrestricted addition chain. The chain is considered to start with 2 1's, so that the 2 can be generated.

These chains provide ways to generate the product x^n in some abstract system where for some reason squaring is expensive, perhaps because multiplying involves temporarily changing the input values. There are no obvious actual practical applications.

Based on that, one might want to allow copying a value in the chain as an elementary operation. However, this is not necessary: one can just repeat the sum used to generate the number. Further, even that is not necessary to generate a minimal length chain. If k is in the chain, the only possible use for another copy of it is to generate 2k. But if k was generated as i+j, one can replace k, k, ..., 2k with k, ..., k+i, ..., k+i+j, and the last is equal to 2k.

One can generate a power tree for these chains, but it is less useful than for general addition chains. Generating it the same way fails to find a minimal chain for 12. One does somewhat better reversing the standard procedure and genating the larger values first; this fails to be minimal first for 25.

Examples

			The only Fibonacci addition chains of length 2 are 1, 1, 2, 3 and 1, 1, 2, 2. Neither generates 4. However, 4 can be appended to either of them to get a chain of length 3. Hence a(4) = 3.
a(30) = 7 because there is no shorter chain than 1, 1, 2, 3, 5, 8, 11, 19, 30.
		

Links

• Lars Blomberg, Table of n, a(n) for n = 1..233

Crossrefs

Cf. A003313, A000045.

Extensions

Corrected a(30) by Lars Blomberg, Mar 16 2017