A034754 -id:A034754 - cp's OEIS frontend

A034738 Dirichlet convolution of b_n = 2^(n-1) with phi(n).

1, 3, 6, 12, 20, 42, 70, 144, 270, 540, 1034, 2112, 4108, 8274, 16440, 32928, 65552, 131418, 262162, 524880, 1048740, 2098206, 4194326, 8391024, 16777300, 33558564, 67109418, 134226120, 268435484, 536888520, 1073741854, 2147516736

Offset: 1

Erich Friedman

nonn

Sum of GCD's of parts in all compositions of n. - Vladeta Jovovic, Aug 13 2003
From Petros Hadjicostas, Dec 07 2017: (Start)
It also equals the sum of all lengths of all cyclic compositions of n. This was proved in Perez (2008).
The bivariate g.f. for the number b(n,k) of all cyclic of compositions of n with k parts is Sum_{n,k>=1} b(n,k)*x^n*y^k = -Sum_{s>=1} (phi(s)/s)*log(1 - y^s*Sum_{t>=1} x^{s*t}) =  -Sum_{s>=1} (phi(s)/s)*log(1 - y^s*x^s/(1-x^s)). See, for example, Hadjicostas (2016). Differentiating w.r.t. y and setting y = 1, we get Sum_{n>=1} a(n)*x^n = Sum_{n>=1} (Sum_{k=1..n} b(n,k)*k)*x^n = Sum_{s>=1} phi(s)*x^s/(1-2*x^s).
(End)

			For the compositions of n=4 we have a(4) = gcd(4) + gcd(1,3) + gcd(3,1) + gcd(2,2) + gcd(2,1,1) + gcd(1,2,1) + gcd(1,1,2) + gcd(1,1,1,1) = 4 + 1 + 1 + 2 + 1 + 1 + 1 + 1 = 12. Also, for cyclic compositions of n=4, we have length(4) + length(1,3) + length(2,2) + length(1,1,2) + length(1,1,1,1) = 1 + 2 + 2 + 3 + 4 = 12.

Amiram Eldar, Table of n, a(n) for n = 1..3322
P. Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, J. Integer Sequences 19 (2016), Article 16.8.2.
R. A. Perez, Compositions versus cyclic compositions, JP Journal of Algebra, Number Theory and Applications, Vol. 12, Issue 1 (2008), pp. 41-48.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See pp. 47-48, 50.

Cf. A000010, A000740, A034754, A053635, A078392.

Table[Sum[EulerPhi[d]*2^(n/d-1), {d, Divisors[n]}], {n, 1, 40}] (* Vaclav Kotesovec, Feb 07 2019 *)

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

a(n) = sumdiv(n, d, eulerphi(n/d)*2^(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-2*x^k))) \\ Seiichi Manyama, Apr 17 2021

a(n) = A053635(n)/2.
a(n) = (1/2)* Sum_{d|n} phi(d)*2^(n/d), n >= 1.
G.f.: Sum_{s>=1} phi(s)*x^s/(1-2*x^s). - Petros Hadjicostas, Dec 07 2017
a(n) ~ 2^(n-1). - Vaclav Kotesovec, Feb 07 2019
a(n) = Sum_{k=1..n} 2^(gcd(k, n) - 1). - Seiichi Manyama, Apr 17 2021
a(n) = Sum_{k=1..n} 2^(n/gcd(n,k) - 1)*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 06 2021

A054610 a(n) = Sum_{d|n} phi(d)*3^(n/d).

Original entry on oeis.org

0, 3, 12, 33, 96, 255, 780, 2205, 6672, 19755, 59340, 177177, 532416, 1594359, 4785228, 14349525, 43053504, 129140211, 387441756, 1162261521, 3486844320, 10460357775, 31381236876, 94143178893, 282430082832, 847288610475

Offset: 0

N. J. A. Sloane, Apr 16 2000

nonn

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

Seiichi Manyama, Table of n, a(n) for n = 0..2095

Column k=3 of A185651.

Cf. A001867, A034754.

a(n) = sum(k=1, n, 3^gcd(n,k)); \\ Michel Marcus, Apr 16 2021

