A091838 - OEIS

%I #12 Jan 17 2019 15:57:42

%S 1,2,4,7,11,18,29,47,76,121,199,310,521,841,1364,2207,3571,5776,9349,

%T 15125,24476,39601,64079,103682,167761,271441,439204,710645,1149851,

%U 1860496,3010349,4870847,7881196,12752041,20633239,33385280,54018521,87403801

%N a(n) is the number of images of the border correlation function for binary words of length n (cf. link).

%C Values for even indices seem mysterious, but does A091838(2n+1) = A002878(n), the bisection of Lucas sequence?

%H Tero Harju, <a href="http://users.utu.fi/harju/combwords.htm">Combinatorics on Words</a> - From _N. J. A. Sloane_, Aug 02 2012

%H T. Harju and D. Nowotka, <a href="http://www.tucs.fi/Publications/attachment.php?fname=TR546.pdf">Border correlation of binary words</a>.

%F a(n) < 2^(n-1)

%F a(n) <= F(n) + F(n-2) - m where F(i) is the i-th Fibonacci number and m=2 if n is in the set {2i | i >= 0} - {2^j, 3x2^j | j >= 0}. - Dirk Nowotka (nowotka(AT)utu.fi), May 16 2004

%F a(n) seems to be asymptotic to phi^n where phi=(1+sqrt(5))/2.

%K nonn

%O 1,2

%A _Benoit Cloitre_, based on the Harju and Nowotka paper, Mar 10 2004

%E More terms from Dirk Nowotka (nowotka(AT)utu.fi), May 16 2004

%E a(31)-a(38) from _Lars Blomberg_, Jan 17 2019