login
This site is supported by donations to The OEIS 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)
28
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

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

LINKS

T. D. Noe, Table of n, a(n) for n = 0..200

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.

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.

Sequence in context: A270925 A084202 A053637 * A060553 A032307 A007560

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 1 00:20 EDT 2016. Contains 274317 sequences.