A228640 -id:A228640 - cp's OEIS frontend

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

1, 3, 11, 70, 629, 7826, 117655, 2097684, 43046889, 1000010044, 25937424611, 743008623292, 23298085122493, 793714780783770, 29192926025492783, 1152921504875290696, 48661191875666868497, 2185911559749720272442, 104127350297911241532859

Offset: 1

Vladeta Jovovic, Aug 09 2000

Diagonal of arrays defined in A054630 and A054631.
Given n colors, a(n) = number of necklaces with n beads and 1 up to n colors effectively assigned to them (super_labeled: which also generates n different monochrome necklaces). - Wouter Meeussen, Aug 09 2002
Number of endofunctions on a set with n objects up to cyclic permutation (rotation). E.g., for n = 3, the 11 endofunctions are 1,1,1; 2,2,2; 3,3,3; 1,1,2; 1,2,2; 1,1,3; 1,3,3; 2,2,3; 2,3,3; 1,2,3; and 1,3,2. - Franklin T. Adams-Watters, Jan 17 2007
Also number of pre-necklaces in Sigma(n,n) (see Ruskey and others). - Peter Luschny, Aug 12 2012
From Olivier Gérard, Aug 01 2016: (Start)
Decomposition of the endofunctions by class size.
.
  n |  1   2   3   4    5     6       7
  --+----------------------------------
  1 |  1
  2 |  2   1
  3 |  3   0   8
  4 |  4   6   0  60
  5 |  5   0   0   0  624
  6 |  6  15  70   0    0  7735
  7 |  7   0   0   0    0     0  117648
.
The right diagonal gives the number of Lyndon Words or aperiodic necklaces, A075147. By multiplying each column by the corresponding size and summing, one gets A000312.
(End)

			The 11 necklaces for n=3 are (grouped by partition of 3): (RRR,GGG,BBB),(RRG,RGG, RRB,RBB, GGB,GBB), (RGB,RBG).

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

Alois P. Heinz, Table of n, a(n) for n = 1..200
M. A. Harrison and R. G. High, On the cycle index of a product of permutation groups, J. Combin. Theory, 4 (1968), 277-299.
F. Ruskey, C. Savage, and T. M. Y. Wang, Generating necklaces, Journal of Algorithms, 13(3), 414 - 430, 1992.
Index entries for sequences related to groups

Cf. A001323, A001324, A001372, A000312.
Diagonal of arrays defined in A054630, A054631 and A075195.
Cf. A075147 Aperiodic necklaces, a subset of this sequence.
Cf. A000169 Classes under translation mod n
Cf. A168658 Classes under complement to n+1
Cf. A130293 Classes under translation and rotation
Cf. A081721 Classes under rotation and reversal
Cf. A275549 Classes under reversal
Cf. A275550 Classes under reversal and complement
Cf. A275551 Classes under translation and reversal
Cf. A275552 Classes under translation and complement
Cf. A275553 Classes under translation, complement and reversal
Cf. A275554 Classes under translation, rotation and complement
Cf. A275555 Classes under translation, rotation and reversal
Cf. A275556 Classes under translation, rotation, complement and reversal
Cf. A275557 Classes under rotation and complement
Cf. A275558 Classes under rotation, complement and reversal
Cf. A228640.

with(numtheory):
a:= n-> add(phi(d)*n^(n/d), d=divisors(n))/n:
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 18 2013

