A056665 -id:A056665 - cp's OEIS frontend

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

1, 3, 11, 68, 629, 7791, 117655, 2097224, 43046745, 1000000637, 25937424611, 743008378618, 23298085122493, 793714773371811, 29192926025391919, 1152921504608944272, 48661191875666868497, 2185911559738739594277, 104127350297911241532859

Offset: 1

Seiichi Manyama, Mar 12 2021

nonn

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

Cf. A000010, A056665, A342421, A342423, A342435.

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

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

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

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

A121774 Number of n-bead necklaces with n+1 colors, divided by (n+1), for n>0, with a(0)=1.

Original entry on oeis.org

1, 1, 2, 6, 33, 260, 2812, 37450, 597965, 11111134, 235796238, 5628851294, 149346730841, 4361070182716, 139013934267864, 4803839602537336, 178901440745010273, 7143501829211426576, 304465936544543927890, 13797052631578947368422, 662424832016591020302673, 33591880889828764020700500

Offset: 0

Paul D. Hanna, Aug 20 2006

nonn

Stefano Spezia, Table of n, a(n) for n = 0..350
Darij Grinberg and Peter Mao, Necklaces over a group with identity product, arXiv:2405.08937 [math.CO], 2024. See p. 23.

Cf. A000010, A121773, A056665, A152290.

