%I #49 Jan 25 2024 17:03:04
%S 1,2,3,5,6,11,15,27,43,75,125,228,391,707,1262,2285,4119,7525,13691,
%T 25111,46033,84740,156123,288529,533670,989305,1835983,3412885,
%U 6351031,11834623,22074821,41222028,77048131,144148859,269913278,505826391,948652695,1780473001,3343960175,6284560319,11818395345
%N Number of binary necklaces of length n with no subsequence 0000.
%C a(n) is the number of cyclic sequences of length n consisting of zeros and ones that do not contain four consecutive zeros provided we consider as equivalent those sequences that are cyclic shifts of each other.
%H Alois P. Heinz, <a href="/A280218/b280218.txt">Table of n, a(n) for n = 1..3521</a>
%H P. Flajolet and M. Soria, <a href="http://algo.inria.fr/flajolet/Publications/cycle2.ps.gz">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H P. Flajolet and M. Soria, <a href="http://dx.doi.org/10.1137/0404006">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/cgi/viewcontent.cgi?article=3464&context=etd">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021. See p. 57.
%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%F a(n) = (1/n) * Sum_{d divides n} totient(n/d) * A073817(d).
%F G.f.: Sum_{k>=1} (phi(k)/k) * log(1/(1-B(x^k))) where B(x) = x*(1+x+x^2+x^3).
%e a(5)=6 because we have six binary cyclic sequences of length 5 that avoid four consecutive zeros: 00011, 00101, 00111, 01101, 01111, 11111.
%t Table[(1/n) Sum[EulerPhi[n/d] SeriesCoefficient[(4 - 3 x - 2 x^2 - x^3)/(1 - x - x^2 - x^3 - x^4), {x, 0, d}], {d, Divisors@ n}], {n, 41}] (* _Michael De Vlieger_, Dec 30 2016 *)
%o (PARI) N=44; x='x+O('x^N);
%o B(x)=x*(1+x+x^2+x^3);
%o Vec(sum(k=1, N, eulerphi(k)/k * log(1/(1-B(x^k))))) \\ _Joerg Arndt_, Dec 29 2016
%Y Row 4 of A322057.
%Y Cf. A000358, A073817, A093305, A280303.
%K nonn
%O 1,2
%A _Petros Hadjicostas_, Dec 29 2016