The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000016 a(n) is the number of distinct (infinite) output sequences from binary n-stage shift register which feeds back the complement of the last stage. (Formerly M0324 N0121) 40
 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 Yan Bo Ti, Gabriel Verret, and Lukas Zobernig, Abelian Varieties with p-rank Zero, arXiv:2203.08401 [math.NT], 2022. Vera López, Antonio; Martínez, Luis; Vera Pérez, Antonio; Vera Pérez, Beatriz; Basova, Olga Combinatorics related to Higman’s conjecture. I: Parallelogramic digraphs and dispositions,  Linear Algebra Appl. 530, 414-444 (2017). 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}. For n=6 there are 6 such sequences. 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 A344707 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 28 01:47 EDT 2022. Contains 357063 sequences. (Running on oeis4.)