%I A000016 M0324 N0121
%S A000016 1,1,1,2,2,4,6,10,16,30,52,94,172,316,586,1096,2048,3856,7286,13798,
%T A000016 26216,49940,95326,182362,349536,671092,1290556,2485534,4793492,
%U A000016 9256396,17895736,34636834,67108864,130150588,252645136,490853416
%N A000016 a(n) = number of distinct (infinite) output sequences from binary n-stage 
               shift register which feeds back the complement of the last stage. 
               E.g. for n=6 there are 6 such sequences.
%C A000016 Also a(n+1) = number of distinct (infinite) output sequences from binary 
               n-stage shift register which feeds back the complement of the sum 
               of its contents. E.g. for n=5 there are 6 such sequences.
%C A000016 Also a(n+1) = number of binary vectors (x_1,...x_n) satisfying Sum_{i=1..n} 
               i*x_i = 0 (mod n+1) = size of Varshamov-Tenengolts code VT_0(n). 
               E.g. |VT_0(5)| = 6 = a(6).
%D A000016 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000016 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000016 A. E. Brouwer, The Enumeration of Locally Transitive Tournaments. Math. 
               Centr. Report ZW138, Amsterdam, 1980.
%D A000016 S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk, Estimating 
               the size of correcting codes using extremal graph problems, in Optimization: 
               Structure and Applications, edited by Charles Pearce, Kluwer, to 
               appear, 2003.
%D A000016 B. D. Ginsburg, On a number theory function applicable in coding theory, 
               Problemy Kibernetiki, No. 19 (1967), pp. 249-252.
%D A000016 S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, 
               p. 172.
%D A000016 R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. 
               Math. Monthly, 113 (2006), 887-896.
%D A000016 N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs 
               (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. 
               Publ., 10, de Gruyter, Berlin, 2002.
%H A000016 T. D. Noe, <a href="b000016.txt">Table of n, a(n) for n = 0..200</a>
%H A000016 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               Sequences realized by oligomorphic permutation groups</a>, J. Integ. 
               Seqs. Vol. 3 (2000), #00.1.5.
%H A000016 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/doc/dijen.txt">
               On single-deletion-correcting codes</a>
%H A000016 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/doc/graphs.html">
               Challenge Problems: Independent Sets in Graphs</a>
%H A000016 <a href="Sindx_To.html#tournament">Index entries for sequences related 
               to tournaments</a>
%H A000016 <a href="Sindx_Ne.html#necklaces">Index entries for sequences related 
               to necklaces</a>
%H A000016 <a href="Sindx_Su.html#subsetsums">Index entries for sequences related 
               to subset sums modulo m</a>
%F A000016 Sum {odd d divides n } (phi(d)*2^(n/d))/(2n), n>0.
%e A000016 For n=3 the 2 output sequences are 000111000111... and 010101...
%e A000016 For n=4 the 4 output sequences are those with periodic parts {0000011111, 
               0001011101, 0010011011, 01}.
%p A000016 with(numtheory); A000016 := proc(n) local d,t1; if n = 0 then RETURN(1) 
               else t1 := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 
               then t1 := t1+phi(d)*2^(n/d)/(2*n); fi; od; RETURN(t1); fi; end;
%o A000016 (PARI) a(n)=if(n<1,n >= 0,sumdiv(n,k,(k%2)*eulerphi(k)*2^(n/k))/(2*n)).
%Y A000016 Cf. A000048, A000031, A000013. The main diagonal of table A068009, the 
               left edge of triangle A053633. Equals A063776(n)/2.
%Y A000016 Sequence in context: A163733 A084202 A053637 this_sequence A060553 A032307 
               A007560
%Y A000016 Adjacent sequences: A000013 A000014 A000015 this_sequence A000017 A000018 
               A000019
%K A000016 nonn,nice,easy
%O A000016 0,4
%A A000016 N. J. A. Sloane (njas(AT)research.att.com).
%E A000016 More terms from Michael Somos