|
| |
|
|
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)
|
|
27
|
|
|
|
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).
|
|
|
REFERENCES
|
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.
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.
R. W. Hall and P. Klingsberg, Asymmetric rhythms and tiling canons, Amer. Math. Monthly, 113 (2006), 887-896.
J. Hedetniemi and K. R. Hutson, Equilibrium of shortest path load in ring network, Congressus Numerant., 203 (2010), 75-95. See p. 83.
R. Pries and C. Weir, The Ekedahl-Oort type of Jacobians of Hermitian curves, arXiv preprint arXiv:1302.6261, 2013
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
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
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
|
Sum {odd d divides n } (phi(d)*2^(n/d))/(2n), n>0.
|
|
|
EXAMPLE
|
For n=3 the 2 output sequences are 000111000111... and 010101...
For n=4 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}](* From 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
|
Cf. A000048, A000031, A000013. The main diagonal of table A068009, the left edge of triangle A053633. Equals A063776(n)/2.
Cf. A182469.
Sequence in context: A198834 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
|
|
|
STATUS
|
approved
|
| |
|
|
