cp's OEIS Frontend

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.

%I A000016 M0324 N0121 #143 Apr 16 2025 03:02:47
%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) is the number of distinct (infinite) output sequences from binary n-stage shift register which feeds back the complement of the last stage.
%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).
%C A000016 Number of binary necklaces with an odd number of zeros. - _Joerg Arndt_, Oct 26 2015
%C A000016 Also, number of subsets of {1,2,...,n-1} which sum to 0 modulo n (cf. A063776). - _Max Alekseyev_, Mar 26 2016
%C A000016 From _Gus Wiseman_, Sep 14 2019: (Start)
%C A000016 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:
%C A000016   1  2  3    4    5      6      7        8
%C A000016         123  234  135    246    147      258
%C A000016                   345    456    357      468
%C A000016                   12345  1236   567      678
%C A000016                          1456   2347     1348
%C A000016                          23456  2567     1568
%C A000016                                 12467    3458
%C A000016                                 13457    3678
%C A000016                                 34567    12458
%C A000016                                 1234567  14578
%C A000016                                          23578
%C A000016                                          24568
%C A000016                                          45678
%C A000016                                          123468
%C A000016                                          135678
%C A000016                                          2345678
%C A000016 (End)
%C A000016 Number of self-dual binary necklaces with 2n beads (cf. A263768, A007147). - _Bernd Mulansky_, Apr 25 2023
%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 J. Hedetniemi and K. R. Hutson, Equilibrium of shortest path load in ring network, Congressus Numerant., 203 (2010), 75-95. See p. 83.
%D A000016 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%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.
%D A000016 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000016 D. Stoffer, Delay equations with rapidly oscillating stable periodic solutions, J. Dyn. Diff. Eqs. 20 (1) (2008) 201, eq. (39)
%H A000016 Seiichi Manyama, <a href="/A000016/b000016.txt">Table of n, a(n) for n = 0..3334</a> (first 201 terms from T. D. Noe)
%H A000016 Nicolás Álvarez, Victória Becher, Martín Mereb, Ivo Pajor, and Carlos Miguel Soto, <a href="https://www-2.dc.uba.ar/staff/becher/papers/extremal.pdf">On extremal factors of de Bruijn-like graphs</a>, Univ. Buenos Aires (Argentina 2023). See also <a href="https://arxiv.org/abs/2308.16257">arXiv:2308.16257</a> [math.CO], 2023. See references.
%H A000016 Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 17.
%H A000016 A. E. Brouwer, <a href="https://ir.cwi.nl/pub/6805">The Enumeration of Locally Transitive Tournaments</a>, Math. Centr. Report ZW138, Amsterdam, 1980.
%H A000016 S. Butenko, P. Pardalos, I. Sergienko, V. P. Shylo and P. Stetsyuk, <a href="http://dx.doi.org/10.1007/978-0-387-98096-6_12">Estimating the size of correcting codes using extremal graph problems</a>, Optimization, 227-243, Springer Optim. Appl., 32, Springer, New York, 2009.
%H A000016 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H A000016 Sébastien Designolle, Tamás Vértesi, and Sebastian Pokutta, <a href="https://arxiv.org/abs/2310.20677">Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms</a>, arXiv:2310.20677 [quant-ph], 2023.
%H A000016 T. M. A. Fink, <a href="https://arxiv.org/abs/2302.05314">Exact dynamics of the critical Kauffman model with connectivity one</a>, arXiv:2302.05314 [cond-mat.stat-mech], 2023.
%H A000016 R. W. Hall and P. Klingsberg, <a href="http://www.jstor.org/stable/27642087">Asymmetric rhythms and tiling canons</a>, Amer. Math. Monthly, 113 (2006), 887-896.
%H A000016 A. A. Kulkarni, N. Kiyavash and R. Sreenivas, <a href="http://www.sc.iitb.ac.in/~ankur/docs/CombinInsightDM_final.pdf">On the Varshamov-Tenengolts Construction on Binary Strings</a>, 2013.
%H A000016 E. M. Palmer and R. W. Robinson, <a href="http://projecteuclid.org/euclid.pjm/1102711113">Enumeration of self-dual configurations</a>, Pacific J. Math., 110 (1984), 203-221.
%H A000016 R. Pries and C. Weir, <a href="http://arxiv.org/abs/1302.6261">The Ekedahl-Oort type of Jacobians of Hermitian curves</a>, arXiv preprint arXiv:1302.6261 [math.NT], 2013.
%H A000016 N. J. A. Sloane, <a href="http://neilsloane.com/doc/dijen.txt">On single-deletion-correcting codes</a>
%H A000016 N. J. A. Sloane, <a href="/A265032/a265032.html">Challenge Problems: Independent Sets in Graphs</a>
%H A000016 Yan Bo Ti, Gabriel Verret, and Lukas Zobernig, <a href="https://arxiv.org/abs/2203.08401">Abelian Varieties with p-rank Zero</a>, arXiv:2203.08401 [math.NT], 2022.
%H A000016 Antonio Vera López, Luis Martínez, Antonio Vera Pérez, Beatriz Vera Pérez, and Olga Basova, <a href="https://doi.org/10.1016/j.laa.2017.05.027">Combinatorics related to Higman's conjecture I: Parallelogramic digraphs and dispositions</a>, Linear Algebra Appl. 530, 414-444 (2017).
%H A000016 <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>
%H A000016 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%H A000016 <a href="/index/Su#subsetsums">Index entries for sequences related to subset sums modulo m</a>
%F A000016 a(n) = Sum_{odd d divides n} (phi(d)*2^(n/d))/(2*n), n>0.
%F A000016 a(n) = A063776(n)/2.
%F A000016 a(n) = 2^(n-1) - A327477(n). - _Gus Wiseman_, Sep 14 2019
%e A000016 For n=3 the 2 output sequences are 000111000111... and 010101...
%e A000016 For n=5 the 4 output sequences are those with periodic parts {0000011111, 0001011101, 0010011011, 01}.
%e A000016 For n=6 there are 6 such sequences.
%p A000016 A000016 := proc(n) local d, t; if n = 0 then return 1 else t := 0; for d from 1 to n do if n mod d = 0 and d mod 2 = 1 then t := t + NumberTheory:-Totient(d)* 2^(n/d)/(2*n) fi od; return t fi end:
%t A000016 a[0] = 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 *)
%o A000016 (PARI) a(n)=if(n<1,n >= 0,sumdiv(n,k,(k%2)*eulerphi(k)*2^(n/k))/(2*n));
%o A000016 (Haskell)
%o A000016 a000016 0 = 1
%o A000016 a000016 n = (`div` (2 * n)) $ sum $
%o A000016    zipWith (*) (map a000010 oddDivs) (map ((2 ^) . (div n)) $ oddDivs)
%o A000016    where oddDivs = a182469_row n
%o A000016 -- _Reinhard Zumkeller_, May 01 2012
%o A000016 (Python)
%o A000016 from sympy import totient, divisors
%o A000016 def A000016(n): return sum(totient(d)<<n//d-1 for d in divisors(n>>(~n&n-1).bit_length(),generator=True))//n if n else 1 # _Chai Wah Wu_, Feb 21 2023
%Y A000016 The main diagonal of table A068009, the left edge of triangle A053633.
%Y A000016 Cf. A000048, A000031, A000013, A053634, A182469.
%Y A000016 Subsets whose mean is an element are A065795.
%Y A000016 Dominated by A082550.
%Y A000016 Partitions containing their mean are A237984.
%Y A000016 Subsets containing n but not their mean are A327477.
%Y A000016 Cf. A051293, A135342, A240850, A327471, A327478.
%K A000016 nonn,nice,easy
%O A000016 0,4
%A A000016 _N. J. A. Sloane_
%E A000016 More terms from _Michael Somos_, Dec 11 1999