A054610 -id:A054610 - cp's OEIS frontend

A185651 A(n,k) = Sum_{d|n} phi(d)*k^(n/d); square array A(n,k), n>=0, k>=0, read by antidiagonals.

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 6, 3, 0, 0, 4, 12, 12, 4, 0, 0, 5, 20, 33, 24, 5, 0, 0, 6, 30, 72, 96, 40, 6, 0, 0, 7, 42, 135, 280, 255, 84, 7, 0, 0, 8, 56, 228, 660, 1040, 780, 140, 8, 0, 0, 9, 72, 357, 1344, 3145, 4200, 2205, 288, 9, 0

Offset: 0

Alois P. Heinz, Aug 29 2013

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

			Square array A(n,k) begins:
  0, 0,  0,   0,    0,     0,     0, ...
  0, 1,  2,   3,    4,     5,     6, ...
  0, 2,  6,  12,   20,    30,    42, ...
  0, 3, 12,  33,   72,   135,   228, ...
  0, 4, 24,  96,  280,   660,  1344, ...
  0, 5, 40, 255, 1040,  3145,  7800, ...
  0, 6, 84, 780, 4200, 15810, 46956, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=0..10 give A000004, A001477, A053635, A054610, A054611, A054612, A054613, A054614, A054615, A054616, A054617.
Rows n=0..10 give A000004, A001477, A002378, A054602, A054603, A054604, A054605, A054606, A054607, A054608, A054609.
Main diagonal gives A228640.
Cf. A000010, A075195, A258170.

with(numtheory):
A:= (n, k)-> add(phi(d)*k^(n/d), d=divisors(n)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

a[, 0] = a[0, ] = 0; a[n_, k_] := Sum[EulerPhi[d]*k^(n/d), {d, Divisors[n]}]; Table[a[n - k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 06 2013 *)

A(n,k) = Sum_{d|n} phi(d)*k^(n/d).
A(n,k) = Sum_{i=0..min(n,k)} C(k,i) * i! * A258170(n,i). - Alois P. Heinz, May 22 2015
G.f. for column k: Sum_{n>=1} phi(n)*k*x^n/(1-k*x^n) for k >= 0. - Petros Hadjicostas, Nov 06 2017
From Richard L. Ollerton, May 07 2021: (Start)
A(n,k) = Sum_{i=1..n} k^gcd(n,i).
A(n,k) = Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)).
A(n,k) = A075195(n,k)*n for n >= 1, k >= 1.  (End)

A001867 Number of n-bead necklaces with 3 colors.

Original entry on oeis.org

1, 3, 6, 11, 24, 51, 130, 315, 834, 2195, 5934, 16107, 44368, 122643, 341802, 956635, 2690844, 7596483, 21524542, 61171659, 174342216, 498112275, 1426419858, 4093181691, 11767920118, 33891544419, 97764131646, 282429537947, 817028472960, 2366564736723

Offset: 0

N. J. A. Sloane

From Richard L. Ollerton, May 07 2021: (Start)
Here, as in A000031, turning over is not allowed.
(1/n) * Dirichlet convolution of phi(n) and 3^n, n>0. (End)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 162.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(a).

T. D. Noe, Table of n, a(n) for n = 0..200
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See pp. 6, 20.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
V. E. Hoggatt, The Fifth Oldie from the Vault. Problem B-415, Elementary Problems and Solutions, Fibonacci Quart. 59 (2021), no. 3, pp. 274-275.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 3
Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, On cardinalities of k-abelian equivalence classes, arXiv preprint arXiv:1605.03319 [math.CO], 2016.
J. Riordan, Letter to N. J. A. Sloane, Jul. 1978
Index entries for sequences related to necklaces

Column 3 of A075195.

Cf. A054610.

with(numtheory): A001867:= n-> `if` (n=0, 1, add (phi(d)* 3^(n/d), d=divisors(n))/n): seq (A001867(n), n=0..40);
spec := [N, {N=Cycle(bead), bead=Union(R,G,B), R=Atom, B=Atom, G=Atom}]; [seq(combstruct[count](spec, size=n), n=1..40)];

Prepend[Table[CyclicGroupIndex[n,t]/.Table[t[i]->3,{i,1,n}],{n,1,28}],1]  (* Geoffrey Critzer, Sep 16 2011 *)
mx=40;CoefficientList[Series[1-Sum[EulerPhi[i] Log[1-3*x^i]/i,{i,1,mx}],{x,0,mx}],x] (* Herbert Kociemba, Nov 01 2016 *)
k=3; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/n, {n, 1, 30}], 1] (* Robert A. Russell, Sep 21 2018 *)

