A034738 -id:A034738 - cp's OEIS frontend

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.

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

A053635 a(n) = Sum_{d|n} phi(d)*2^(n/d).

Original entry on oeis.org

0, 2, 6, 12, 24, 40, 84, 140, 288, 540, 1080, 2068, 4224, 8216, 16548, 32880, 65856, 131104, 262836, 524324, 1049760, 2097480, 4196412, 8388652, 16782048, 33554600, 67117128, 134218836, 268452240, 536870968, 1073777040, 2147483708, 4295033472, 8589938808

Offset: 0

N. J. A. Sloane, Mar 23 2000

nonn

Dirichlet convolution of phi(n) and 2^n. - Richard L. Ollerton, May 06 2021

Seiichi Manyama, Table of n, a(n) for n = 0..3321
James East and Ron Niles, Integer polygons of given perimeter, arXiv:1710.11245 [math.CO], 2017.
James East and Ron Niles, Integer polygons of given perimeter, Bull. Aust. Math. Soc. 100(1) (2019), 131-147.
T. Pisanski, D. Schattschneider, and B. Servatius, Applying Burnside's lemma to a one-dimensional Escher problem, Math. Mag., 79 (2006), 167-180. See v(n).

Cf. A000031, A053634, A053636. Twice A034738.

Column k=2 of A185651.

[0] cat  [&+[EulerPhi(d)*2^(n div d): d in Divisors(n)]: n in [1..40]]; // Vincenzo Librandi, Jul 20 2019

with(numtheory); A053685:=n->add( phi(n/d)*2^d, d in divisors(n)); # N. J. A. Sloane, Nov 21 2009

a[0] = 0; a[n_] := Sum[EulerPhi[d] 2^(n/d), {d, Divisors[n]}];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Aug 30 2018 *)

a(n) = if (n, sumdiv(n, d, eulerphi(d)*2^(n/d)), 0); \\ Michel Marcus, Sep 20 2017

a(n) = n * A000031(n).
a(n) = Sum_{k=1..n} 2^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021
a(n) = Sum_{k=1..n} 2^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021

A034754 Dirichlet convolution of 3^(n-1) with phi(n).

Original entry on oeis.org

1, 4, 11, 32, 85, 260, 735, 2224, 6585, 19780, 59059, 177472, 531453, 1595076, 4783175, 14351168, 43046737, 129147252, 387420507, 1162281440, 3486785925, 10460412292, 31381059631, 94143360944, 282429536825, 847289140932

Offset: 1

Erich Friedman

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..2096

Cf. A000010, A001867, A034738, A054610.

Table[Sum[3^(n/d - 1)*EulerPhi[d], {d, Divisors[n]}], {n, 1, 30}] (* Vaclav Kotesovec, Sep 10 2019 *)

a(n) = sum(k=1, n, 3^(gcd(k, n)-1)); \\ Seiichi Manyama, Apr 17 2021

a(n) = sumdiv(n, d, eulerphi(n/d)*3^(d-1)); \\ Seiichi Manyama, Apr 17 2021

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k/(1-3*x^k))) \\ Seiichi Manyama, Apr 17 2021

a(n) ~ 3^(n-1). - Vaclav Kotesovec, Sep 11 2019
G.f.: Sum_{k>=1} phi(k) * x^k / (1 - 3*x^k). - Ilya Gutkovskiy, Feb 14 2020
a(n) = Sum_{k=1..n} 3^(gcd(k, n) - 1) = A054610(n)/3. - Seiichi Manyama, Apr 17 2021
a(n) = Sum_{k=1..n} 3^(n/gcd(n,k) - 1)*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021

A349565 Dirichlet convolution of Fibonacci numbers with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Original entry on oeis.org

1, -1, -2, -3, -11, -16, -51, -93, -214, -419, -935, -1812, -3863, -7649, -15698, -31443, -63939, -127676, -257963, -516037, -1037298, -2076547, -4165647, -8335716, -16702015, -33421217, -66911078, -133875827, -267921227, -535987784, -1072395555, -2145208557, -4291436930, -8584038291, -17170640199, -34344407256

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution of this sequence with A034738 produces A034748.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A000045, A011782, A349452, A349566 (Dirichlet inverse).

