cp's OEIS Frontend

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.

%I A054630 #65 Mar 22 2024 19:07:18
%S A054630 1,2,3,3,6,11,4,10,24,70,5,15,45,165,629,6,21,76,336,1560,7826,7,28,
%T A054630 119,616,3367,19684,117655,8,36,176,1044,6560,43800,299600,2097684,9,
%U A054630 45,249,1665,11817,88725,683289,5381685,43046889,10,55,340,2530,20008,166870,1428580,12501280,111111340,1000010044
%N 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.
%C A054630 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
%C A054630 From _Petros Hadjicostas_, Sep 12 2018: (Start)
%C A054630 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.
%C A054630 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.
%C A054630 (End)
%D A054630 D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.
%H A054630 Peter Luschny, <a href="/A054630/b054630.txt">Rows 1..45, flattened</a>
%H A054630 H. Fredricksen and I. J. Kessler, <a href="https://doi.org/10.1016/0012-365X(86)90089-0">An algorithm for generating necklaces of beads in two colors</a>, Discrete Math. 61 (1986), 181-188.
%H A054630 H. Fredricksen and J. Maiorana, <a href="https://doi.org/10.1016/0012-365X(78)90002-X">Necklaces of beads in k colors and k-ary de Bruijn sequences</a>, Discrete Math. 23(3) (1978), 207-210. Reviewed in  MR0523071 (80e:05007).
%H A054630 Peter Luschny, <a href="/A054630/a054630.txt">Implementation of the FKM algorithm in SageMath and Julia</a>.
%H A054630 F. Ruskey, C. Savage, and T. M. Y. Wang, <a href="http://dx.doi.org/10.1016/0196-6774(92)90047-G">Generating necklaces</a>, Journal of Algorithms, 13(3), 1992, 414-430.
%H A054630 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A054630 T(n,n) = A056665(n). - _Peter Luschny_, Aug 12 2012
%F A054630 T(n,k) = (1/k)*Sum_{i=1..k} n^gcd(i, k). - _Peter Luschny_, Sep 10 2018
%e A054630 Triangle starts:
%e A054630   1;
%e A054630   2,  3;
%e A054630   3,  6, 11;
%e A054630   4, 10, 24, 70;
%e A054630   5, 15, 45, 165,  629;
%e A054630   6, 21, 76, 336, 1560, 7826;
%e A054630 The 24 necklaces over {0,1,2} of length 4 are:
%e A054630   0000,0001,0002,0011,0012,0021,0022,0101,0102,0111,0112,0121,
%e A054630   0122,0202,0211,0212,0221,0222,1111,1112,1122,1212,1222,2222.
%e A054630 The 24 necklaces over {0,1,2,3} of length 3 are:
%e A054630   000,001,002,003,011,012,013,021,022,023,031,032,
%e A054630   033,111,112,113,122,123,132,133,222,223,233,333.
%p A054630 T := (n,k) -> add(n^igcd(i,k), i=1..k)/k:
%p A054630 seq(seq(T(n,k), k=1..n), n=1..10); # _Peter Luschny_, Sep 10 2018
%t A054630 T[n_, k_] := 1/k Sum[EulerPhi[d] n^(k/d), {d, Divisors[k]}];
%t A054630 Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 30 2018 *)
%o A054630 (Sage)
%o A054630 def A054630(n,k): return (1/k)*add(euler_phi(d)*n^(k/d) for d in divisors(k))
%o A054630 for n in (1..9):
%o A054630     print([A054630(n,k) for k in (1..n)]) # _Peter Luschny_, Aug 12 2012
%o A054630 (Julia)
%o A054630 A054630(n::Int, k::Int) = div(sum(n^gcd(i,k) for i in 1:k), k)
%o A054630 for n in 1:6
%o A054630     println([A054630(n, k) for k in 1:n])
%o A054630 end # _Peter Luschny_, Sep 10 2018
%Y A054630 Cf. A054631, A054618, A054619, A056665, A215474. Upper triangle of A075195.
%K A054630 nonn,tabl
%O A054630 1,2
%A A054630 _N. J. A. Sloane_, Apr 16 2000, revised Mar 21 2007