a(n)=if (n==0, 1, 1/n * sumdiv(n, d, eulerphi(d)*3^(n/d) )); /* Joerg Arndt, Jul 04 2011 */

a(n) = (1/n)*Sum_{d|n} phi(d)*3^(n/d), n>0.
G.f.: 1 - Sum_{n>=1} phi(n)*log(1 - 3*x^n)/n. - Herbert Kociemba, Nov 01 2016
a(n) ~ 3^n/n. - Vaclav Kotesovec, Nov 01 2016
a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} 3^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021
a(0) = 1; a(n) = (1/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

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

Original entry on oeis.org

1, 9, 29, 74, 129, 261, 349, 596, 789, 1161, 1341, 2146, 2209, 3141, 3741, 4776, 4929, 7101, 6877, 9546, 10121, 12069, 12189, 17284, 16145, 19881, 21321, 25826, 24417, 33669, 29821, 38224, 38889, 44361, 45021, 58386, 50689, 61893, 64061, 76884, 68961, 91089, 79549, 99234, 101781

Offset: 1

Seiichi Manyama, Apr 17 2021

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

Column 3 of A343510.

Cf. A000010, A001157 (sigma_2(n)), A018804, A054610, A069097, A309323, A332517, A342423, A342433, A343498, A343499, A343513.

A343497:= func< n | (&+[d^3*EulerPhi(Floor(n/d)): d in Divisors(n)]) >;
[A343497(n): n in [1..50]]; // G. C. Greubel, Jun 24 2024

with(numtheory):
seq(add(phi(n/d) * d^3, d in divisors(n)), n = 1..50); # Peter Bala, Jan 20 2024

a[n_] := Sum[GCD[k, n]^3, {k, 1, n}]; Array[a, 50] (* Amiram Eldar, Apr 18 2021 *)
f[p_, e_] := p^(e - 1)*((p^2 + p + 1)*p^(2*e) - 1)/(p + 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* Amiram Eldar, Nov 22 2022 *)
A343497[n_]:= DivisorSum[n, #^3*EulerPhi[n/#] &]; Table[A343497[n], {n, 50}] (* G. C. Greubel, Jun 24 2024 *)

PARI
```
a(n) = sum(k=1, n, gcd(k, n)^3);
```

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

a(n) = sumdiv(n, d, moebius(n/d)*d*sigma(d, 2));

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k*(1+4*x^k+x^(2*k))/(1-x^k)^4))

def A343497(n): return sum(k^3*euler_phi(n/k) for k in (1..n) if (k).divides(n))
[A343497(n) for n in range(1,51)] # G. C. Greubel, Jun 24 2024

a(n) = Sum_{d|n} phi(n/d) * d^3.
a(n) = Sum_{d|n} mu(n/d) * d * sigma_2(d).
G.f.: Sum_{k >= 1} phi(k) * x^k * (1 + 4*x^k + x^(2*k))/(1 - x^k)^4.
Dirichlet g.f.: zeta(s-1) * zeta(s-3) / zeta(s). - Ilya Gutkovskiy, Apr 18 2021
Sum_{k=1..n} a(k) ~ 45*zeta(3)*n^4 / (2*Pi^4). - Vaclav Kotesovec, May 20 2021
Multiplicative with a(p^e) = p^(e-1)*((p^2+p+1)*p^(2*e) - 1)/(p+1). - Amiram Eldar, Nov 22 2022
a(n) = Sum_{1 <= i, j, k <= n} gcd(i, j, k, n) = Sum_{d divides n} d * J_3(n/d), where the Jordan totient function J_3(n) = A059376(n). - Peter Bala, Jan 20 2024

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

A286237 Triangular table: T(n,k) = 0 if k does not divide n, otherwise T(n,k) = P(phi(k), n/k), where P is sequence A000027 used as a pairing function N x N -> N, and phi is Euler totient function, A000010. Table is read by rows as T(1,1), T(2,1), T(2,2), etc.

Original entry on oeis.org

1, 2, 1, 4, 0, 3, 7, 2, 0, 3, 11, 0, 0, 0, 10, 16, 4, 5, 0, 0, 3, 22, 0, 0, 0, 0, 0, 21, 29, 7, 0, 5, 0, 0, 0, 10, 37, 0, 8, 0, 0, 0, 0, 0, 21, 46, 11, 0, 0, 14, 0, 0, 0, 0, 10, 56, 0, 0, 0, 0, 0, 0, 0, 0, 0, 55, 67, 16, 12, 8, 0, 5, 0, 0, 0, 0, 0, 10, 79, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 78, 92, 22, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 0, 21, 106, 0, 17, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36

Offset: 1

Antti Karttunen, May 05 2017

