login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. Adams-Watters, Dec 21 2015

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 19 15:17 EDT 2021. Contains 347564 sequences. (Running on oeis4.)