|
%I M0324 N0121 #135 Mar 09 2024 11:22:45
%S 1,1,1,2,2,4,6,10,16,30,52,94,172,316,586,1096,2048,3856,7286,13798,
%T 26216,49940,95326,182362,349536,671092,1290556,2485534,4793492,
%U 9256396,17895736,34636834,67108864,130150588,252645136,490853416
%N 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 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 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 Number of binary necklaces with an odd number of zeros. - _Joerg Arndt_, Oct 26 2015
%C Also, number of subsets of {1,2,...,n-1} which sum to 0 modulo n (cf. A063776). - _Max Alekseyev_, Mar 26 2016
%C From _Gus Wiseman_, Sep 14 2019: (Start)
%C 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 1 2 3 4 5 6 7 8
%C 123 234 135 246 147 258
%C 345 456 357 468
%C 12345 1236 567 678
%C 1456 2347 1348
%C 23456 2567 1568
%C 12467 3458
%C 13457 3678
%C 34567 12458
%C 1234567 14578
%C 23578
%C 24568
%C 45678
%C 123468
%C 135678
%C 2345678
%C (End)
%C Number of self-dual binary necklaces with 2n beads (cf. A263768, A007147). - _Bernd Mulansky_, Apr 25 2023
%D B. D. Ginsburg, On a number theory function applicable in coding theory, Problemy Kibernetiki, No. 19 (1967), pp. 249-252.
%D S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 172.
%D J. Hedetniemi and K. R. Hutson, Equilibrium of shortest path load in ring network, Congressus Numerant., 203 (2010), 75-95. See p. 83.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D D. Stoffer, Delay equations with rapidly oscillating stable periodic solutions, J. Dyn. Diff. Eqs. 20 (1) (2008) 201, eq. (39)
%H 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 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).
%H 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 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 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 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 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 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 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 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 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 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 N. J. A. Sloane, <a href="http://neilsloane.com/doc/dijen.txt">On single-deletion-correcting codes</a>
%H N. J. A. Sloane, <a href="/A265032/a265032.html">Challenge Problems: Independent Sets in Graphs</a>
%H 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 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 <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%H <a href="/index/Su#subsetsums">Index entries for sequences related to subset sums modulo m</a>
%F a(n) = Sum_{odd d divides n} (phi(d)*2^(n/d))/(2*n), n>0.
%F a(n) = A063776(n)/2.
%F a(n) = 2^(n-1) - A327477(n). - _Gus Wiseman_, Sep 14 2019
%e For n=3 the 2 output sequences are 000111000111... and 010101...
%e For n=5 the 4 output sequences are those with periodic parts {0000011111, 0001011101, 0010011011, 01}.
%e For n=6 there are 6 such sequences.
%p 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 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 (PARI) a(n)=if(n<1,n >= 0,sumdiv(n,k,(k%2)*eulerphi(k)*2^(n/k))/(2*n));
%o (Haskell)
%o a000016 0 = 1
%o a000016 n = (`div` (2 * n)) $ sum $
%o zipWith (*) (map a000010 oddDivs) (map ((2 ^) . (div n)) $ oddDivs)
%o where oddDivs = a182469_row n
%o -- _Reinhard Zumkeller_, May 01 2012
%o (Python)
%o from sympy import totient, divisors
%o 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 The main diagonal of table A068009, the left edge of triangle A053633.
%Y Cf. A000048, A000031, A000013, A053634, A182469.
%Y Subsets whose mean is an element are A065795.
%Y Dominated by A082550.
%Y Partitions containing their mean are A237984.
%Y Subsets containing n but not their mean are A327477.
%Y Cf. A051293, A135342, A240850, A327471, A327478.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_
%E More terms from _Michael Somos_, Dec 11 1999
| 