Equally: square array A(n,k) = P(A000010(n), (n+k-1)/n) if n divides (n+k-1), 0 otherwise, read by descending antidiagonals as A(1,1), A(1,2), A(2,1), etc. Here P is sequence A000027 used as a pairing function N x N -> N.
When viewed as a triangular table, this sequence packs the values of phi(k) and quotient n/k (when it is integral) to a single value with the pairing function A000027. The two "components" can be accessed with functions A002260 & A004736, which allows us generate from this sequence various sums related to necklace enumeration (among other things).
For example, we have:
  Sum_{i=A000217(n-1) .. A000217(n)} [a(i) > 0] * A002260(a(i)) * 2^(A004736(a(i))) = A053635(n).
and
  Sum_{i=A000217(n-1) .. A000217(n)} [a(i) > 0] * A002260(a(i)) * 3^(A004736(a(i))) = A054610(n).

			The first fifteen rows of the triangle:
    1,
    2,  1,
    4,  0,  3,
    7,  2,  0,  3,
   11,  0,  0,  0, 10,
   16,  4,  5,  0,  0,  3,
   22,  0,  0,  0,  0,  0, 21,
   29,  7,  0,  5,  0,  0,  0, 10,
   37,  0,  8,  0,  0,  0,  0,  0, 21,
   46, 11,  0,  0, 14,  0,  0,  0,  0, 10,
   56,  0,  0,  0,  0,  0,  0,  0,  0,  0, 55,
   67, 16, 12,  8,  0,  5,  0,  0,  0,  0,  0, 10,
   79,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 78,
   92, 22,  0,  0,  0,  0, 27,  0,  0,  0,  0,  0,  0, 21,
  106,  0, 17,  0, 19,  0,  0,  0,  0,  0,  0,  0,  0,  0, 36
---------------------------------------------------------------
Note how triangle A286239 contains on each row the same numbers in the same "divisibility-allotted" positions, but in reverse order.
In the following examples: a = this sequence interpreted as a one-dimensional sequence, A = interpreted as a square array, T = interpreted as a triangular table, P = A000027 interpreted as a pairing function N x N -> N, phi = Euler totient function, A000010.
---
a(7) = A(1,4) = T(4,1) = P(phi(1),4/1) = P(1,4) = 1+(((1+4)^2 - 1 - (3*4))/2) = 7.
a(30) = A(2,7) = T(8,2) = P(phi(2),8/2) = P(1,4) (i.e., same as above) = 7.
a(10) = A(5,1) = T(5,5) = P(phi(5),5/5) = P(4,1) = 1+(((4+1)^2 - 4 - (3*1))/2) = 10.
a(110) = A(5,11) = T(15,5) = P(phi(5),15/5) = P(4,3) = 1+((4+3)^2 - 4 - (3*3))/2 = 19.

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 rows of triangle/antidiagonals of array
Eric Weisstein's World of Mathematics, Pairing Function

Transpose: A286236.
Cf. A000124 (left edge of the triangle), A000217 (every number at the right edge is a triangular number).
Cf. A000010, A000027, A002024, A002260, A004736, A051731, A053635, A054610, A286235, A286239, A286247.

(* Based on Python script by Indranil Ghosh *)
T[n_, m_] := ((n + m)^2 - n - 3*m + 2)/2
t[n_, k_] := If[Mod[n, k] != 0, 0, T[EulerPhi[k], n/k]]
Table[t[n, k], {n, 1, 20}, {k, 1, n}]
(* David Radcliffe, Jun 12 2025 *)

