A054619 -id:A054619 - cp's OEIS frontend

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

0, 1, 6, 33, 280, 3145, 46956, 823585, 16781472, 387422001, 10000100440, 285311670721, 8916103479504, 302875106592409, 11112006930972780, 437893890382391745, 18446744078004651136, 827240261886336764449, 39346408075494964903956, 1978419655660313589124321

Offset: 0

Alois P. Heinz, Aug 28 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200

Main diagonal of A054618, A054619, A185651.

Cf. A000010, A056665.

[0] cat [&+[EulerPhi(d)*n^(n div d): d in Divisors(n)]:n in [1..20]]; // Marius A. Burtea, Feb 15 2020

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

a[0] = 0; a[n_] := DivisorSum[n, EulerPhi[#]*n^(n/#)&]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 21 2017 *)

a(n) = if (n, sumdiv(n, d, eulerphi(d)*n^(n/d)), 0); \\ Michel Marcus, Feb 15 2020; corrected Jun 13 2022

a(n) = sum(k=1, n, n^gcd(k, n)); \\ Seiichi Manyama, Mar 10 2021

from sympy import totient, divisors
def A228640(n):
    return sum(totient(d)*n**(n//d) for d in divisors(n,generator=True)) # Chai Wah Wu, Feb 15 2020

a(n) = Sum_{k=1..n} n^gcd(k,n) = n * A056665(n). - Seiichi Manyama, Mar 10 2021

a(n) = Sum_{k=1..n} n^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021

A054630 T(n,k) = Sum_{d|k} phi(d)*n^(k/d)/k, triangle read by rows, T(n,k) for n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 2, 3, 3, 6, 11, 4, 10, 24, 70, 5, 15, 45, 165, 629, 6, 21, 76, 336, 1560, 7826, 7, 28, 119, 616, 3367, 19684, 117655, 8, 36, 176, 1044, 6560, 43800, 299600, 2097684, 9, 45, 249, 1665, 11817, 88725, 683289, 5381685, 43046889, 10, 55, 340, 2530, 20008, 166870, 1428580, 12501280, 111111340, 1000010044

Offset: 1

N. J. A. Sloane, Apr 16 2000, revised Mar 21 2007

T(n, k) is the number of n-ary necklaces of length k (see Ruskey, Savage and Wang). - Peter Luschny, Aug 12 2012, comment corrected at the suggestion of Petros Hadjicostas, Peter Luschny, Sep 10 2018
From Petros Hadjicostas, Sep 12 2018: (Start)
The programs by Peter Luschny below can generate all n-ary necklaces of length k (and all k-ary necklaces of length n) for any positive integer values of n and k, not just for 1 <= k <= n.
From the examples below, we see that the number of 4-ary necklaces of length 3 equals the number of 3-ary necklaces of length 4. The question is whether there are other pairs (n, k) of distinct positive integers such that the number of n-ary necklaces of length k equals the number of k-ary necklaces of length n.
(End)

			Triangle starts:
  1;
  2,  3;
  3,  6, 11;
  4, 10, 24, 70;
  5, 15, 45, 165,  629;
  6, 21, 76, 336, 1560, 7826;
The 24 necklaces over {0,1,2} of length 4 are:
  0000,0001,0002,0011,0012,0021,0022,0101,0102,0111,0112,0121,
  0122,0202,0211,0212,0221,0222,1111,1112,1122,1212,1222,2222.
The 24 necklaces over {0,1,2,3} of length 3 are:
  000,001,002,003,011,012,013,021,022,023,031,032,
  033,111,112,113,122,123,132,133,222,223,233,333.

D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.

Peter Luschny, Rows 1..45, flattened
H. Fredricksen and I. J. Kessler, An algorithm for generating necklaces of beads in two colors, Discrete Math. 61 (1986), 181-188.
H. Fredricksen and J. Maiorana, Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Math. 23(3) (1978), 207-210. Reviewed in MR0523071 (80e:05007).
Peter Luschny, Implementation of the FKM algorithm in SageMath and Julia.
F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 1992, 414-430.
Index entries for sequences related to necklaces

Cf. A054631, A054618, A054619, A056665, A215474. Upper triangle of A075195.

A054630(n::Int, k::Int) = div(sum(n^gcd(i,k) for i in 1:k), k)
for n in 1:6
    println([A054630(n, k) for k in 1:n])
end # Peter Luschny, Sep 10 2018

T := (n,k) -> add(n^igcd(i,k), i=1..k)/k:
seq(seq(T(n,k), k=1..n), n=1..10); # Peter Luschny, Sep 10 2018

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

def A054630(n,k): return (1/k)*add(euler_phi(d)*n^(k/d) for d in divisors(k))
for n in (1..9):
    print([A054630(n,k) for k in (1..n)]) # Peter Luschny, Aug 12 2012

T(n,n) = A056665(n). - Peter Luschny, Aug 12 2012

T(n,k) = (1/k)*Sum_{i=1..k} n^gcd(i, k). - Peter Luschny, Sep 10 2018

A054631 Triangle read by rows: row n (n >= 1) contains the numbers T(n,k) = Sum_{d|n} phi(d)*k^(n/d)/n, for k=1..n.

Original entry on oeis.org

1, 1, 3, 1, 4, 11, 1, 6, 24, 70, 1, 8, 51, 208, 629, 1, 14, 130, 700, 2635, 7826, 1, 20, 315, 2344, 11165, 39996, 117655, 1, 36, 834, 8230, 48915, 210126, 720916, 2097684, 1, 60, 2195, 29144, 217045, 1119796, 4483815, 14913200, 43046889

Offset: 1

N. J. A. Sloane, Apr 16 2000, revised Mar 21 2007

T(n,k) is the number of n-bead necklaces with up to k different colored beads. - Yves-Loic Martin, Sep 29 2020

			1;
1,  3;                                   (A000217)
1,  4,  11;                              (A006527)
1,  6,  24,   70;                        (A006528)
1,  8,  51,  208,   629;                 (A054620)
1, 14, 130,  700,  2635,  7826;          (A006565)
1, 20, 315, 2344, 11165, 39996, 117655;  (A054621)

Seiichi Manyama, Rows n = 1..140, flattened
Wikipedia, Necklace (combinatorics)
Index entries for sequences related to necklaces

Cf. A054630, A054618, A054619, A087854. Lower triangle of A075195.

A054631 := proc(n,k) add( numtheory[phi](d)*k^(n/d),d=numtheory[divisors](n) ) ;  %/n ; end proc: # R. J. Mathar, Aug 30 2011

Needs["Combinatorica`"]; Table[Table[NumberOfNecklaces[n, k, Cyclic], {k, 1, n}], {n, 1, 8}] //Grid (* Geoffrey Critzer, Oct 07 2012, after code by T. D. Noe in A027671 *)
t[n_, k_] := Sum[EulerPhi[d]*k^(n/d)/n, {d, Divisors[n]}]; Table[t[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 20 2014 *)

T(n, k) = sumdiv(n, d, eulerphi(d)*k^(n/d))/n; \\ Seiichi Manyama, Mar 10 2021

T(n, k) = sum(j=1, n, k^gcd(j, n))/n; \\ Seiichi Manyama, Mar 10 2021

T(n,k) = Sum_{j=1..k} binomial(k,j) * A087854(n, j). - Yves-Loic Martin, Sep 29 2020

T(n,k) = (1/n) * Sum_{j=1..n} k^gcd(j, n). - Seiichi Manyama, Mar 10 2021

A054611 a(n) = Sum_{d|n} phi(d)*4^(n/d).

Original entry on oeis.org

0, 4, 20, 72, 280, 1040, 4200, 16408, 65840, 262296, 1049680, 4194344, 16782000, 67108912, 268451960, 1073744160, 4295033440, 17179869248, 68719747320, 274877907016, 1099512679520, 4398046544304, 17592190238920, 70368744177752

Offset: 0

N. J. A. Sloane, Apr 16 2000

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1660
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).

Column k=4 of A185651.
Row n=4 of A054619.
Cf. A001868.

A054611:=proc(n) local k, t1; t1:=0; for k in divisors(n) do t1 := t1+phi(k)*4^(n/k); od: t1; end;

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

a(n) = n * A001868(n).

a(n) = Sum_{k=1..n} 4^gcd(n,k). - Ilya Gutkovskiy, Apr 16 2021

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

Original entry on oeis.org

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

N. J. A. Sloane, Apr 16 2000

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

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

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

Cf. A054619, A054630, A054631.
Main diagonal gives: A228640.
Cf. A000010.

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

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

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

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)

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A054630 T(n,k) = Sum_{d|k} phi(d)*n^(k/d)/k, triangle read by rows, T(n,k) for n >= 1 and 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Sage

Formula

A054631 Triangle read by rows: row n (n >= 1) contains the numbers T(n,k) = Sum_{d|n} phi(d)*k^(n/d)/n, for k=1..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A054611 a(n) = Sum_{d|n} phi(d)*4^(n/d).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula