A275554
Number of classes of endofunctions of [n] under vertical translation mod n, rotation and complement to n+1.
Original entry on oeis.org
1, 1, 2, 3, 14, 65, 680, 8407, 131416, 2391515, 50006040, 1178973851, 30958827996, 896080197025, 28346960490560, 973097534189967, 36028797169965112, 1431211525754907905, 60719765554419645244, 2740193428892401092979, 131072000000281600209176
Offset: 0
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.
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.
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
A275555
Number of classes of endofunctions of [n] under vertical translation mod n, rotation and reversal.
Original entry on oeis.org
1, 1, 2, 4, 16, 77, 730, 8578, 132422, 2394795, 50031012, 1179054376, 30959574248, 896082610429, 28346986843640, 973097619619654, 36028798243701780, 1431211529242786625, 60719765604009463866, 2740193429053744941868, 131072000002841600036024
Offset: 0
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.
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.
A275556 Classes under translation, rotation, complement and reversal
Cf.
A275557 Classes under rotation and complement
Cf.
A275558 Classes under rotation, complement and reversal
A275556
Number of classes of endofunctions of [n] under vertical translation mod n, rotation, complement to n+1 and reversal.
Original entry on oeis.org
1, 1, 2, 3, 13, 45, 412, 4375, 66988, 1199038, 25033020, 589567451, 15480284910, 448042511917, 14173510363424, 486548852524671, 18014399792942108, 715605766365332673, 30359882832309625502, 1370096714607544395379, 65536000002956800104588
Offset: 0
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.
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.
A275557 Classes under rotation and complement
Cf.
A275558 Classes under rotation, complement and reversal
A275557
Number of classes of endofunctions of [n] under rotation and complement to n+1.
Original entry on oeis.org
1, 1, 2, 6, 38, 315, 3932, 58828, 1049108, 21523445, 500010024, 12968712306, 371504436220, 11649042561247, 396857394156656, 14596463012746392, 576460752571867208, 24330595937833434249, 1092955779880370116836, 52063675148955620766430, 2621440000000512000336088
Offset: 0
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.
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.
A275558 Classes under rotation, complement and reversal
A228640
a(n) = Sum_{d|n} phi(d)*n^(n/d).
Original entry on oeis.org
0, 1, 6, 33, 280, 3145, 46956, 823585, 16781472, 387422001, 10000100440, 285311670721, 8916103479504, 302875106592409, 11112006930972780, 437893890382391745, 18446744078004651136, 827240261886336764449, 39346408075494964903956, 1978419655660313589124321
Offset: 0
-
[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
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
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
-
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
A215474
Triangle read by rows: number of k-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime.
Original entry on oeis.org
1, 1, 3, 1, 5, 14, 1, 8, 32, 90, 1, 14, 80, 294, 829, 1, 23, 196, 964, 3409, 9695, 1, 41, 508, 3304, 14569, 49685, 141280, 1, 71, 1318, 11464, 63319, 259475, 861580, 2447592, 1, 127, 3502, 40584, 280319, 1379195, 5345276, 17360616, 49212093, 1, 226, 9382
Offset: 1
T(4, 3) counts the 32 ternary preprimes of length 4 which are:
0000,0001,0002,0010,0011,0012,0020,0021,0022,0101,0102,
0110,0111,0112,0120,0121,0122,0202,0210,0211,0212,0220,
0221,0222,1111,1112,1121,1122,1212,1221,1222,2222.
Triangle starts (compare the table A143328 as a square array):
[1]
[1, 3]
[1, 5, 14]
[1, 8, 32, 90]
[1, 14, 80, 294, 829]
[1, 23, 196, 964, 3409, 9695]
[1, 41, 508, 3304, 14569, 49685, 141280]
- D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.
-
# From Alois P. Heinz A143328.
with(numtheory):
f0 := proc(n) option remember; unapply(k^n-add(f0(d)(k),d=divisors(n) minus{n}),k) end;
f2 := proc(n) option remember; unapply(f0(n)(x)/n,x) end;
g2 := proc(n) option remember; unapply(add(f2(j)(x),j=1..n),x) end;
A215474 := (n, k) -> g2(n)(k);
seq(print(seq(A215474(n,d),d=1..n)),n=1..8);
-
t[n_, k_] := Sum[(1/j)*MoebiusMu[j/d]*k^d, {j, 1, n}, {d, Divisors[j]}]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 26 2013 *)
-
# This algorithm generates and counts all k-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 A215474_count(n, k):
a = [0]*(n+1); a[0]=-1
j = 1; count = 0
while True:
count += 1;
j = n
while a[j] >= k-1 : j -= 1
if j == 0 : break
a[j] += 1
for i in (j+1..n): a[i] = a[i-j]
return count
def A215474(n,k):
return add((1/j)*add(moebius(j/d)*k^d for d in divisors(j)) for j in (1..n))
for n in (1..9): print([A215474(n,k) for k in (1..n)])
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
-
[(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
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
-
[&+[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
A212360
Partition array a(n,k) with the total number of necklaces (C_n symmetry) with n beads, each available in n colors, with color signature given by the k-th partition of n in Abramowitz-Stegun(A-St) order.
Original entry on oeis.org
1, 2, 1, 3, 6, 2, 4, 12, 12, 36, 6, 5, 20, 40, 120, 180, 240, 24, 6, 30, 90, 60, 300, 1200, 320, 1200, 2700, 1800, 120, 7, 42, 126, 210, 630, 3150, 2100, 3150, 4200, 25200, 12600, 12600, 37800, 15120, 720, 8, 56, 224, 392, 280, 1176, 7056, 11760, 9072, 11760, 11760, 88200, 58800, 176400, 22260, 58800, 470400, 352800, 141120, 529200, 141120, 5040
Offset: 1
n\k 1 2 3 4 5 6 7 8 9 10 11
1 1
2 2 1
3 3 6 2
4 4 12 12 36 6
5 5 20 40 120 180 240 24
6 6 30 90 60 300 1200 320 1200 2700 1800 120
...
See the link for the rows n=1..15.
a(3,1)=3 because the 3 necklaces with 3 beads coming in 3 colors have the color multinomials (here monomials) c[1]^3=c[1]*c[1]*c[1], c[2]^3 and c[3]^3. The partition of 3 is 3, the color representative is c[1]^3, and the equivalence class with color signature from the partition 3 has the three given members.
a(3,2)=6 from the color signature 2,1 with the representative multinomial c[1]^2 c[2] with coefficient A212359(3,2)=1, the only 3-necklace cyclic(112) (taking j for the color c[j]), and A035206(3,2)=6 members of the whole color equivalence class: cyclic(112), cyclic(113), cyclic(221), cyclic(223), cyclic(331) and cyclic(332).
a(3,3)=2, color signature 1^3=1,1,1 with representative multinomial c[1]*c[2]*c[3] with coefficient A212359(3,3)=2 from the two necklaces cyclic(1,2,3) and cyclic (1,3,2). There are no other members in this class (A035206(3,3)=1).
The sum of row nr. 3 is 11=A056665(3). See the example given there with c[1]=R, c[2]=G and c[3]=B.
Comments