Cf. also A034738, A034748, A349563, A349567, A349569.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * 2^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, Fibonacci[#] * s[n/#] &]; Array[a, 36] (* Amiram Eldar, Nov 22 2021 *)

A011782(n) = (2^(n-1));
memoA349452 = Map();
A349452(n) = if(1==n,1,my(v); if(mapisdefined(memoA349452,n,&v), v, v = -sumdiv(n,d,if(dA011782(n/d)*A349452(d),0)); mapput(memoA349452,n,v); (v)));
A349565(n) = sumdiv(n,d,fibonacci(d)*A349452(n/d));

a(n) = Sum_{d|n} A000045(d) * A349452(n/d).

A349566 Dirichlet convolution of A011782 (2^(n-1)) with A349451 (Dirichlet inverse of Fibonacci numbers).

Original entry on oeis.org

1, 1, 2, 4, 11, 20, 51, 100, 218, 441, 935, 1862, 3863, 7751, 15742, 31648, 63939, 128180, 257963, 516974, 1037502, 2078417, 4165647, 8339900, 16702136, 33428943, 66911942, 133891584, 267921227, 536021340, 1072395555, 2145272320, 4291440670, 8584166169, 17170641321, 34344672290, 68695318919, 137399603159, 274814652766

Offset: 1

Antti Karttunen, Nov 22 2021

nonn

Dirichlet convolution of this sequence with A034748 produces A034738.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A000045, A011782, A349451, A349565 (Dirichlet inverse).

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * Fibonacci[n/#] &, # < n &]; a[n_] := DivisorSum[n, 2^(# - 1) * s[n/#] &]; Array[a, 40] (* Amiram Eldar, Nov 22 2021 *)

memoA349451 = Map();
A349451(n) = if(1==n,1,my(v); if(mapisdefined(memoA349451,n,&v), v, v = -sumdiv(n,d,if(dA349451(d),0)); mapput(memoA349451,n,v); (v)));
A349566(n) = sumdiv(n,d,(2^(d-1)) * A349451(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A349451(n/d).

A349567 Dirichlet convolution of A133494 [3^(n-1)] with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Original entry on oeis.org

1, 1, 5, 17, 65, 197, 665, 2017, 6285, 19025, 58025, 174565, 527345, 1584737, 4766245, 14311841, 42981185, 128995317, 387158345, 1161697825, 3485732845, 10458138977, 31376865305, 94134428213, 282412758225, 847253996225, 2541798693045, 7625460083185, 22876524019505, 68629830861205, 205890058352825, 617671220125537

Offset: 1

Antti Karttunen, Nov 22 2021

nonn

Dirichlet convolution of this sequence with A034738 produces A034754.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A133494, A349452, A349568 (Dirichlet inverse).

Cf. also A034738, A034754, A349563, A349565, A349569.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * 2^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, 3^(# - 1) * s[n/#] &]; Array[a, 32] (* Amiram Eldar, Nov 22 2021 *)

A011782(n) = (2^(n-1));
memoA349452 = Map();
A349452(n) = if(1==n,1,my(v); if(mapisdefined(memoA349452,n,&v), v, v = -sumdiv(n,d,if(dA011782(n/d)*A349452(d),0)); mapput(memoA349452,n,v); (v)));
A349567(n) = sumdiv(n,d,(3^(d-1)) * A349452(n/d));

a(n) = Sum_{d|n} 3^(d-1) * A349452(n/d).

A349569 Dirichlet convolution of A000027 (identity function) with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Original entry on oeis.org

1, 0, -1, -4, -11, -24, -57, -112, -243, -480, -1013, -1964, -4083, -8064, -16309, -32496, -65519, -130440, -262125, -523156, -1048263, -2095104, -4194281, -8383760, -16777015, -33546240, -67107609, -134200860, -268435427, -536835096, -1073741793, -2147417216, -4294962187, -8589803520, -17179867533, -34359463812

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution with A034729 gives sigma, A000203, and convolution with A034738 gives A018804.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A000027, A011782, A349452, A349570 (Dirichlet inverse).

Cf. also A000203, A018804, A034729, A034738, A349563, A349565, A349567.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#]*2^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, # * s[n/#] &]; Array[a, 36] (* Amiram Eldar, Nov 22 2021 *)

A011782(n) = (2^(n-1));
memoA349452 = Map();
A349452(n) = if(1==n,1,my(v); if(mapisdefined(memoA349452,n,&v), v, v = -sumdiv(n,d,if(dA011782(n/d)*A349452(d),0)); mapput(memoA349452,n,v); (v)));
A349569(n) = sumdiv(n,d,d * A349452(n/d));

a(n) = Sum_{d|n} d * A349452(n/d).

A065567 T(n,m) is the sum over all m-subsets of {1,...,n} of the gcd of the subset.

Original entry on oeis.org

1, 3, 1, 6, 3, 1, 10, 7, 4, 1, 15, 11, 10, 5, 1, 21, 20, 21, 15, 6, 1, 28, 26, 36, 35, 21, 7, 1, 36, 38, 60, 71, 56, 28, 8, 1, 45, 50, 90, 127, 126, 84, 36, 9, 1, 55, 67, 132, 215, 253, 210, 120, 45, 10, 1, 66, 77, 177, 335, 463, 462, 330, 165, 55, 11, 1, 78, 105, 250, 512, 798, 925, 792, 495, 220, 66, 12, 1

Offset: 1

Wouter Meeussen, Nov 30 2001

First differences of row sums equals A034738.

			Triangle begins:
   1;
   3,  1;
   6,  3,  1;
  10,  7,  4, 1;
  15, 11, 10, 5, 1;
  ...
T(4,2) = 7 = gcd(1,2) + gcd(1,3) + gcd(1,4) + gcd(2,3) + gcd(2,4) + gcd(3,4).

Alois P. Heinz, Rows n = 1..200 (first 31 rows from Sean A. Irvine)

Row sums give A065568.
T(2n,n) gives A244174 for n>=1.
T(2n,n+1) gives A001791 for n>=1.
T(2n+1,n+1) gives A001700 for n>=0.
Cf. A002088, A034738.

with(combstruct):
a065567_row := proc(n) local k,L,l,R,comb;
R := NULL;
for k from 1 to n do
   L := 0;
   comb := iterstructs(Combination(n),size=k):
   while not finished(comb) do
      l := nextstruct(comb);
      L := L + igcd(op(l));
   od;
   R := R,L;
od;
R end: # Peter Luschny, Dec 07 2010
# second Maple program:
b:= proc(n, g, t) option remember; `if`(n=0, g*x^t,
      b(n-1, igcd(g, n), t+1)+b(n-1, g, t))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0$2)):
seq(T(n), n=1..12);  # Alois P. Heinz, Sep 05 2023

Table[Plus@@(GCD@@@KSubsets[Range[n], m]), {n, 16}, {m, n}]

Sum_{k=1..n} (-1)^(k+1) * T(n,k) = A002088(n). - Alois P. Heinz, Sep 05 2023

A349568 Dirichlet convolution of A011782 [2^(n-1)] with A349453 (Dirichlet inverse of A133494, 3^(n-1)).

Original entry on oeis.org

1, -1, -5, -16, -65, -187, -665, -1984, -6260, -18895, -58025, -174016, -527345, -1583407, -4765595, -14307568, -42981185, -128980852, -387158345, -1161657760, -3485726195, -10458022927, -31376865305, -94134053296, -282412754000, -847252941535, -2541798630320, -7625456893096, -22876524019505, -68629821114805

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution of this sequence with A034754 produces A034738.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A133494, A349453, A349567 (Dirichlet inverse).

Cf. also A034738, A034754, A349564, A349566, A349570.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * 3^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, 2^(# - 1) * s[n/#] &]; Array[a, 30] (* Amiram Eldar, Nov 22 2021 *)

A133494(n) = max(1, 3^(n-1));
memoA349453 = Map();
A349453(n) = if(1==n,1,my(v); if(mapisdefined(memoA349453,n,&v), v, v = -sumdiv(n,d,if(dA133494(n/d)*A349453(d),0)); mapput(memoA349453,n,v); (v)));
A349568(n) = sumdiv(n,d,(2^(d-1)) * A349453(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A349453(n/d).

cp's OEIS Frontend

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

A053635 a(n) = Sum_{d|n} phi(d)*2^(n/d).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A034754 Dirichlet convolution of 3^(n-1) with phi(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A349565 Dirichlet convolution of Fibonacci numbers with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349566 Dirichlet convolution of A011782 (2^(n-1)) with A349451 (Dirichlet inverse of Fibonacci numbers).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349567 Dirichlet convolution of A133494 [3^(n-1)] with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349569 Dirichlet convolution of A000027 (identity function) with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Views

Author

Keywords

Comments