a(n) = n * A001867(n).
a(n) = 3*A034754(n). - R. J. Mathar, May 18 2014
a(n) = Sum_{k=1..n} 3^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021
a(n) = Sum_{k=1..n} 3^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021

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

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

A343489 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Sum_{j=1..n} k^(gcd(j, n) - 1).

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 3, 2, 0, 1, 4, 6, 4, 4, 0, 1, 5, 11, 12, 5, 2, 0, 1, 6, 18, 32, 20, 6, 6, 0, 1, 7, 27, 70, 85, 42, 7, 4, 0, 1, 8, 38, 132, 260, 260, 70, 8, 6, 0, 1, 9, 51, 224, 629, 1050, 735, 144, 9, 4, 0, 1, 10, 66, 352, 1300, 3162, 4102, 2224, 270, 10, 10

Offset: 0

Seiichi Manyama, Apr 17 2021

			Square array begins:
  0, 0,  0,   0,    0,    0,    0, ...
  1, 1,  1,   1,    1,    1,    1, ...
  1, 2,  3,   4,    5,    6,    7, ...
  2, 3,  6,  11,   18,   27,   38, ...
  2, 4, 12,  32,   70,  132,  224, ...
  4, 5, 20,  85,  260,  629, 1300, ...
  2, 6, 42, 260, 1050, 3162, 7826, ...

Columns k=0..5 give A000010, A001477, A034738, A034754, A343490, A343492.
Main diagonal gives A056665.
Cf. A185651, A319082.

T[n_, k_] := Sum[If[k == (g = GCD[j, n] - 1) == 0, 1, k^g], {j, 1, n}]; Table[T[k, n - k], {n, 0, 11}, {k, 0, n}] // Flatten (* Amiram Eldar, Apr 17 2021 *)

T(n, k) = sum(j=1, n, k^(gcd(j, n)-1));

T(n, k) = if(n==0, 0, sumdiv(n, d, eulerphi(n/d)*k^(d-1)));

G.f. of column k: Sum_{j>=1} phi(j) * x^j / (1 - k*x^j).
T(n,k) = A185651(n,k)/k for k > 0.
T(n,k) = Sum_{d|n} phi(n/d)*k^(d - 1).

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

Original entry on oeis.org

1, 2, 4, 8, 17, 44, 105, 278, 733, 1978, 5369, 14792, 40881, 113934, 318884, 896948, 2532161, 7174862, 20390553, 58114072, 166037460, 475473286, 1364393897, 3922640132, 11297181473, 32588043882, 94143179560, 272342824320, 788854912241, 2287679406940, 6641649422409

Offset: 1

Seiichi Manyama, Jul 13 2023

nonn

Cf. A000010, A034754, A195459, A327625.

Cf. A000013, A364211, A364212.

a[n_] := DivisorSum[n, 3^(n/#-1)*EulerPhi[3*#]/(2*n) &]; Array[a, 30] (* Amiram Eldar, Jul 14 2023 *)

a(n) = sumdiv(n, d, 3^(n/d-1)*eulerphi(3*d))/(2*n);

G.f.: (-1/2) * Sum_{k>0} phi(3*k) * log(1-3*x^k)/(3*k).

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

Original entry on oeis.org

1, -2, 11, -28, 85, -238, 735, -2216, 6585, -19610, 59059, -177428, 531453, -1593606, 4783175, -14351152, 43046737, -129134082, 387420507, -1162281100, 3486785925, -10460294174, 31381059631, -94143360856, 282429536825, -847288078026, 2541865841523, -7625599078020, 22876792454989

Offset: 1

Seiichi Manyama, Apr 12 2025

sign

Column k=3 of A382995.

Cf. A000010, A034754, A343465.

a(n) = sumdiv(n, d, eulerphi(n/d)*(-3)^(d-1));

a(n) = Sum_{k=1..n} (-3)^(gcd(n,k) - 1).

G.f.: Sum_{k>=1} phi(k) * x^k / (1 + 3*x^k).

cp's OEIS Frontend

A034738 Dirichlet convolution of b_n = 2^(n-1) with phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A054610 a(n) = Sum_{d|n} phi(d)*3^(n/d).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A343489 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Sum_{j=1..n} k^(gcd(j, n) - 1).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

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