%I A003000 M0328
%S A003000 1,2,2,4,6,12,20,40,74,148,284,568,1116,2232,4424,8848,17622,35244,
%T A003000 70340,140680,281076,562152,1123736,2247472,4493828,8987656,17973080,
%U A003000 35946160,71887896,143775792,287542736,575085472,1150153322,2300306644
%N A003000 Number of "bifix-free" words of length n over a two-letter alphabet.
%C A003000 Many authors use the term "unbordered" for "bifix-free". The Lothaire 
               (1997) reference refers to bifix-free words as primary words (Chapter 
               8). - David Callan (callan(AT)stat.wisc.edu), Sep 25 2006
%D A003000 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A003000 G. Blom, Problem 94-20: Overlapping binary sequences, SIAM Review 37 
               (1995), 619-620.
%D A003000 L. J. Guibas and A. M. Odlyzko; Periods in Strings, Journal of Combinatorial 
               Theory A 30 (1981) 19-42. Their L_n(0) is A003000[n].
%D A003000 H. Harborth, Endliche 0-1-Folgen mit gleichen Teilbl\"ocken, J. f\"ur 
               Reine Angewandte Math. 271 (1974), 139-154, see p. 143.
%D A003000 P. Tolstrup Nielsen, A note on bifix-free sequences, IEEE Trans. Info. 
               Theory IT-19 (1973), 704-706.
%D A003000 M. Lothaire, Combinatorics on Words, Cambridge University Press, NY, 
               1997.
%H A003000 D. J. Greaves and S. J. Montgomery-Smith, <a href="http://www.math.missouri.edu/
               ~stephen/preprints/unforgeable/">Unforgeable Marker Sequences</a>
               .
%H A003000 T. Harju and D. Nowotka, <a href="http://www.tucs.fi/Publications/attachment.php?fname=TR546.pdf">
               Border correlation of binary words</a>.
%H A003000 Guy P. Srinivasan, <a href="a122536.txt">Java program for this sequence 
               and A122536</a>
%F A003000 a(2n+1) = 2a(2n), a(2n) = 2a(2n-1) - a(n).
%F A003000 A003000[n]/2^n converges to 0.2677868402178891123766714035843025525550598979934845320763118885112149...
%F A003000 a(0)=1; a(n)=2*a(n-1)-1/2*(1+(-1)^n)*a([n/2]). - Farideh Firoozbakht 
               (mymontain(AT)yahoo.com), Jun 10 2004
%t A003000 a[0]=1;a[n_]:=a[n]=2*a[n-1]-(1+(-1)^n)/2*a[Floor[n/2]]; Table[a[n], {n, 
               0, 34}]
%t A003000 a[0]=1; a[n_]:=a[n]=2*a[n-1]-If[EvenQ[n], a[n/2], 0] (Ed Pegg, Jr., (ed(AT)mathpuzzle.com), 
               Jan 05 2005)
%Y A003000 Equals 2 * A045690 for n > 0. Complement gives A094536. Cf. A019308, 
               A019309, A094536, A094537.
%Y A003000 Cf. A094536, A094537.
%Y A003000 Sequence in context: A001679 A030435 A063886 this_sequence A122536 A128209 
               A052953
%Y A003000 Adjacent sequences: A002997 A002998 A002999 this_sequence A003001 A003002 
               A003003
%K A003000 nonn,easy,nice
%O A003000 0,2
%A A003000 N. J. A. Sloane (njas(AT)research.att.com).
%E A003000 New description and reference from Jeffrey Shallit Sep 15 1996. Additional 
               comments from TORSTEN.SILLKE(AT)LHSYSTEMS.COM, Jan 17, 2001.
%E A003000 More terms from Farideh Firoozbakht (mymontain(AT)yahoo.com), Jun 10 
               2004