login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

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 - 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[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

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

N. J. A. Sloane

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.

License Agreements, Terms of Use, Privacy Policy. .

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