Table[Fold[ #1+EulerPhi[ #2] n^(n/#2)&, 0, Divisors[n]]/n, {n, 7}]

a(n) = sum(k=1,n,n^gcd(k,n)) / n; \\ Joerg Arndt, Mar 19 2017

# This algorithm counts all n-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime. It is algorithm F in Knuth 7.2.1.1.
def A056665_list(n):
    C = []
    for m in (1..n):
        a = [0]*(n+1); a[0]=-1;
        j = 1; count = 0
        while(true):
            if m%j == 0 : count += 1;
            j = n
            while a[j] >= m-1 : j -= 1
            if j == 0 : break
            a[j] += 1
            for k in (j+1..n): a[k] = a[k-j]
        C.append(count)
    return C

def A056665(n): return sum(euler_phi(d)*n^(n//d)//n for d in divisors(n))
[A056665(n) for n in (1..18)] # Peter Luschny, Aug 12 2012

a(n) = Sum_{d|n} phi(d)*n^(n/d)/n.
a(n) ~ n^(n-1). - Vaclav Kotesovec, Sep 11 2014
a(n) = (1/n) * Sum_{k=1..n} n^gcd(k,n). - Joerg Arndt, Mar 19 2017
a(n) = [x^n] -Sum_{k>=1} phi(k)*log(1 - n*x^k)/k. - Ilya Gutkovskiy, Mar 21 2018
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = (1/n)*Sum_{k=1..n} n^(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*A228640(n). (End)

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

Original entry on oeis.org

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)

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

Original entry on oeis.org

1, 5, 29, 274, 3129, 47515, 823549, 16843268, 387459861, 10009769725, 285311670621, 8918311856102, 302875106592265, 11112685048729175, 437893951473411261, 18447025557276459016, 827240261886336764193, 39346558373052524325225, 1978419655660313589123997

Offset: 1

Ilya Gutkovskiy, Feb 14 2020

nonn

If n is prime, a(n) = n-1 + n^n. - Robert Israel, Feb 16 2020

Robert Israel, Table of n, a(n) for n = 1..386

Cf. A000010, A008683, A018804, A031971, A069097, A226561, A228640, A321294.

[&+[Gcd(n,k)^n:k in [1..n]]: n in [1..20]]; // Marius A. Burtea, Feb 15 2020

f:= n -> add(igcd(n,k)^n,k=1..n):
map(f, [$1..30]); # Robert Israel, Feb 16 2020

Table[Sum[GCD[n, k]^n, {k, 1, n}], {n, 1, 19}]
Table[Sum[EulerPhi[n/d] d^n, {d, Divisors[n]}], {n, 1, 19}]
Table[Sum[MoebiusMu[n/d] d DivisorSigma[n - 1, d], {d, Divisors[n]}], {n, 1, 19}]

a(n) = sum(k=1, n, gcd(n, k)^n); \\ Michel Marcus, Feb 14 2020

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

a(n) = Sum_{d|n} phi(n/d) * d^n.
a(n) = Sum_{d|n} mu(n/d) * d * sigma_(n-1)(d).
a(n) ~ n^n.
From Richard L. Ollerton, May 09 2021: (Start)
a(n) = Sum_{k=1..n} (n/gcd(n,k))^n*phi(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))*gcd(n,k)*sigma_(n-1)(gcd(n,k))/phi(n/gcd(n,k)). (End)

A332621 a(n) = (1/n) * Sum_{k=1..n} n^(n/gcd(n, k)).

Original entry on oeis.org

1, 3, 19, 133, 2501, 15631, 705895, 8389641, 258280489, 4000040011, 259374246011, 2972033984173, 279577021469773, 4762288684702095, 233543408203327951, 9223372037928525841, 778579070010669895697, 13115469358498302735067, 1874292305362402347591139

Offset: 1

Ilya Gutkovskiy, Feb 17 2020

nonn

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

Cf. A000010, A056665, A130586, A226561, A228640, A308814, A321349, A332620.

[(1/n)*&+[n^(n div Gcd(n,k)):k in [1..n]]:n in [1..20]]; // Marius A. Burtea, Feb 17 2020

Table[(1/n) Sum[n^(n/GCD[n, k]), {k, 1, n}], {n, 1, 19}]
Table[(1/n) Sum[EulerPhi[d] n^d, {d, Divisors[n]}], {n, 1, 19}]
Table[SeriesCoefficient[Sum[Sum[EulerPhi[j] n^(j - 1) x^(k j), {j, 1, n}], {k, 1, n}], {x, 0, n}], {n, 1, 19}]

a(n) = sum(k=1, n, n^(n/gcd(n, k)))/n; \\ Michel Marcus, Mar 10 2021

a(n) = [x^n] Sum_{k>=1} Sum_{j>=1} phi(j) * n^(j-1) * x^(k*j).
a(n) = (1/n) * Sum_{k=1..n} n^(lcm(n, k)/k).
a(n) = (1/n) * Sum_{d|n} phi(d) * n^d.
a(n) = A332620(n) / n.

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)

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

Original entry on oeis.org

1, 2, 6, 3, 12, 33, 4, 20, 72, 280, 5, 30, 135, 660, 3145, 6, 42, 228, 1344, 7800, 46956, 7, 56, 357, 2464, 16835, 118104, 823585, 8, 72, 528, 4176, 32800, 262800, 2097200, 16781472, 9, 90, 747, 6660, 59085, 532350, 4783023, 43053480, 387422001

Offset: 1

N. J. A. Sloane, Apr 16 2000

			1;
2, 6;
3, 12, 33;
4, 20, 72,  280;
5, 30, 135, 660,  3145;
6, 42, 228, 1344, 7800, 46956;
...

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

Cf. A054618, A054630, A054631, A185651 (transpose).

Main diagonal gives: A228640.

with(numtheory):
T:= (n, k)-> add(phi(d)*n^(k/d), d=divisors(k)):
seq(seq(T(n,k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 28 2013

T[n_, 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, Feb 25 2015 *)

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

A332620 a(n) = Sum_{k=1..n} n^(n/gcd(n, k)).

Original entry on oeis.org

1, 6, 57, 532, 12505, 93786, 4941265, 67117128, 2324524401, 40000400110, 2853116706121, 35664407810076, 3634501279107049, 66672041585829330, 3503151123049919265, 147573952606856413456, 13235844190181388226849, 236078448452969449231206, 35611553801885644604231641

Offset: 1

Ilya Gutkovskiy, Feb 17 2020

nonn

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

Cf. A000010, A056665, A066108, A226561, A228640, A321349, A332621.

[&+[n^(n div Gcd(n,k)):k in [1..n]]:n in [1..20]]; // Marius A. Burtea, Feb 17 2020

Table[Sum[n^(n/GCD[n, k]), {k, 1, n}], {n, 1, 19}]
Table[Sum[EulerPhi[d] n^d, {d, Divisors[n]}], {n, 1, 19}]
Table[SeriesCoefficient[Sum[Sum[EulerPhi[j] n^j x^(k j), {j, 1, n}], {k, 1, n}], {x, 0, n}], {n, 1, 19}]

a(n) = sum(k=1, n, n^(n/gcd(n, k))); \\ Michel Marcus, Mar 10 2021

a(n) = [x^n] Sum_{k>=1} Sum_{j>=1} phi(j) * n^j * x^(k*j).
a(n) = Sum_{k=1..n} n^(lcm(n, k)/k).
a(n) = Sum_{d|n} phi(d) * n^d.
a(n) = n * A332621(n).

A332653 a(n) = (1/n) * Sum_{k=1..n} n^(k/gcd(n, k)).

Original entry on oeis.org

1, 2, 5, 19, 157, 1306, 19609, 266372, 5321721, 101001214, 2593742461, 61920391842, 1941507093541, 56984643437138, 2076518238897649, 72340172854919941, 3041324492229179281, 121440691499123469858, 5784852794328402307381, 262799364106291328009626

Offset: 1

Ilya Gutkovskiy, Feb 18 2020

nonn

Cf. A023037, A056665, A057661, A226561, A228640, A332620, A332621, A332652, A332655.

[(1/n)*&+[n^(k div Gcd(n,k)):k in [1..n]]:n in [1..21]]; // Marius A. Burtea, Feb 18 2020

Table[(1/n) Sum[n^(k/GCD[n, k]), {k, 1, n}], {n, 1, 20}]
Table[Sum[Sum[If[GCD[k, d] == 1, n^(k - 1), 0], {k, 1, d}], {d, Divisors[n]}], {n, 1, 20}]

a(n) = (1/n) * Sum_{k=1..n} n^(lcm(n, k)/n).
a(n) = Sum_{d|n} Sum_{k=1..d, gcd(k, d) = 1} n^(k-1).
a(n) = A332652(n) / n.

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

Original entry on oeis.org

1, 5, 30, 264, 3135, 46709, 823564, 16777528, 387420759, 10000003265, 285311670666, 8916100500148, 302875106592331, 11112006826381965, 437893890380965260, 18446744073726350224, 827240261886336764313, 39346408075296928032645

Offset: 1

Seiichi Manyama, Mar 10 2021

Cf. A000217, A228640, A342394, A342395.

a[n_] := Sum[k^GCD[k, n], {k, 1, n}]; Array[a, 18] (* Amiram Eldar, Mar 10 2021 *)

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

If p is prime, a(p) = A000217(p-1) + p^p = (p-1)*p/2 + p^p.

A332652 a(n) = Sum_{k=1..n} n^(k/gcd(n, k)).

Original entry on oeis.org

1, 4, 15, 76, 785, 7836, 137263, 2130976, 47895489, 1010012140, 28531167071, 743044702104, 25239592216033, 797785008119932, 31147773583464735, 1157442765678719056, 51702516367896047777, 2185932446984222457444, 109912203092239643840239, 5255987282125826560192520

Offset: 1

Ilya Gutkovskiy, Feb 18 2020

nonn

Cf. A031972, A056665, A057661, A226561, A228640, A332620, A332621, A332653, A332655.

[&+[n^(k div Gcd(n,k)):k in [1..n]]:n in [1..21]]; // Marius A. Burtea, Feb 18 2020

Table[Sum[n^(k/GCD[n, k]), {k, 1, n}], {n, 1, 20}]
Table[Sum[Sum[If[GCD[k, d] == 1, n^k, 0], {k, 1, d}], {d, Divisors[n]}], {n, 1, 20}]

a(n) = Sum_{k=1..n} n^(lcm(n, k)/n).
a(n) = Sum_{d|n} Sum_{k=1..d, gcd(k, d) = 1} n^k.
a(n) = n * A332653(n).

cp's OEIS Frontend

A056665 Number of equivalence classes of n-valued Post functions of 1 variable under action of complementing group C(1,n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Sage

Formula

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A332621 a(n) = (1/n) * Sum_{k=1..n} n^(n/gcd(n, k)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A332620 a(n) = Sum_{k=1..n} n^(n/gcd(n, k)).

Views