a[n_] := DivisorSum[n, EulerPhi[n/#] * (n+1)^(#-1) &] / n; a[0] = 1; Array[a, 20, 0] (* Amiram Eldar, Aug 15 2023 *)

a(n)=if(n==0,1,(1/n)*sumdiv(n,d,eulerphi(n/d)*(n+1)^(d-1)))

/* a(n) = Sum_{k=0..[n/2]} A152290(n, n*k):  */
{A152290(n,k)=local(e_q=1+sum(j=1,n,x^j/prod(i=1,j,(q^i-1)/(q-1))),LW_q=serreverse(x/e_q+x^2*O(x^n))/x); polcoeff(polcoeff(LW_q+x*O(x^n),n,x)*prod(i=1,n,(q^i-1)/(q-1))+q*O(q^k),k,q)}
{a(n)=sum(k=0,n\2,A152290(n, n*k))}
for(n=0,20,print1(a(n),", ")) \\ Paul D. Hanna, Jul 18 2013

a(n) = (1/n)*Sum_{d|n} phi(n/d)*(n+1)^(d-1), for n>0, with a(0)=1.
a(n) = Sum_{k=0..[n/2]} A152290(n, n*k), where A152290 is a triangle of coefficients in a q-analog of the LambertW function. - Paul D. Hanna, Jul 18 2013
a(n) = A121773(n)/(n+1). - Amiram Eldar, Aug 15 2023

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.

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

Original entry on oeis.org

1, 3, 11, 68, 629, 7797, 117655, 2097254, 43046979, 1000000799, 25937424611, 743008402000, 23298085122493, 793714773374529, 29192926027528343, 1152921504613147242, 48661191875666868497, 2185911559739107208115, 104127350297911241532859, 5242880000000008181608132

Offset: 1

Seiichi Manyama, Mar 13 2021

nonn

Martin Ehrenstein, Table of n, a(n) for n = 1..400

Cf. A000010, A018804, A056665, A173235, A341036, A342394, A342433, A342436, A342449.

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

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

If p is prime, a(p) = p-1 + p^(p-1) = A173235(p).

a(19) and beyond from Martin Ehrenstein, Mar 13 2021

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

Original entry on oeis.org

1, 3, 11, 68, 629, 7793, 117655, 2097228, 43046772, 1000000649, 25937424611, 743008379146, 23298085122493, 793714773371841, 29192926025401528, 1152921504608945960, 48661191875666868497, 2185911559738739835591, 104127350297911241532859

Offset: 1

Seiichi Manyama, Mar 10 2021

Cf. A056665, A173235, A342389, A342396.

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

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

If p is prime, a(p) = p-1 + p^(p-1) = A173235(p) = A056665(p).

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

A121773 Number of n-bead necklaces with n+1 colors for n>0, with a(0)=1.

Original entry on oeis.org

1, 2, 6, 24, 165, 1560, 19684, 299600, 5381685, 111111340, 2593758618, 67546215528, 1941507500933, 61054982558024, 2085209014017960, 76861433640597376, 3041324492665174641, 128583032925805678368, 5784852794346334629910, 275941052631578947368440

Offset: 0

Paul D. Hanna, Aug 20 2006

nonn

Stefano Spezia, Table of n, a(n) for n = 0..350

Cf. A121774, A056665.

a[0] = 1; a[n_] := DivisorSum[n, (n+1)^# * EulerPhi[n/#] &] / n; Array[a, 20, 0] (* Amiram Eldar, Aug 15 2023 *)

a(n)=if(n==0,1,(1/n)*sumdiv(n,d,eulerphi(n/d)*(n+1)^d))

a(n) = (1/n)*Sum_{d|n} phi(n/d)*(n+1)^d, for n>0, with a(0)=1.

a(n) is divisible by (n+1); a(n)/(n+1) = A121774(n).

a(18)-a(19) from Amiram Eldar, Aug 15 2023

A213935 Triangle with entry a(n,m) giving the total number of necklaces of n beads (C_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

Original entry on oeis.org

1, 2, 1, 3, 6, 2, 4, 24, 36, 6, 5, 60, 300, 240, 24, 6, 180, 1820, 3900, 1800, 120, 7, 378, 9030, 42000, 50400, 15120, 720, 8, 952, 40824, 357420, 882000, 670320, 141120, 5040, 9, 2088, 169512, 2610720, 11677680, 17781120, 9313920, 1451520, 40320, 10, 4770, 673560, 17193960, 128598624, 345144240, 355622400, 136080000, 16329600, 362880

Offset: 1

Wolfdieter Lang, Jun 27 2012

This triangle is obtained from the array A212360 by summing in the row number n, for n>=1, all entries related to partitions of n with the same number of parts m.
a(n,m) is the total number of necklaces of n beads (C_n symmetry) corresponding to all the color multinomials obtained from all p(n,m)=A008284(n,m) partitions of n with m parts, written in nonincreasing form, by 'exponentiation'. Therefore only m from the available n colors are present, and a(n,m) gives the number of necklaces with n beads with only m of the n available colors present, for m from 1,2,...,n, and n>=1. All of the possible color assignments are counted.
See the comments on A212359 for the Abramowitz-Stegun (A-St) order of partitions, and the 'exponentiation' to obtain multisets, used to encode color multinomials, from partitions.
The row sums of this triangle coincide with the ones of array A212360, and they are given by A056665.

			n\m 1    2      3       4       5       8      7     8 ...
1   1
2   2    1
3   3    6      2
4   4   24     36       6
5   5   60    300     240      24
6   6  180   1820    3900    1800     120
7   7  378   9030   42000   50400   15120     72
8   8  952  40824  357420  882000  670320 141120  5040
...
Row n=9:   9 2088 169512 2610720 11677680 17781120 9313920 1451520 40320.
Row n=10: 10 4770 673560 17193960 128598624 345144240 355622400 136080000 16329600 362880.
a(2,2)=1 from the color monomial c[1]^1*c[2]^1= c[1]*c[2] (from the m=2 partition [1,1] of n=2). The necklace in question is cyclic(12) (we use j for color c[j] in these examples).
a(5,3) = 120 + 180 = 300, from A212360(5,4) + A212360(5,5), because k(5,3,1)=4 and p(5,3)=2.
a(3,1) = 3 from the color monomials c[1]^3, c[2]^3 and c[3]^1. The three necklaces are cyclic(111), cyclic(222) and cyclic(333).
In general a(n,1)=n from the partition [n] providing the color signature (exponent), and the n color choices.
a(3,2) = 6 from the color signature c[.]^2 c[.]^1, (from the m=2 partition [2,1] of n=3), and there are 6 choices for the color indices. The 6 necklaces are cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).
a(3,3) = 2. The color multinomial is c[1]*c[2]*c[3] (from the m=3 partition [1,1,1]). All three available colors are used. There are two non-equivalent necklaces: cyclic(1,2,3) and cyclic(1,3,2).
a(4,2) = 24 from two color signatures c[.]^3 c[.] and c[.]^2 c[.]^2 (from the two m=2 partitions of n=4: [3,1] and [2,2]). The first one produces 4*3=12 necklaces, namely 1112, 1113, 1114, 2221, 2223, 2224, 3331, 3332, 3334, 4441, 4442 and 4443 all taken cyclically. The second color signature leads to another 2*6=12 necklaces: 1122, 1133, 1144, 2233, 2244, 3344, 1212, 1313, 1414, 2323, 2424 and 3434, all taken cyclically. Together they provide the 24 necklaces counted by a(4,2).

Cf. A212360, A056665 (row sums). A075195 (another necklace table).

a(n,m) = Sum_{j=1..p(n,m)}A212360(n,k(n,m,1)+j-1), with k(n,m,1) the position where in the list of partitions of n in A-St order the first with m parts appears, and p(n,m) the number of partitions of n with m parts shown in the array A008284. E.g., n=5, m=3: k(5,3,1)=4, p(5,3)=2.

A319082 A(n, k) = (1/k)Sum_{d|k} EulerPhi(d)n^(k/d) for n >= 0 and k > 0, A(n, 0) = 0, square array read by ascending antidiagonals.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 1, 0, 0, 3, 3, 1, 0, 0, 4, 6, 4, 1, 0, 0, 5, 10, 11, 6, 1, 0, 0, 6, 15, 24, 24, 8, 1, 0, 0, 7, 21, 45, 70, 51, 14, 1, 0, 0, 8, 28, 76, 165, 208, 130, 20, 1, 0, 0, 9, 36, 119, 336, 629, 700, 315, 36, 1, 0, 0, 10, 45, 176, 616, 1560, 2635, 2344, 834, 60, 1, 0, 0, 11, 55, 249, 1044, 3367, 7826, 11165, 8230, 2195, 108, 1, 0

Offset: 0

Peter Luschny, Sep 10 2018

			Array starts:
[n\k][0   1   2    3    4     5      6       7       8        9  ...]
[0]   0,  0,  0,   0,   0,    0,     0,      0,      0,       0, ...
[1]   0,  1,  1,   1,   1,    1,     1,      1,      1,       1, ...
[2]   0,  2,  3,   4,   6,    8,    14,     20,     36,      60, ...
[3]   0,  3,  6,  11,  24,   51,   130,    315,    834,    2195, ...
[4]   0,  4, 10,  24,  70,  208,   700,   2344,   8230,   29144, ...
[5]   0,  5, 15,  45, 165,  629,  2635,  11165,  48915,  217045, ...
[6]   0,  6, 21,  76, 336, 1560,  7826,  39996, 210126, 1119796, ...
[7]   0,  7, 28, 119, 616, 3367, 19684, 117655, 720916, 4483815, ...

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

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
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

Essentially the same table as A075195.
A185651(n, k) = n*A(k, n).
Main diagonal gives A056665.
A054630(n,k) is a subtriangle for n >= 1 and 1 <= k <= n.

with(numtheory):
A := (n, k) -> `if`(k=0, 0, (1/k)*add(phi(d)*n^(k/d), d=divisors(k))):
seq(seq(A(n-k, k), k=0..n), n=0..12);
# Alternatively, row-wise printed as a table:
T := (n, k) -> `if`(k=0, 0, add(n^igcd(i, k), i=1..k)/k):
seq(lprint(seq(T(n, k), k=0..9)), n=0..7);

A(n,k)=if(k==0, 0, sumdiv(k,d, eulerphi(d)*n^(k/d))/k) \\ Andrew Howroyd, Jan 05 2024

def A319082(n, k):
    return 0 if k == 0 else (1/k)*sum(euler_phi(d)*n^(k//d) for d in divisors(k))
for n in (0..7):
    print([n], [A319082(n, k) for k in (0..9)])

A(n, k) = (1/k)*Sum_{i=1..k} n^gcd(i, k) for k > 0.

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A121774 Number of n-bead necklaces with n+1 colors, divided by (n+1), for n>0, with a(0)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Magma

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

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

A121773 Number of n-bead necklaces with n+1 colors for n>0, with a(0)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A213935 Triangle with entry a(n,m) giving the total number of necklaces of n beads (C_n symmetry) with n colors available for each bead, but only m distinct colors present, with m from {1, 2, ..., n} and n >= 1.

Views

Author

Keywords

Comments

Examples

A319082 A(n, k) = (1/k)Sum_{d|k} EulerPhi(d)n^(k/d) for n >= 0 and k > 0, A(n, 0) = 0, square array read by ascending antidiagonals.