from sympy import totient
def T(n, m): return ((n + m)**2 - n - 3*m + 2)//2
def t(n, k): return 0 if n%k!=0 else T(totient(k), n//k)
for n in range(1, 21): print([t(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, May 10 2017

(define (A286237 n) (A286237bi (A002260 n) (A004736 n)))
(define (A286237bi row col) (if (not (zero? (modulo (+ row col -1) row))) 0 (let ((a (A000010 row)) (b (quotient (+ row col -1) row))) (* (/ 1 2) (+ (expt (+ a b) 2) (- a) (- (* 3 b)) 2)))))
;; Alternatively, with triangular indexing:
(define (A286237 n) (A286237tr (A002024 n) (A002260 n)))
(define (A286237tr n k) (if (not (zero? (modulo n k))) 0 (let ((a (A000010 k)) (b (/ n k))) (* (/ 1 2) (+ (expt (+ a b) 2) (- a) (- (* 3 b)) 2)))))
;; Note that: (A286237tr n k) is equal to (A286237bi k (+ 1 (- n k))).

As a triangle (with n >= 1, 1 <= k <= n):
T(n,k) = 0 if k does not divide n, otherwise T(n,k) = (1/2)*(2 + ((A000010(k)+(n/k))^2) - A000010(k) - 3*(n/k)).
T(n,k) = A051731(n,k) * A286235(n,k).
Other identities. For all n >= 1:
T(prime(n),prime(n)) = A000217(prime(n)-1).

A286239 Triangular table: T(n,k) = 0 if k does not divide n, otherwise T(n,k) = P(A000010(n/k), k), where P is sequence A000027 used as a pairing function N x N -> N. Table is read by rows as T(1,1), T(2,1), T(2,2), etc.

Original entry on oeis.org

1, 1, 2, 3, 0, 4, 3, 2, 0, 7, 10, 0, 0, 0, 11, 3, 5, 4, 0, 0, 16, 21, 0, 0, 0, 0, 0, 22, 10, 5, 0, 7, 0, 0, 0, 29, 21, 0, 8, 0, 0, 0, 0, 0, 37, 10, 14, 0, 0, 11, 0, 0, 0, 0, 46, 55, 0, 0, 0, 0, 0, 0, 0, 0, 0, 56, 10, 5, 8, 12, 0, 16, 0, 0, 0, 0, 0, 67, 78, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 79, 21, 27, 0, 0, 0, 0, 22, 0, 0, 0, 0, 0, 0, 92, 36, 0, 19, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 106

Offset: 1

Antti Karttunen, May 06 2017

This sequence packs the values of phi(n/k) and k (whenever k divides n) to a single value, with the pairing function A000027. The two "components" can be accessed with functions A002260 & A004736, which allows us generate from this sequence various sums related to necklace enumeration (among other things).
For example, we have:
  Sum_{i=A000217(n-1) .. A000217(n)} [a(i) > 0] * A002260(a(i)) * 2^(A004736(a(i))) = A053635(n).
and
  Sum_{i=A000217(n-1) .. A000217(n)} [a(i) > 0] * A002260(a(i)) * 3^(A004736(a(i))) = A054610(n)
Triangle A286237 has the same property.

			The first fifteen rows of triangle:
   1,
   1,  2,
   3,  0,  4,
   3,  2,  0,  7,
  10,  0,  0,  0, 11,
   3,  5,  4,  0,  0, 16,
  21,  0,  0,  0,  0,  0, 22,
  10,  5,  0,  7,  0,  0,  0, 29,
  21,  0,  8,  0,  0,  0,  0,  0, 37,
  10, 14,  0,  0, 11,  0,  0,  0,  0, 46,
  55,  0,  0,  0,  0,  0,  0,  0,  0,  0, 56,
  10,  5,  8, 12,  0, 16,  0,  0,  0,  0,  0, 67,
  78,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 79,
  21, 27,  0,  0,  0,  0, 22,  0,  0,  0,  0,  0,  0, 92,
  36,  0, 19,  0, 17,  0,  0,  0,  0,  0,  0,  0,  0,  0, 106
   -------------------------------------------------------------
Note how triangle A286237 contains on each row the same numbers in the same "divisibility-allotted" positions, but in reverse order.

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 rows of triangle/antidiagonals of array

Transpose: A286238.
Cf. A000124 (the right edge of the triangle).
Cf. A000010, A000027, A053635, A054610, A054523, A286156, A286237, A286249.

from sympy import totient
def T(n, m): return ((n + m)**2 - n - 3*m + 2)//2
def t(n, k): return 0 if n%k!=0 else T(totient(n//k), k)
for n in range(1, 21): print([t(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, May 09 2017

(define (A286239 n) (A286239tr (A002024 n) (A002260 n)))
(define (A286239tr n k) (if (not (zero? (modulo n k))) 0 (let ((a (A000010 (/ n k))) (b k)) (* (/ 1 2) (+ (expt (+ a b) 2) (- a) (- (* 3 b)) 2)))))

As a triangle (with n >= 1, 1 <= k <= n):

T(n,k) = 0 if k does not divide n, otherwise T(n,k) = (1/2)*(2 + ((A000010(n/k)+k)^2) - A000010(n/k) - 3*k).

cp's OEIS Frontend

A185651 A(n,k) = Sum_{d|n} phi(d)*k^(n/d); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A001867 Number of n-bead necklaces with 3 colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

SageMath

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A286237 Triangular table: T(n,k) = 0 if k does not divide n, otherwise T(n,k) = P(phi(k), n/k), where P is sequence A000027 used as a pairing function N x N -> N, and phi is Euler totient function, A000010. Table is read by rows as T(1,1), T(2,1), T(2,2), etc.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A286239 Triangular table: T(n,k) = 0 if k does not divide n, otherwise T(n,k) = P(A000010(n/k), k), where P is sequence A000027 used as a pairing function N x N -> N. Table is read by rows as T(1,1), T(2,1), T(2,2), etc.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Scheme

Formula