A038199 -id:A038199 - cp's OEIS frontend

A317475 Numbers k such that k^2 | A038199(k).

1, 16, 32, 64, 112, 128, 256, 395, 448, 512, 1024, 1093, 1168, 1368, 1472, 1792, 2013, 2048, 3279, 3344, 3511, 3968, 4096, 5472, 5696, 7168, 7651, 8192, 10533, 14209, 16384, 17488, 19674, 21672, 21888, 22953, 27552, 28672, 31599, 32768, 33883, 34905, 34976

Offset: 1

Amiram Eldar, Jul 29 2018

nonn

Serret proved in 1855 a generalization of Fermat's little theorem: for b >= 1, Sum_{d|k} mu(d)*b^(k/d) == 0 (mod k). This sequence includes numbers k such that k^2 divides the sum with base b=2.
Includes all the powers of 2 above 8.
An alternative generalization of Wieferich primes (A001220) which are the prime terms of this sequence.
Also numbers k such that k | A059966(k).

			16 is in the sequence since Sum_{d|16} mu(d)*2^(16/d) = 65280 = 255 * 16^2.

Wacław Sierpiński, Elementary Theory of Numbers, Elsevier, North Holland, 1988, page 217.

Amiram Eldar, Table of n, a(n) for n = 1..250
Joseph-Alfred Serret, Théorème de Fermat généralisé, Nouvelles Annales de Mathématiques, Vol. 14 (1855), pp. 261-262.

Cf. A000079, A001220, A038199, A059966, A077816, A182297.

f[n_] := DivisorSum[n, MoebiusMu[#] * 2^(n/#) &]; Select[Range[1000], Divisible[f[#], #^2] &]

isok(n) = frac(sumdiv(n, d, moebius(n/d)*(2^d-1))/n^2) == 0; \\ Michel Marcus, Jul 30 2018

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Original entry on oeis.org

1, 1, 3, 6, 15, 27, 63, 120, 252, 495, 1023, 2010, 4095, 8127, 16365, 32640, 65535, 130788, 262143, 523770, 1048509, 2096127, 4194303, 8386440, 16777200, 33550335, 67108608, 134209530, 268435455, 536854005, 1073741823, 2147450880

Offset: 1

N. J. A. Sloane

Also number of compositions of n into relatively prime parts (that is, the gcd of all the parts is 1). Also number of subsets of {1,2,..,n} containing n and consisting of relatively prime numbers. - Vladeta Jovovic, Aug 13 2003
Also number of perfect parity patterns that have exactly n columns (see A118141). - Don Knuth, May 11 2006
a(n) is odd if and only if n is squarefree (Tim Keller). - Emeric Deutsch, Apr 27 2007
a(n) is a multiple of 3 for all n>=3 (see Problem 11161 link). - Emeric Deutsch, Aug 13 2008
Row sums of triangle A143424. - Gary W. Adamson, Aug 14 2008
a(n) is the number of monic irreducible polynomials with nonzero constant coefficient in GF(2)[x] of degree n. - Michel Marcus, Oct 30 2016
a(n) is the number of aperiodic compositions of n, the number of compositions of n with relatively prime parts, and the number of compositions of n with relatively prime run-lengths. - Gus Wiseman, Dec 21 2017

			For n=4, there are 6 compositions of n into coprime parts: <3,1>, <2,1,1>, <1,3>, <1,2,1>, <1,1,2>, and <1,1,1,1>.
From _Gus Wiseman_, Dec 19 2017: (Start)
The a(6) = 27 aperiodic compositions are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1221), (1311), (2112), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
The a(6) = 27 compositions into relatively prime parts are:
  (111111),
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1122), (1131), (1212), (1221), (1311), (2112), (2121), (2211), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (51).
The a(6) = 27 compositions with relatively prime run-lengths are:
  (11112), (11121), (11211), (12111), (21111),
  (1113), (1131), (1212), (1221), (1311), (2112), (2121), (3111),
  (114), (123), (132), (141), (213), (231), (312), (321), (411),
  (15), (24), (42), (51),
  (6).
