

A266082


Length of shortest Fibonacci addition chain for n.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


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.


LINKS

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


EXAMPLE

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.


CROSSREFS

Cf. A003313, A000045.
Sequence in context: A274010 A213711 A072649 * A105195 A257569 A039836
Adjacent sequences: A266079 A266080 A266081 * A266083 A266084 A266085


KEYWORD

nonn,nice


AUTHOR

Franklin T. AdamsWatters, Dec 21 2015


EXTENSIONS

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


STATUS

approved



