A031367 -id:A031367 - cp's OEIS frontend

A006206 Number of aperiodic binary necklaces of length n with no subsequence 00, excluding the necklace "0".

1, 1, 1, 1, 2, 2, 4, 5, 8, 11, 18, 25, 40, 58, 90, 135, 210, 316, 492, 750, 1164, 1791, 2786, 4305, 6710, 10420, 16264, 25350, 39650, 61967, 97108, 152145, 238818, 374955, 589520, 927200, 1459960, 2299854, 3626200, 5720274, 9030450, 14263078

Offset: 1

N. J. A. Sloane and Frank Ruskey

Bau-Sen Du (1985/1989)'s Table 1 has this sequence, denoted A_{n,1}, as the second column. - Jonathan Vos Post, Jun 18 2007

			Necklaces are: 1, 10, 110, 1110; 11110, 11010, 111110, 111010, ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

James Spahlinger, Table of n, a(n) for n = 1..5000
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
Joerg Arndt, Matters Computational (The Fxtbook), p. 710.
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See 2nd line of Table 1 (p. 6).
Michael Baake, Joachim Hermisson, and Peter Pleasants, The torus parametrization of quasiperiodic LI-classes, J. Phys. A 30(9) (1997), 3029-3056.
Latham Boyle and Paul J. Steinhardt, Self-Similar One-Dimensional Quasilattices, arXiv:1608.08220 [math-ph], 2016.
D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
D. J. Broadhurst and D. Kreimer, Association of multiple zeta values with positive knots via Feynman diagrams up to 9 loops, arXiv:hep-th/9609128, 1996.
D. J. Broadhurst and D. Kreimer, Association of multiple zeta values with positive knots via Feynman diagrams up to 9 loops, Phys. Lett B., 393 (1997), 403-412.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. 3 (2000), #00.1.5.
M. Conder, S. Du, R. Nedela, and M. Skoviera, Regular maps with nilpotent automorphism group, Journal of Algebraic Combinatorics, 44(4) (2016), 863-874. ["... We note that the sequence h_n above agrees in all but the first term with the sequence A006206 in ..."]
Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem, Bull. Austral. Math. Soc. 31 (1985), 89-103. Corrigendum: 32 (1985), 159.
Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem, arXiv:0706.2297 [math.DS], 2007.
Bau-Sen Du, A Simple Method Which Generates Infinitely Many Congruence Identities, Fib. Quart. 27 (1989), 116-124.
Bau-Sen Du, A Simple Method Which Generates Infinitely Many Congruence Identities, arXiv:0706.2421 [math.NT], 2007.
Larry Ericksen, Primality Testing and Prime Constellations, Šiauliai Mathematical Seminar, 3(11), 2008; mentions this sequence.
R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, arXiv:0903.2514 [math.NT], 2009-2011; sequence gamma_{1,j}^(A).
A. Pakapongpun and T. Ward, Functorial Orbit counting, J. Integer Seqs. 12 (2009), #09.2.4; example 21.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs. 4 (2001), #01.2.1.
Robert Schneider, Andrew V. Sills, and Hunter Waldron, On the q-factorization of power series, arXiv:2501.18744 [math.CO], 2025. See p. 6.
Index entries for sequences related to Lyndon words

Cf. A006207 (A_{n,2}), A006208 (A_{n,3}), A006209 (A_{n,4}), A130628 (A_{n,5}), A208092 (A_{n,6}), A006210 (D_{n,2}), A006211 (D_{n,3}), A094392.
Cf. A001461 (partial sums), A000045, A008683, A027750.
Cf. A125951 and A113788 for similar sequences.

a006206 n = sum (map f $ a027750_row n) `div` n where
   f d = a008683 (n `div` d) * (a000045 (d - 1) + a000045 (d + 1))
-- Reinhard Zumkeller, Jun 01 2013

with(numtheory): with(combinat):
A006206 := proc(n) local sum; sum := 0; for d in divisors(n) do sum := sum + mobius(n/d)*(fibonacci(d+1)+fibonacci(d-1)) end do; sum/n; end proc:

