The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. (Formerly M0324 N0121) 39
 1, 1, 1, 2, 2, 4, 6, 10, 16, 30, 52, 94, 172, 316, 586, 1096, 2048, 3856, 7286, 13798, 26216, 49940, 95326, 182362, 349536, 671092, 1290556, 2485534, 4793492, 9256396, 17895736, 34636834, 67108864, 130150588, 252645136, 490853416 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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. 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). Number of binary necklaces with an odd number of zeros. - Joerg Arndt, Oct 26 2015 Also, number of subsets of {1,2,...,n-1} which sum to 0 modulo n (cf. A063776). - Max Alekseyev, Mar 26 2016 From Gus Wiseman, Sep 14 2019: (Start) Also the number of subsets of {1..n} containing n whose mean is an element. For example, the a(1) = 1 through a(8) = 16 subsets are:   1  2  3    4    5      6      7        8         123  234  135    246    147      258                   345    456    357      468                   12345  1236   567      678                          1456   2347     1348                          23456  2567     1568                                 12467    3458                                 13457    3678                                 34567    12458                                 1234567  14578                                          23578                                          24568                                          45678                                          123468                                          135678                                          2345678 (End) REFERENCES B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252. S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 172. J. Hedetniemi and K. R. Hutson, Equilibrium of shortest path load in ring network, Congressus Numerant., 203 (2010), 75-95. See p. 83. N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). 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. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). D. Stoffer, Delay equations with rapidly oscillating stable periodic solutions, J. Dyn. Diff. Eqs. 20 (1) (2008) 201, eq. (39) LINKS T. D. Noe and Seiichi Manyama, Table of n, a(n) for n = 0..3334 (first 201 terms from T. D. Noe) A. E. Brouwer, The Enumeration of Locally Transitive Tournaments, Math. Centr. Report ZW138, Amsterdam, 1980. S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk, Estimating the size of correcting codes using extremal graph problems, Optimization, 227-243, Springer Optim. Appl., 32, Springer, New York, 2009. P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5. R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. Math. Monthly, 113 (2006), 887-896. A. A. Kulkarni, N. Kiyavash and R. Sreenivas, On the Varshamov-Tenengolts Construction on Binary Strings, 2013. R. Pries and C. Weir, The Ekedahl-Oort type of Jacobians of Hermitian curves, arXiv preprint arXiv:1302.6261 [math.NT], 2013. N. J. A. Sloane, On single-deletion-correcting codes N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs FORMULA a(n) = Sum_{odd d divides n} (phi(d)*2^(n/d))/(2*n), n>0. a(n) = A063776(n)/2. a(n) = 2^n - A327477(n). - Gus Wiseman, Sep 14 2019 EXAMPLE For n=3 the 2 output sequences are 000111000111... and 010101... For n=5 the 4 output sequences are those with periodic parts {0000011111, 0001011101, 0010011011, 01}. MAPLE 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; MATHEMATICA a = 1; a[n_] := Sum[Mod[k, 2] EulerPhi[k]*2^(n/k)/(2*n), {k, Divisors[n]}]; Table[a[n], {n, 0, 35}](* Jean-François Alcover, Feb 17 2012, after Pari *) PROG (PARI) a(n)=if(n<1, n >= 0, sumdiv(n, k, (k%2)*eulerphi(k)*2^(n/k))/(2*n)); (Haskell) a000016 0 = 1 a000016 n = (`div` (2 * n)) \$ sum \$    zipWith (*) (map a000010 oddDivs) (map ((2 ^) . (div n)) \$ oddDivs)    where oddDivs = a182469_row n -- Reinhard Zumkeller, May 01 2012 CROSSREFS The main diagonal of table A068009, the left edge of triangle A053633. Cf. A000048, A000031, A000013, A053634, A182469. Subsets whose mean is an element are A065795. Dominated by A082550. Partitions containing their mean are A237984. Subsets containing n but not their mean are A327477. Cf. A051293, A135342, A240850, A327471, A327478. Sequence in context: A084202 A300865 A053637 * A060553 A293673 A293505 Adjacent sequences:  A000013 A000014 A000015 * A000017 A000018 A000019 KEYWORD nonn,nice,easy AUTHOR EXTENSIONS More terms from Michael Somos, Dec 11 1999 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 10 02:05 EDT 2020. Contains 335570 sequences. (Running on oeis4.)