A249783 Smallest index of a Fibonacci-like sequence containing n, see comments.

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

Offset

0,5

Comments

Any two nonnegative integers F0 and F1 generate a Fibonacci-like sequence where for n > 1, Fn = F[n-1] + F[n-2]. Call F0 + F1 the "index" of such a sequence. In this sequence, a(n) is the smallest occurring index of any Fibonacci-like sequence containing n.

Links

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Index to sequences related to the complexity of n

Formula

a(n) <= A054495(n) <= n. - Charles R Greathouse IV, Nov 06 2014

Example

For n = 0, the trivial sequence 0, 0, 0, ... has index 0.
For n = 5, the classic Fibonacci sequence 0, 1, 1, 2, 3, 5, ... contains 5 and has index 1.
For n = 7, the Lucas sequence 2, 1, 3, 4, 7, ... contains 7, and no such sequence with a smaller index contains 7.

Mathematica

a[n_] := Module[{a, k, A, B}, If[n<2, Return[n]]; For[k=1, k <= n-1, k++, For[a=0, a <= k-1, a++, A=a; B=k-A; While[B<n, {A, B} = {B, A+B}]; If[B == n, Return[k]]]]; n]; Array[a, 101, 0] (* Jean-François Alcover, Jan 06 2017, translated from PARI *)

Prog

(Haskell)
bi x y = if (x<y) then (x+y) else (bi y (x-y))
a249783 0 = 0
a249783 n = minimum (map (bi n) [0..(n-1)])
(PARI) a(n)=if(n<2, return(n)); for(k=1, n-1, for(a=0, k-1, my(A=a, B=k-A); while(B<n, [A, B]=[B, A+B]); if(B==n, return(k)))); n \\ Charles R Greathouse IV, Nov 06 2014

Crossrefs

If n > 0 is an element of A000045, a(n) = 1. If n > 2 is twice such an element, a(n) = 2. If n > 3 is an element of A000032 or of A022086, a(n) = 3.

Sequence in context: A231516 A048793 A344084 * A352964 A209278 A326921

Adjacent sequences: A249780 A249781 A249782 * A249784 A249785 A249786

Keyword

nonn,look,nice

Author

Allan C. Wechsler, Nov 05 2014

Extensions

Extended by Charles R Greathouse IV, Nov 06 2014

Status

approved