(End)

H. O. Peitgen and P. H. Richter, The Beauty of Fractals, Springer-Verlag; contribution by A. Douady, p. 165.
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).

Seiichi Manyama, Table of n, a(n) for n = 1..3322 (terms 1..300 from T. D. Noe)
Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2.
Donald Knuth, Robin Chapman and Reiner Martin, Problem 11243, Perfect Parity Patterns, Am. Math. Monthly 115 (7) (2008) p 668, function c(n).
Emeric Deutsch and Lafayette College Problem Group, Problem 11161: Compositions without Common Factors, American Mathematical Monthly, vol. 114, No. 4, 2007, p. 363.
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
J. E. Iglesias, A formula for the number of closest packings of equal spheres having a given repeat period, Z. Krist. 155 (1981) 121-127, Table 2.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
Nicolae Mihalache and Francois Vigneron, Factorization of the quadratic Misiurewicz-Thurston polynomials, arXiv:2506.17662 [math.DS], 2025. See p. 8.
Robert Munafo, Enumeration of Period-N Mu-Atoms
Jeffrey Shallit and N. J. A. Sloane, Correspondence 1974-1975
François Vigneron and Nicolae Mihalache, How to split a tera-polynomial, arXiv:2402.06083 [math.NA], 2024.
Index entries for sequences related to Lyndon words

Cf. A000837, A003239, A008683, A008965, A022553, A034738, A035928, A038199, A051168, A054525, A056267, A059966, A143424, A167606, A178472, A216954, A228369, A294859, A296302.
Equals A027375/2.
See A056278 for a variant.
First differences of A085945.
Column k=2 of A143325.
Row sums of A101391.

with(numtheory): a[1]:=1: a[2]:=1: for n from 3 to 32 do div:=divisors(n): a[n]:=2^(n-1)-sum(a[n/div[j]],j=2..tau(n)) od: seq(a[n],n=1..32); # Emeric Deutsch, Apr 27 2007
with(numtheory); A000740:=n-> add(mobius(n/d)*2^(d-1), d in divisors(n)); # N. J. A. Sloane, Oct 18 2012

a[n_] := Sum[ MoebiusMu[n/d]*2^(d - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 32}] (* Jean-François Alcover, Feb 03 2012, after PARI *)

a(n) = sumdiv(n,d,moebius(n/d)*2^(d-1))

