|
%I #24 Jan 06 2017 11:42:28
%S 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,
%T 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,
%U 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
%N Smallest index of a Fibonacci-like sequence containing n, see comments.
%C 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.
%H Charles R Greathouse IV, <a href="/A249783/b249783.txt">Table of n, a(n) for n = 0..10000</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F a(n) <= A054495(n) <= n. - _Charles R Greathouse IV_, Nov 06 2014
%e For n = 0, the trivial sequence 0, 0, 0, ... has index 0.
%e For n = 5, the classic Fibonacci sequence 0, 1, 1, 2, 3, 5, ... contains 5 and has index 1.
%e For n = 7, the Lucas sequence 2, 1, 3, 4, 7, ... contains 7, and no such sequence with a smaller index contains 7.
%t 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 *)
%o (Haskell)
%o bi x y = if (x<y) then (x+y) else (bi y (x-y))
%o a249783 0 = 0
%o a249783 n = minimum (map (bi n) [0..(n-1)])
%o (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
%Y 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.
%K nonn,look,nice
%O 0,5
%A _Allan C. Wechsler_, Nov 05 2014
%E Extended by _Charles R Greathouse IV_, Nov 06 2014
|