a[n_] := Total[(MoebiusMu[n/#]*(Fibonacci[#+1] + Fibonacci[#-1]) & ) /@ Divisors[n]]/n;
(* or *) a[n_] := Sum[LucasL[k]*MoebiusMu[n/k], {k, Divisors[n]}]/n; Table[a[n], {n,100}] (* Jean-François Alcover, Jul 19 2011, after given formulas *)

a(n)=if(n<1,0,sumdiv(n,d,moebius(n/d)*(fibonacci(d-1)+fibonacci(d+1)))/n)

z = PowerSeriesRing(ZZ, 'z').gen().O(30)
r = (1 - (z + z**2))
F = -z*r.derivative()/r
[sum(moebius(n//d)*F[d] for d in divisors(n))//n for n in range(1, 24)] # F. Chapoton, Apr 24 2020

Euler transform is Fibonacci(n+1): 1/((1 - x) * (1 - x^2) * (1 - x^3) * (1 - x^4) * (1 - x^5)^2 * (1 - x^6)^2 * ...) = 1/(Product_{n >= 1} (1 - x^n)^a(n)) = 1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 8*x^5 + ...
Coefficients of power series of natural logarithm of the infinite product Product_{n>=1} (1 - x^n - x^(2*n))^(-mu(n)/n), where mu(n) is the Moebius function. This is related to Fibonacci sequence since 1/(1 - x^n - x^(2*n)) expands to a power series whose terms are Fibonacci numbers.
a(n) = (1/n) * Sum_{d|n} mu(n/d) * (Fibonacci(d-1) + Fibonacci(d+1)) = (1/n) * Sum_{d|n} mu(n/d) * Lucas(d). Hence Lucas(n) = Sum_{d|n} d*a(d).
a(n) = round((1/n) * Sum_{d|n} mu(d)*phi^(n/d)), n > 2. - David Broadhurst [Formula corrected by Jason Yuen, Dec 29 2024]
G.f.: Sum_{n >= 1} -mu(n) * log(1 - x^n - x^(2*n))/n.
a(n) = (1/n) * Sum_{d|n} mu(d) * A001610(n/d - 1), n > 1. - R. J. Mathar, Mar 07 2009
For n > 2, a(n) = A060280(n) = A031367(n)/n.

A001350 Associated Mersenne numbers.

Original entry on oeis.org

0, 1, 1, 4, 5, 11, 16, 29, 45, 76, 121, 199, 320, 521, 841, 1364, 2205, 3571, 5776, 9349, 15125, 24476, 39601, 64079, 103680, 167761, 271441, 439204, 710645, 1149851, 1860496, 3010349, 4870845, 7881196, 12752041, 20633239, 33385280, 54018521, 87403801, 141422324

Offset: 0

N. J. A. Sloane, R. K. Guy

a(n) is last term in the period of the continued fraction expansion of phi^n (phi being the golden number). E.g.: n=10, phi^10=[122,1,121,1,121,1,121,...] (and the period may only have 1 or 2 terms). Also, a(n) = floor(phi^n)-((n+1) mod 2), or a(n) = A014217(n)-((n+1) mod 2). - Thomas Baruchel, Nov 05 2002 [continued fraction value corrected by Jon E. Schoenfield, Jan 20 2019]
a(n) is the resultant of the polynomials x^2-x-1 and x^(n+1)-x^n-1 for n >= 1. - Richard Choulet, Aug 05 2007
This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - Michael Somos, Feb 12 2012
Gives the number of arrangements of black and white beads on a necklace with a total of n beads satisfying (1) there is at least one black bead (2) between any two black beads the number of white beads is even and (3) rotations and flippings of a necklace are considered distinct (see Butler). - Peter Bala, Mar 06 2014
This is the case P1 = 1, P2 = 0, Q = -1 of the 3-parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014
The resultant of the (s_2, s_2+n) pair, where s_n(X) is X^n-X-1, is -a(n). See Rush link. - Michel Marcus, Sep 30 2019

			G.f. = x + x^2 + 4*x^3 + 5*x^4 + 11*x^5 + 16*x^6 + 29*x^7 + 45*x^8 + 76*x^9 + ...
n=1: a(9)/a(3) = 76/4 = 19; a(18)/a(6) = 5776/16 = 361 = 19^2. - _Bob Selcoe_, Jun 01 2014

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 0..1000
Gene Abrams and Gonzalo Aranda Pino, The Leavitt path algebras of generalized Cayley graphs, arXiv preprint arXiv:1310.4735 [math.RA], 2013.
Michael Baake, Joachim Hermisson, and Peter A. B. Pleasants, The torus parametrization of quasiperiodic LI-classes, J. Phys. A 30 (1997), no. 9, 3029-3056.
Michael Baake, John A. G. Roberts, and Alfred Weiss, Periodic orbits of linear endomorphism of the 2-torus and its lattices, arXiv:0808.3489 [math.DS] (2008).
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. 21.
Steve Butler, The art of juggling with two balls or a proof for a modular condition of Lucas numbers, arXiv:1004.4293v2 [math.CO], 2010.
James W. Cannon, William J. Floyd, LeeR Lambert, Walter R. Parry and Jessica S. Purcell, Bitwist manifolds and two-bridge knots, arXiv preprint arXiv:1306.4564 [math.GT], 2013-2015.
James W. Cannon, William J. Floyd, LeeR Lambert, Walter R. Parry and Jessica S. Purcell, Bitwist manifolds and two-bridge knots, Pacific Journal of Mathematics 284 (2016), 1-39.
N. Garnier and O. Ramare, Fibonacci numbers and trigonometric identities, Fibonacci Quart. 46/47 (2008/2009), no. 1, 56-61.
R. K. Guy, Letters to N. J. A. Sloane, June-August 1968
Petros Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
C. B. Haselgrove, Associated Mersenne numbers, Eureka, 11 (1949), 19-22.
C. B. Haselgrove, Associated Mersenne numbers [Annotated and scanned copy]
G. I. Lehrer and G. B. Segal, Homology stability for classical regular semisimple varieties, Math. Zeit., 236 (2001), 251-290; see Thm. 7.12.
B. Myers, Number of spanning trees in a wheel, IEE Trans. Circuit Theo. 18 (2) (1971) 280-282, Table 1.
Natascha Neumärker, Realizability of Integer Sequences as Differences of Fixed Point Count Sequences, Journal of Integer Sequences, 12 (2009), Article 09.4.5, Example 10.
Aleksandar Petojević, Marjana Gorjanac Ranitović, Dragan Rastovac, and Milinko Mandić, The Golden Ratio, Factorials, and the Lambert W Function, J. Int. Seq. (2024) Art. 24.5.7. See p. 2.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
David E. Rush, Degree n Relatives of the Golden Ratio and Resultants of the Corresponding Polynomials, Fib. Q. 50(4), 2012, 313-325. See p. 317.
Jianxin Wei and Yujun Yang, Associated Mersenne graphs, arXiv:2407.08237 [math.CO], 2024. See p. 4.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1).

Cf. A031367, A098554, A000032, A004146, A129744.

[Floor(-(1 - ((1 + Sqrt(5))/2)^n - (-(1 + Sqrt(5))/2)^(-n) + (-1)^n)): n in [0..40]]; // Vincenzo Librandi, Aug 15 2011

A001350 := n -> add(binomial(k-1, 2*k-n)*n/(n-k), k=0..n-1);
seq(A001350(n), n=0..39); # Peter Luschny, Sep 26 2014

Clear[f, n]; f[n_] = -(1 - ((1 + Sqrt[5])/2)^n - (-(1 + Sqrt[5])/2)^(-n) + (-1)^n); Table[FullSimplify[ExpandAll[f[n]]], {n, 0, 30}] (* Roger L. Bagula and Gary W. Adamson, Nov 26 2008 *)
a[ n_] := LucasL[n] - 1 - (-1)^n; (* Michael Somos, May 18 2015 *)
a[ n_] := SeriesCoefficient[ x D[ Log[ 1 + x / (1 - x - x^2)], x], {x, 0, n}]; (* Michael Somos, May 18 2015 *)
LinearRecurrence[{1, 2, -1, -1}, {0, 1, 1, 4}, 40] (* Jean-François Alcover, Jan 07 2019 *)

{a(n) = fibonacci(n+1) + fibonacci(n-1) - 1 - (-1)^n};

{a(n) = my(w = quadgen(5)); simplify( -(w^n - 1) * ((-1/w)^n - 1))}; /* Michael Somos, Feb 12 2012 */

from sympy import lucas
def A001350(n): return lucas(n)-((n&1^1)<<1) # Chai Wah Wu, Sep 23 2023

G.f.: x*(1+x^2)/((1-x^2)*(1-x-x^2)). -  Simon Plouffe in his 1992 dissertation
a(n) = a(n-1) + a(n-2) + 1 -(-1)^n. a(-n) = (-1)^n * a(n).
a(n) = A050140(Fibonacci(n)). - Thomas Baruchel, Nov 05 2002
Convolution of F(n) and {1, 0, 2, 0, 2, ...}. a(n) = Sum_{k=0..n} ((1+(-1)^k)-0^k)*F(n-k) = Sum_{k=0..n} F(k)*((1+(-1)^(n-k))-0^(n-k)). - Paul Barry, Jul 19 2004
a(n) = 2*A074331(n) - A000045(n). - Paul Barry, Jul 19 2004
a(n) = Lucas_number(n) - 1 - (-1)^n = A000032(n) - 1 - (-1)^n. - Hieronymus Fischer, Feb 18 2006
a(n) = -(1 - ((1 + sqrt(5))/2)^n - (-(1 + sqrt(5))/2)^(-n) + (-1)^n). - Roger L. Bagula and Gary W. Adamson, Nov 26 2008
a(n) = n * Sum_{k=1..n} (Sum_{i=ceiling((n-k)/2)..(n-k)} (binomial(i,n-k-i)*binomial(k+i-1,k-1))/k*(-1)^(k+1)), n>0. - Vladimir Kruchinin, Sep 03 2010
a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4). - Colin Barker, Apr 11 2014
a(n) = sqrt(A152152(n)). - Colin Barker, Apr 11 2014
a(n) = a(2*n)/A000032(n) when n is odd; a(n) = a(2*n)/(A000032(n+2)) when n is even. - Bob Selcoe, Jun 01 2014
a(12n+6)/a(4n+2) = (a(6n+3)/a(2n+1))^2. - Bob Selcoe, Jun 01 2014
a(n) = Sum_{k=0..n-1} binomial(k-1, 2*k-n)*n/(n-k). - Peter Luschny, Sep 26 2014
From Peter Bala, Mar 19 2015: (Start)
a(n) = -(alpha^n - 1)*(beta^n - 1), where alpha = 1/2*(1 + sqrt(5)) and beta = (1/2)*(1 - sqrt(5)).
a(n) = -det(I - M^n) where I is the 2 X 2 identity matrix and M = [ 1, 1; 1, 0 ]. Cf. A129744.
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + Sum_{n >= 1} Fibonacci(n)*x^n. Cf. A004146. (End)
a(n) = A052952(n-1) + A052952(n-3). - R. J. Mathar, Jul 02 2018
a(n) = (L(2*n+1) - L(n+1)) mod (L(n+1)-1) for n > 0 where L(k)=A000032(k). - Art Baker, Jan 17 2019
a(n) = Sum_{j=n..2*n-1} L(j) mod Sum_{j=0..n-1} L(j) where L(j)=A000032(j). - Art Baker, Jan 20 2019
Convolution of (1, 0, 3, 0, 5, 0, 7, ...) and (1, 1, 1, 2, 3, 5, 8, 13, ...). - Gary W. Adamson, Jul 08 2019
a(n) = Sum_{d|n} d*A060280(d) = Sum_{d|n} A031367(d). [Baake, Roberts, Weiss, eq(2)]. - R. J. Mathar, Oct 19 2021

Additional comments from Michael Somos, Aug 01 2002

A060280 Number of orbits of length n under the map whose periodic points are counted by A001350.

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 4, 5, 8, 11, 18, 25, 40, 58, 90, 135, 210, 316, 492, 750, 1164, 1791, 2786, 4305, 6710, 10420, 16264, 25350, 39650, 61967, 97108, 152145, 238818, 374955, 589520, 927200, 1459960, 2299854, 3626200, 5720274, 9030450, 14263078, 22542396

Offset: 1

Thomas Ward, Mar 29 2001

Euler transform is A000045. 1/((1-x)*(1-x^3)*(1-x^4)*(1-x^5)^2*(1-x^6)^2*...) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 8*x^6 + ... - Michael Somos, Jan 28 2003

			a(7)=4 since the 7th term of A001350 is 29 and the 1st is 1, so there are (29-1)/7 = 4 orbits of length 7.
x + x^3 + x^4 + 2*x^5 + 2*x^6 + 4*x^7 + 5*x^8 + 8*x^9 + 11*x^10 + 18*x^11 + ...

Seiichi Manyama, Table of n, a(n) for n = 1..4000
Michael Baake, Joachim Hermisson, and Peter Pleasants, The torus parametrization of quasiperiodic LI-classes J. Phys. A 30 (1997), no. 9, 3029-3056.
Michael Baake, John A.G. Roberts, and Alfred Weiss, Periodic orbits of linear endomorphisms on the 2-torus and its lattices, arXiv:0808.3489 [math.DS], Aug 26, 2008. [_Jonathan Vos Post_, Aug 27 2008]
Larry Ericksen, Primality Testing and Prime Constellations, Šiauliai Mathematical Seminar, Vol. 3 (11), 2008. Mentions this sequence.
N. Neumarker, Realizability of Integer Sequences as Differences of Fixed Point Count Sequences, JIS 12 (2009) 09.4.5.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
T. Ward, Exactly realizable sequences

Cf. A000032, A000045, A001350, A006206, A324485, A324489.

First column of A348422.

A060280:= func< n | n le 2 select 2-n else (&+[Lucas(d)*MoebiusMu(Floor(n/d)) : d in Divisors(n)])/n >;
[A060280(n): n in [1..50]]; // G. C. Greubel, Nov 06 2024

A060280 := proc(n)
    add( numtheory[mobius](d)*A001350(n/d), d=numtheory[divisors](n)) ;
    %/n;
end proc: # R. J. Mathar, Jul 15 2016

A001350[n_] := LucasL[n] - (-1)^n - 1;
a[n_] := (1/n)*DivisorSum[n, MoebiusMu[#]*A001350[n/#]& ];
Array[a, 50] (* Jean-François Alcover, Nov 23 2017 *)

{a(n) = if( n<3, n==1, sumdiv( n, d, moebius(n/d) * (fibonacci(d - 1) + fibonacci(d + 1))) / n)} /* Michael Somos, Jan 28 2003 */

A000032=BinaryRecurrenceSequence(1,1,2,1)
def A060280(n): return sum(A000032(k)*moebius(n/k) for k in (1..n) if (k).divides(n))//n - int(n==2)
[A060280(n) for n in range(1,41)] # G. C. Greubel, Nov 06 2024

a(n) = (1/n)* Sum_{d|n} mu(d)*A001350(n/d).
a(n) = A006206(n) except for n=2. - Michael Somos, Jan 28 2003
a(n) = A031367(n)/n. - R. J. Mathar, Jul 15 2016
G.f.: Sum_{k>=1} mu(k)*log(1 + x^k/(1 - x^k - x^(2*k)))/k. - Ilya Gutkovskiy, May 18 2019

cp's OEIS Frontend

A006206 Number of aperiodic binary necklaces of length n with no subsequence 00, excluding the necklace "0".

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

A001350 Associated Mersenne numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A060280 Number of orbits of length n under the map whose periodic points are counted by A001350.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A324488 Inflation orbit counts b^{(3)}_n for Danzer's F-type tiling and other 3D cut and project patterns with tau-inflation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A250112 Number of symmetric primitive Lucas strings of length n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A250113 Number of asymmetric Lucas strings of length n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A324484 Inflation orbit counts b^{(2)}_n for 2D cut and project patterns with tau-inflation.

Views

Author

Keywords

Links

Crossrefs