%I #19 Jan 05 2024 12:29:38
%S 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,
%T 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,
%U 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
%N 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.
%D D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.
%H Andrew Howroyd, <a href="/A319082/b319082.txt">Table of n, a(n) for n = 0..1325</a> (first 51 antidiagonals)
%H 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 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 Peter Luschny, <a href="/A054630/a054630.txt">Implementation of the FKM algorithm in SageMath and Julia</a>
%H 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 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A(n, k) = (1/k)*Sum_{i=1..k} n^gcd(i, k) for k > 0.
%e Array starts:
%e [n\k][0 1 2 3 4 5 6 7 8 9 ...]
%e [0] 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
%e [1] 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e [2] 0, 2, 3, 4, 6, 8, 14, 20, 36, 60, ...
%e [3] 0, 3, 6, 11, 24, 51, 130, 315, 834, 2195, ...
%e [4] 0, 4, 10, 24, 70, 208, 700, 2344, 8230, 29144, ...
%e [5] 0, 5, 15, 45, 165, 629, 2635, 11165, 48915, 217045, ...
%e [6] 0, 6, 21, 76, 336, 1560, 7826, 39996, 210126, 1119796, ...
%e [7] 0, 7, 28, 119, 616, 3367, 19684, 117655, 720916, 4483815, ...
%p with(numtheory):
%p A := (n, k) -> `if`(k=0, 0, (1/k)*add(phi(d)*n^(k/d), d=divisors(k))):
%p seq(seq(A(n-k, k), k=0..n), n=0..12);
%p # Alternatively, row-wise printed as a table:
%p T := (n, k) -> `if`(k=0, 0, add(n^igcd(i, k), i=1..k)/k):
%p seq(lprint(seq(T(n, k), k=0..9)), n=0..7);
%o (Sage)
%o def A319082(n, k):
%o return 0 if k == 0 else (1/k)*sum(euler_phi(d)*n^(k//d) for d in divisors(k))
%o for n in (0..7):
%o print([n], [A319082(n, k) for k in (0..9)])
%o (PARI) A(n,k)=if(k==0, 0, sumdiv(k,d, eulerphi(d)*n^(k/d))/k) \\ _Andrew Howroyd_, Jan 05 2024
%Y Essentially the same table as A075195.
%Y A185651(n, k) = n*A(k, n).
%Y Main diagonal gives A056665.
%Y A054630(n,k) is a subtriangle for n >= 1 and 1 <= k <= n.
%K nonn,tabl
%O 0,8
%A _Peter Luschny_, Sep 10 2018
|