A007147 -id:A007147 - cp's OEIS frontend

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.

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

N. J. A. Sloane

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

			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.

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)

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). See also arXiv:2308.16257 [math.CO], 2023. See references.
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

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.

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

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:

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

a(n)=if(n<1,n >= 0,sumdiv(n,k,(k%2)*eulerphi(k)*2^(n/k))/(2*n));

from sympy import totient, divisors
def A000016(n): return sum(totient(d)<>(~n&n-1).bit_length(),generator=True))//n if n else 1 # Chai Wah Wu, Feb 21 2023

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

More terms from Michael Somos, Dec 11 1999

A007148 Number of self-complementary 2-colored bracelets (turnover necklaces) with 2n beads.

Original entry on oeis.org

1, 2, 3, 6, 10, 20, 37, 74, 143, 284, 559, 1114, 2206, 4394, 8740, 17418, 34696, 69194, 137971, 275280, 549258, 1096286, 2188333, 4369162, 8724154, 17422652, 34797199, 69505908, 138845926, 277383872, 554189329, 1107297290, 2212558942

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations Pacific J. Math., 110 (1984), 203-221.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to bracelets

Cf. A000013, A000079, A007147.

Different from, but easily confused with, A045690 and A093371.

# see A245558
L := proc(n,k)
    local a,j ;
    a := 0 ;
    for j in numtheory[divisors](igcd(n,k)) do
        a := a+numtheory[mobius](j)*binomial(n/j,k/j) ;
    end do:
    a/n ;
end proc:
A007148 := proc(n)
    local a,k,l;
    a := 0 ;
    for k from 1 to n do
        for l in numtheory[divisors](igcd(n,k)) do
            a := a+L(n/l,k/l)*ceil(k/2/l) ;
        end do:
    end do:
    a;
end proc:
seq(A007148(n),n=1..20) ; # R. J. Mathar, Jul 23 2017

a[n_] := (1/2)*(2^(n-1) + Total[ EulerPhi[2*#]*2^(n/#) &  /@ Divisors[n]]/(2*n)); Table[ a[n], {n, 1, 33}] (* Jean-François Alcover, Oct 25 2011 *)

a(n)= (1/2) *(2^(n-1)+sumdiv(n,k,eulerphi(2*k)*2^(n/k))/(2*n))

from sympy import divisors, totient
def a(n):
    if n==1: return 1
    return 2**(n - 2) + sum(totient(2*d)*2**(n//d) for d in divisors(n))//(4*n)
print([a(n) for n in range(1, 31)]) # Indranil Ghosh, Jul 24 2017

a(n) = 2^(n-2) + (1/(4n)) * Sum_{d|n} phi(2d)*2^(n/d). - N. J. A. Sloane, Sep 25 2012

a(n) = (1/2)*(A000079(n-1) + A000013(n)).

Description corrected by Christian G. Bower

A263768 Number of necklaces with n beads colored white or red, where the number of white beads is odd and at least three and turning over is allowed.

Original entry on oeis.org

1, 1, 3, 4, 8, 11, 22, 33, 62, 101, 189, 324, 611, 1087, 2055, 3770, 7154, 13363, 25481, 48174, 92204, 175791, 337593, 647325, 1246862, 2400841, 4636389, 8956059, 17334800, 33570815, 65108061, 126355335, 245492243, 477284181, 928772649, 1808538354, 3524337979, 6872209823

Offset: 3

David Eppstein, Oct 25 2015

nonn

a(n) is also the number of non-isomorphic n-vertex undirected graphs forming an odd cycle with any number of degree-1 vertices attached to each cycle vertex. To transform a necklace into a graph of this type, create a cycle vertex for each white bead and a pendant vertex for each red bead, with each pendant vertex attached to the next clockwise cycle vertex. Since these are exactly the graphs of the n-vertex and n-edge linear thrackles, a(n) is also the number of non-isomorphic linear thrackles.

For any n there is a unique n-bead necklace where the number of white beads is 1. Hence this sequence is one less than the number of n-bead (0,1) bracelets with an odd number of 0's. - Andrew Howroyd, Feb 28 2017

			For n=5 the a(5)=3 solutions are: five white beads (a 5-cycle), three white beads and two red beads with the two red beads adjacent (a triangle with two pendant vertices attached at one triangle vertex), and three white beads and two red beads with the two red beads separated (a triangle with two of its vertices having a single pendant vertex attached).

Andrew Howroyd, Table of n, a(n) for n = 3..100
Bernd Mulansky and Andreas Potschka, A zonogon approach for computing small polygons of maximum perimeter, arXiv:2404.01841 [math.OC], 2024. See p. 9. See also Math. Program., 2025.

Cf. A227910, A007147, A000016.

Table[1/2*(2^Quotient[n - 1, 2] + Total@ Map[(Mod[#, 2]*EulerPhi[#]*2^(n/#) &), Divisors[n]]/(2 n)) - 1, {n, 3, 40}] (* Michael De Vlieger, Apr 10 2024, after Jean-François Alcover at A007147 *)

a(n) = (A000016(n) + A016116(n-1)) / 2 - 1. - Andrew Howroyd, Feb 28 2017

a(n) = A007147(n) - 1. - Bernd Mulansky, Mar 08 2023

a(21)-a(40) from Andrew Howroyd, Feb 28 2017

A059736 A class of polytopal spheres.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 4, 6, 16, 25, 52, 89, 175, 308, 593, 1066, 2031, 3743, 7124, 13330, 25445, 48134, 92160, 175743, 337541, 647269, 1246802, 2400776, 4636319, 8955984, 17334720, 33570730, 65107971, 126355239, 245492141, 477284073

Offset: 1

N. J. A. Sloane, Feb 09 2001

V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

A016116 := n->2^floor(n/2):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: A007147 := n->1/2*(A016116(n-1)+A000016(n)): A059736 := n->A007147(n) - floor(n^2/12) - 1: for j from 1 to 100 do printf(`%d,`, A059736(j)) od:

a[n_] := (1/2)*(2^Quotient[n - 1, 2] + Total[(Mod[#, 2]*EulerPhi[#]*2^(n/#) &) /@ Divisors[n]]/(2*n)) - Floor[n^2/12] - 1;
Array[a, 36] (* Jean-François Alcover, Aug 30 2019 *)

a(n) = A007147(n) - [n^2/12] - 1.

More terms from James Sellers, Feb 20 2001

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A007148 Number of self-complementary 2-colored bracelets (turnover necklaces) with 2n beads.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A263768 Number of necklaces with n beads colored white or red, where the number of white beads is odd and at least three and turning over is allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A059736 A class of polytopal spheres.

Views

Author

Keywords

Links

Programs

Maple

Mathematica

Formula

Extensions