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)

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

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)

Number of self-dual binary necklaces with 2n beads (cf. A263768, A007147). - Bernd Mulansky, Apr 25 2023

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

Seiichi Manyama, Table of n, a(n) for n = 0..3334 (first 201 terms from T. D. Noe)

Nicolás Álvarez, Victória Becher, Martín Mereb, Ivo Pajor, and Carlos Miguel Soto, On extremal factors of de Bruijn-like graphs, Univ. Buenos Aires (Argentina 2023).

Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 17.

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.

Sébastien Designolle, Tamás Vértesi, and Sebastian Pokutta, Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms, arXiv:2310.20677 [quant-ph], 2023.

T. M. A. Fink, Exact dynamics of the critical Kauffman model with connectivity one, arXiv:2302.05314 [cond-mat.stat-mech], 2023.

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.

E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations, Pacific J. Math., 110 (1984), 203-221.

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.

Antonio Vera López, Luis Martínez, Antonio Vera Pérez, Beatriz Vera Pérez, and Olga Basova, Combinatorics related to Higman’s conjecture. I: Parallelogramic digraphs and dispositions, Linear Algebra Appl. 530, 414-444 (2017).

Index entries for sequences related to tournaments

Index entries for sequences related to necklaces

Index entries for sequences related to subset sums modulo m

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-1) - 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

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:

Mathematica

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 *)

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
(Python)
from sympy import totient, divisors
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

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 * A361223 A060553 A293673

Adjacent sequences: A000013 A000014 A000015 * A000017 A000018 A000019

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

More terms from Michael Somos, Dec 11 1999

Status

approved