from sympy import mobius, divisors
def a(n): return sum([mobius(n // d) * 2**(d - 1) for d in divisors(n)])
[a(n) for n in range(1, 101)]  # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(n/d)*2^(d-1), Mobius transform of A011782. Furthermore, Sum_{d|n} a(d) = 2^(n-1).
a(n) = A027375(n)/2 = A038199(n)/2.
a(n) = Sum_{k=0..n} A051168(n,k)*k. - Max Alekseyev, Apr 09 2013
Recurrence relation: a(n) = 2^(n-1) - Sum_{d|n,d>1} a(n/d). (Lafayette College Problem Group; see the Maple program and Iglesias eq (6)). - Emeric Deutsch, Apr 27 2007
G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Oct 24 2018
G.f. satisfies Sum_{n>=1} A( (x/(1 + 2*x))^n ) = x. - Paul D. Hanna, Apr 02 2025

Connection with Mandelbrot set discovered by Warren D. Smith and proved by Robert Munafo, Feb 06 2000

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.

Original entry on oeis.org

0, 2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730, 65280, 131070, 261576, 524286, 1047540, 2097018, 4192254, 8388606, 16772880, 33554400, 67100670, 134217216, 268419060, 536870910, 1073708010, 2147483646, 4294901760

Offset: 0

N. J. A. Sloane

A sequence S is aperiodic if it is not of the form S = T^k with k>1. - N. J. A. Sloane, Oct 26 2012
Equivalently, number of output sequences with primitive period n from a simple cycling shift register. - Frank Ruskey, Jan 17 2000
Also, the number of nonempty subsets A of the set of the integers 1 to n such that gcd(A) is relatively prime to n (for n>1). - R. J. Mathar, Aug 13 2006; range corrected by Geoffrey Critzer, Dec 07 2014
Without the first term, this sequence is the Moebius transform of 2^n (n>0). For n > 0, a(n) is also the number of periodic points of period n of the transform associated to the Kolakoski sequence A000002. This transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the 2 periodic points of period 2. A001037(n) = a(n)/n gives the number of orbits of size n. - Jean-Christophe Hervé, Oct 25 2014
From Bernard Schott, Jun 19 2019: (Start)
There are 2^n strings of length n that can be formed from the symbols 0 and 1; in the example below with a(3) = 6, the last two strings that are not aperiodic binary strings are { 000, 111 }, corresponding to 0^3 and 1^3, using the notation of the first comment.
Two properties mentioned by Krusemeyer et al. are:
1) For any n > 2, a(n) is divisible by 6.
2) Lim_{n->oo} a(n+1)/a(n) = 2. (End)

			a(3) = 6 = |{ 001, 010, 011, 100, 101, 110 }|. - corrected by _Geoffrey Critzer_, Dec 07 2014

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 13. - From N. J. A. Sloane, Oct 26 2012
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
Blanchet-Sadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 978-1-4200-6092-8; 1-4200-6092-9 MR2384993 (2009f:68142). See p. 164.
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967.
Mark I. Krusemeyer, George T. Gilbert, Loren C. Larson, A Mathematical Orchard, Problems and Solutions, MAA, 2012, Problem 128, pp. 225-227.

T. D. Noe, Table of n, a(n) for n = 0..300
J.-P. Allouche, Note on the transcendence of a generating function. In A. Laurincikas and E. Manstavicius, editors, Proceedings of the Palanga Conference for the 75th birthday of Prof. Kubilius, New trends in Probab. and Statist., Vol. 4, pages 461-465, 1997.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], Dec 25 2012.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
John D. Cook, Counting primitive bit strings (2014).
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 85.
Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit and Taylor J. Smith, Periodicity in rectangular arrays, arXiv:1602.06915 [cs.DM], 2016; Information Processing Letters 118 (2017) 58-63. See Table 1.
O. Georgiou, C. P. Dettmann and E. G. Altmann, Faster than expected escape for a class of fully chaotic maps, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From _N. J. A. Sloane_, Dec 23 2012
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
David W. Lyons, Cristina Mullican, Adam Rilatt, and Jack D. Putnam, Werner states from diagrams, arXiv:2302.05572 [quant-ph], 2023.
Robert M. May, Simple mathematical models with very complicated dynamics, Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - _N. J. A. Sloane_, Mar 17 2019
M. B. Nathanson, Primitive sets and Euler phi function for subsets of {1,2,...,n}, arXiv:math/0608150 [math.NT], 2006-2007.
P. Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, arXiv:1306.4891 [math.NT], 2013 and J. Int. Seq. 16 (2013) #13.9.1.
P. Pongsriiam, A remark on relative prime sets, arXiv:1306.2529 [math.NT], 2013.
P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.
R. C. Read, Combinatorial problems in the theory of music, Disc. Math. 167/168 (1997) 543-551, sequence A(n).
M. Tang, Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ... , n}, J. Int. Seq. 13 (2010) # 10.7.6.
László Tóth, Menon-type identities concerning subsets of the set {1,2,...,n}, arXiv:2109.06541 [math.NT], 2021.

A038199 and A056267 are essentially the same sequence with different initial terms.
Cf. A020921, A216953.
Column k=2 of A143324.

