A054618 Triangle T(n,k) = Sum_{d|n} phi(d)*k^(n/d).

1, 2, 6, 3, 12, 33, 4, 24, 96, 280, 5, 40, 255, 1040, 3145, 6, 84, 780, 4200, 15810, 46956, 7, 140, 2205, 16408, 78155, 279972, 823585, 8, 288, 6672, 65840, 391320, 1681008, 5767328, 16781472, 9, 540, 19755, 262296, 1953405, 10078164, 40354335, 134218800, 387422001

Offset: 1

Author

N. J. A. Sloane, Apr 16 2000

Keywords

• nonn
• tabl

Comments

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

Examples

			1;
2, 6;
3, 12, 33;
4, 24, 96,  280;
5, 40, 255, 1040, 3145;
6, 84, 780, 4200, 15810, 46956;
...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened

Crossrefs

Cf. A054619, A054630, A054631.

Main diagonal gives: A228640.

Cf. A000010.

Programs

Maple

with(numtheory):
T:= (n, k)-> add(phi(d)*k^(n/d), d=divisors(n)):
seq(seq(T(n, k), k=1..n), n=1..10); # Alois P. Heinz, Aug 28 2013
A054618 := proc(n, k)
    add( numtheory[phi](d)*k^(n/d),d=numtheory[divisors](n)) ;
end proc:
seq(seq(A054618(n,k),k=1..n),n=1..10) ; # R. J. Mathar, Jan 23 2022

Mathematica

T[n_, k_] := Sum[EulerPhi[d]*k^(n/d), {d, Divisors[n]}]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 25 2015 *)

PARI

T(n, k) = sumdiv(n, d, eulerphi(d)*k^(n/d)); \\ Michel Marcus, Feb 25 2015

Formula

From Richard L. Ollerton, May 10 2021: (Start)

T(n,k) = Sum_{i=1..n} k^gcd(n,i).

T(n,k) = Sum_{i=1..n} k^(n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)). (End)