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

Author

Allan C. Wechsler, Nov 05 2014

Keywords

• nonn
• look
• nice

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.

Examples

			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.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
• Index to sequences related to the complexity of n

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.

Programs

Haskell

bi x y = if (x
				

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[BJean-François Alcover, Jan 06 2017, translated from PARI *)

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(BCharles R Greathouse IV, Nov 06 2014

Formula

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

Extensions

Extended by Charles R Greathouse IV, Nov 06 2014