|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