a027375 n = n * a001037 n  -- Reinhard Zumkeller, Feb 01 2013

with(numtheory): A027375 :=n->add( mobius(d)*2^(n/d), d = divisors(n)); # N. J. A. Sloane, Sep 25 2012

Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ], {n, 1, 32} ]
a[0]=0; a[n_] := DivisorSum[n, MoebiusMu[n/#]*2^#&]; Array[a, 40, 0] (* Jean-François Alcover, Dec 01 2015 *)

PARI
```
a(n) = sumdiv(n,d,moebius(n\d)*2^d);
```

from sympy import mobius, divisors
def a(n): return sum(mobius(d)*2**(n//d) for d in divisors(n))
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(d)*2^(n/d).
a(n) = 2*A000740(n).
a(n) = n*A001037(n).
Sum_{d|n} a(n) = 2^n.
a(p) = 2^p - 2 for p prime. - R. J. Mathar, Aug 13 2006
a(n) = 2^n - O(2^(n/2)). - Charles R Greathouse IV, Apr 28 2016
a(n) = 2^n - A152061(n). - Bernard Schott, Jun 20 2019
G.f.: 2 * Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Nov 11 2019

A056267 Number of primitive (aperiodic) words of length n which contain exactly two different symbols.

Original entry on oeis.org

0, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730, 65280, 131070, 261576, 524286, 1047540, 2097018, 4192254, 8388606, 16772880, 33554400, 67100670, 134217216, 268419060, 536870910, 1073708010, 2147483646

Offset: 1

Marks R. Nester

nonn

M. R. Nester, Mathematical investigations of some plant interaction designs, PhD Thesis, University of Queensland, Brisbane, Australia, 1999 [See A056391 for pdf file of Chap. 2].

Cf. A000079, A000918.

A027375 and A038199 are essentially the same sequence with different initial terms.

a(n) = sumdiv(n, d, moebius(d)*(2^(n/d) - 2)); \\ Michel Marcus, Jun 30 2019

a(n) = Sum_{d|n} mu(d)*A000918(n/d), n>0.

Corrected and extended by Franklin T. Adams-Watters and T. D. Noe, Oct 25 2006

A130887 Inverse Moebius transform of the Mersenne numbers: a(n) = Sum_{d|n} (2^d - 1).

Original entry on oeis.org

1, 4, 8, 19, 32, 74, 128, 274, 519, 1058, 2048, 4184, 8192, 16514, 32806, 65809, 131072, 262728, 524288, 1049648, 2097286, 4196354, 8388608, 16781654, 33554463, 67117058, 134218246, 268451984, 536870912, 1073775718, 2147483648, 4295033104, 8589936646

Offset: 1

Gary W. Adamson, Jun 07 2007

nonn

			G.f. = x + 4*x^2 + 8*x^3 + 19*x^4 + 32*x^5 + 74*x^6 + 128*x^7 + 274*x^8 + ...

Enrique Pérez Herrero, Table of n, a(n) for n = 1..500

Cf. A001047.

Cf. A027750, A000225, A038199.

a130887 = sum . map a000225 . a027750_row
-- Reinhard Zumkeller, Feb 17 2013

A130887[n_]:=DivisorSum[n,Plus@@Table[Binomial[#,i],{i,1,#}]&]; Array[A130887,20] (* Enrique Pérez Herrero, Apr 14 2012 *)
a[ n_] := If[ n < 1, 0, DivisorSum[ n, 2^# - 1 &]]; (* Michael Somos, Jan 28 2017 *)

{a(n) = if( n<1, 0, sumdiv(n, d, 2^d-1))}; /* Michael Somos, Jan 28 2017 */

a(n) = Sum_{d|n} Sum_{k=1..d} C(d,k) = Sum_{d|n} (-1 + 2^d) = Sum_{d|n} 2^d - tau(n) = A055895(n) - A000010(n). - Enrique Pérez Herrero, Apr 14 2012
G.f.: Sum_{k>=1} (2^k - 1)*x^k/(1 - x^k). - Ilya Gutkovskiy, Jan 28 2017
a(n) = Sum_{i=1..n} 2^(i-1)*A135539(n,i). - Ridouane Oudra, Sep 19 2022

New name from Enrique Pérez Herrero, Apr 14 2012

Name corrected by Michel Marcus, Sep 19 2022

A023995 Number of sets S = {a_1, a_2, ..., a_k}, with 1 < a_i < a_j <= n such that no a_j divides the product of all the others.

Original entry on oeis.org

1, 2, 4, 6, 12, 16, 32, 44, 64, 86, 172, 204, 408, 544, 660, 860, 1720, 2080, 4160, 4800, 5792, 7784, 15568, 17440, 23648, 31616, 40976, 46584, 93168, 102768, 205536, 261600, 316160, 426304, 479616, 524112, 1048224, 1407856, 1699568, 1848384, 3696768, 4049376, 8098752, 9292544

Offset: 1

Lionel Levine (levine(AT)ultranet.com)

nonn

			f(4)=6: {}, {2}, {3}, {4}, {2,3}, {3,4}.

Sean A. Irvine, Java program (github)

Cf. A038199.

More terms from Sean A. Irvine, Jun 17 2019

A032253 "DHK" (bracelet, identity, unlabeled) transform of 3,3,3,3,...

Original entry on oeis.org

1, 3, 6, 13, 27, 78, 278, 1011, 3753, 13843, 50934, 187629, 692891, 2568882, 9562074, 35742329, 134117829, 505093740, 1908474674, 7232842785, 27486193251, 104712247296, 399816026490, 1529742725403, 5864036504705, 22517947805343, 86607583200294, 333599771067256

Offset: 0

Christian G. Bower

nonn

From Petros Hadjicostas, Jun 17 2019: (Start)
An unmarked cyclic composition of n >= 1 is an equivalence of ordered partitions of n such that two ordered partitions are equivalent iff one can be obtained from the other by rotation.
A dihedral composition of n >= 1 is an equivalence class of ordered partitions of n such that two such ordered partitions are equivalent iff one can be obtained from the other by rotation or reflection. See, for example, Knopfmacher and Robbins (2013).
A cyclic composition (ordered partition) of n >= 1 is called achiral iff it has a reflection symmetry, and it is called chiral otherwise. (This terminology comes from Chemistry in the study of molecules.)
A symmetric (achiral) cyclic composition of n >= 1 is also a symmetric (achiral) dihedral composition of n > = 1 (and vice versa).
Many mathematicians consider a cyclic composition of n >= 1 with one part or with two parts as achiral by default because the axis of symmetry may pass through the parts. When he defines the DHK transform, Bowers (in the link below) does not accept this convention except possibly for a cyclic composition with two identical (in value and color) parts.
Given n >= 1, a(n) here is the number of aperiodic chiral dihedral compositions of n such that the parts may be colored by any one of three colors (say, A, B, C).
Notice that a(1) = 3 because 1_A, 1_B, 1_C are the three colored aperiodic dihedral compositions of n = 1 that (according to Bowers) are considered chiral (= with no reflection symmetry).
In addition, a(2) = 6 because 2_A, 2_B, 2_C, 1_A + 1_B, 1_B + 1_C, 1_C + 1_A are the six colored aperiodic dihedral compositions of n = 2 that (according to Bowers) are considered chiral (= with no reflection symmetry).
In general, for n >= 1, if one disagrees with Bower's conventions about colored aperiodic dihedral compositions with one or two parts, then a(n) - 3*A001651(n) = a(n) - 3 * floor((3*n - 1 )/2) is the actual number of aperiodic chiral dihedral compositions of n such that the parts may be colored by any one of three colors.
Let c = (c(n): n >= 1) be the input sequence and b = (b(n): n >= 1) be the output sequence under Bower's DHK transform; i.e., b = (DHK c). Let C(x) = Sum_{n >= 1} c(n)*x^n; i.e., C(x) is the g.f. of c. Then the g.f. of b is Sum_{n >= 1} b(n)*x^n = -(1/2) * Sum_{d >= 1} (mu(d)/d) * log(1 - C(x^d)) - (1/2) * Sum_{d >= 1} mu(d) * ((C(x^d) + 1)^2/(2 * (1 - C(x^(2*d))) - (1/2)) + C(x) + (1/2) * (C(x)^2 - C(x^2)). Here, c(n) = 3 for all n >= 1 and C(x) = 3*x/(1 - x).
The part of the g.f. that gives the extra aperiodic dihedral compositions due to Bower is C(x) + (1/2) * (C(x)^2 - C(x^2)) = 3*x*(1 + x + x^2)/((1 + x)*(1 - x)^2). This is the g.f. of (3*A001651(n): n >= 1).
Here, D(x) = (C(x) + 1)^2/(2*(1 - C(x^2))) - (1/2) = 3*x/((1 - 2*x)*(1 - x)) = 3*(x + 3*x^2 + 7*x^3 + 15*x^4 + ...) is the g.f. of (3*A000225(n): n >= 1) = (3*(2^n - 1): n >= 1), which counts the symmetric (= achiral) unmarked cyclic compositions of n where up to 3 colors can be used.
Thus, the sequence (3*A038199(n): n >= 1) = (3*Sum_{d|n} mu(d)*A000225(n/d): n >= 1) = (3*Sum_{d|n} mu(d)*(2^(n/d) - 1): n >= 1) counts the aperiodic symmetric (unmarked) cyclic compositions of n where up to three colors can be used (without Bower's conventions for compositions with one or two parts). This latter sequence has g.f. Sum_{d >= 1} mu(d)*D(x^d) = Sum_{d >= 1} mu(d) * ((C(x^d) + 1)^2/(2 * (1 - C(x^(2*d))) - (1/2)).
Finally, -Sum_{d >= 1} (mu(d)/d)*log(1 - C(x^d)), where C(x) = 3*x/(1 - x), is the g.f. of sequence (A185172(n): n >= 1), which counts the aperiodic (unmarked) cyclic compositions of n where up to three colors can be used. See Eqs. (94) and (95) in Novelli and Thibon (2008) or  Eqs. (99) and (100) in Novelli and Thibon (2010).
(End)

			From _Petros Hadjicostas_, Jun 17 2019: (Start)
For n = 3, the Bower's extra 3*A001651(3) = 12 aperiodic dihedral compositions of 3 (using three colors) with one or two parts are as follows: 3_A, 3_B, 3_C, 1_A + 2_A, 1_B + 2_B, 1_C + 2_C, 1_A + 2_B, 1_A + 2_C, 1_B + 2_A, 1_B + 2_C, 1_C + 2_A, 1_C + 2_B. Since a(3) - 3*A001651(3) = 13 - 12 = 1, we have only one aperiodic chiral dihedral composition of 3 (with more than two parts): 1_A + 1_B + 1_C.
For n = 4, the Bower's extra 3*A001651(4) = 15 aperiodic dihedral compositions of n = 4 (using three colors) with one or two parts are as follows: 4_X, where X \in {A, B, C}; 2_X + 2_Y,  where (X,Y) \in {(A, B), (B, C), (C, A)}; and 1_X + 3_Y, where (X, Y) \in {(A, A), (A, B), (A, C), (B, A), (B, B), (B, C), (C, A), (C, B), (C, C)}.
The remaining (i.e., the genuine) a(4) - 15 = 27 - 15 = 12 aperiodic chiral dihedral compositions of n = 4 of 3 colors are as follows: 1_X + 2_X + 1_Y, where (X, Y) \in {(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)}; 1_X + 2_Y + 1_Z and 1_X + 1_X + 1_Y + 1_Z, where (X, Y, Z) \in \{(A, B, C), (B, C, A), (C, A, B)}.
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..500
C. G. Bower, Transforms (2)
Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, arXiv:0806.3682 [math.CO], 2008. See Eqs. (94) and (95).
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, Discrete Math. 310 (2010), no. 24, 3584-3606. See Eqs. (99) and (100).

Cf. A001651, A032102, A032239, A032240, A032241, A032242, A032244, A032245, A032251, A032252, A032254, A032256, A032257, A032258, A032259, A038199, A185172.

A001651[n_] := n - 1 + Ceiling[n/2];
A185172[n_] := If[n==1, 3, Sum[MoebiusMu[d] 4^(n/d), {d, Divisors[n]}]/n];
A038199[n_] := Sum[((2^d-1) MoebiusMu[n/d]), {d, Divisors[n]}];
a[n_] := Switch[n, 0, 1, 1, 3, _, 3 A001651[n] + (1/2)(A185172[n] - 3 * A038199[n])];
a /@ Range[0, 30] (* Jean-François Alcover, Sep 17 2019 *)

DHK(p,n)={my(q=((1+p)^2/(1-subst(p, x, x^2))-1)/2); p + (p^2-subst(p, x, x^2))/2 + sum(d=1, n, moebius(d)*(log(subst(1/(1+O(x*x^(n\d))-p), x, x^d))/d - subst(q + O(x*x^(n\d)), x, x^d)))/2}
seq(n)={Vec(1 + DHK(3*x/(1-x) + O(x*x^n), n))} \\ Andrew Howroyd, Sep 21 2018

From Petros Hadjicostas, Jun 18 2019: (Start)
a(n) = 3*A001651(n) + (1/2)*(A185172(n) - 3*A038199(n)) for n >= 1. Here, A001651(n) = floor((3*n - 1)/2) and A038199(n) = Sum_{d|n} mu(d)*(2^(n/d) - 1) for n >= 1. Also, A185172(1) = 3 and A185172(n) = (1/n)*Sum_{d|n} mu(d) * 4^(n/d) for n >= 2.
G.f.: 1 - (1/2)*Sum_{d >= 1} (mu(d)/d)*log(1 - 3*x^d/(1 - x^d)) - (1/2)*Sum_{d >= 1} mu(d)*3*x^d/((1 - 2*x^d)*(1 - x^d)) + 3*x*(1 + x + x^2)/((1 + x)*(1 - x)^2).
G.f.: 1 - x/2 - (1/2)*Sum_{d >= 1} (mu(d)/d)*log(1 - 4*x^d) - (1/2)*Sum_{d >= 1} mu(d)*3*x^d/((1 - 2*x^d)*(1 - x^d)) + 3*x*(1 + x + x^2)/((1 + x)*(1 - x)^2). (End)

a(0)=1 prepended and terms a(24) and beyond from Andrew Howroyd, Sep 21 2018

cp's OEIS Frontend

A317475 Numbers k such that k^2 | A038199(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A000740 Number of 2n-bead balanced binary necklaces of fundamental period 2n, equivalent to reversed complement; also Dirichlet convolution of b_n=2^(n-1) with mu(n); also number of components of Mandelbrot set corresponding to Julia sets with an attractive n-cycle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A056267 Number of primitive (aperiodic) words of length n which contain exactly two different symbols.

Views

Author

Keywords

References

Crossrefs

Programs

PARI

Formula

Extensions

A130887 Inverse Moebius transform of the Mersenne numbers: a(n) = Sum_{d|n} (2^d - 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A023995 Number of sets S = {a_1, a_2, ..., a_k}, with 1 < a_i < a_j <= n such that no a_j divides the product of all the others.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A032253 "DHK" (bracelet, identity, unlabeled) transform of 3,3,3,3,...

Views

Author

Keywords