login
Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{1 <= x_1 <= x_2 <= ... <= x_k <= n} gcd(x_1, x_2, ..., x_k).
5

%I #34 Sep 13 2024 11:59:28

%S 1,1,3,1,4,6,1,5,9,10,1,6,13,17,15,1,7,18,28,26,21,1,8,24,44,47,41,28,

%T 1,9,31,66,83,82,54,36,1,10,39,95,140,159,116,74,45,1,11,48,132,225,

%U 293,249,172,95,55,1,12,58,178,346,512,509,401,235,122,66,1,13,69,234,512,852,980,888,592,321,143,78

%N Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = Sum_{1 <= x_1 <= x_2 <= ... <= x_k <= n} gcd(x_1, x_2, ..., x_k).

%H Seiichi Manyama, <a href="/A345229/b345229.txt">Antidiagonals n = 1..140, flattened</a>

%F G.f. of column k: (1/(1 - x)) * Sum_{j>=1} phi(j) * x^j/(1 - x^j)^k.

%F T(n,k) = Sum_{j=1..n} Sum_{d|j} phi(j/d) * binomial(d+k-2, k-1).

%F T(n,k) = Sum_{j=1..n} phi(j) * binomial(floor(n/j)+k-1,k). - _Seiichi Manyama_, Sep 13 2024

%e G.f. of column 3: (1/(1 - x)) * Sum_{j>=1} phi(j) * x^j/(1 - x^j)^3.

%e Square array begins:

%e 1, 1, 1, 1, 1, 1, 1, ...

%e 3, 4, 5, 6, 7, 8, 9, ...

%e 6, 9, 13, 18, 24, 31, 39, ...

%e 10, 17, 28, 44, 66, 95, 132, ...

%e 15, 26, 47, 83, 140, 225, 346, ...

%e 21, 41, 82, 159, 293, 512, 852, ...

%e 28, 54, 116, 249, 509, 980, 1782, ...

%p T:= (n, k)-> coeff(series((1/(1-x))* add(numtheory[phi](j)

%p *x^j/(1-x^j)^k, j=1..n), x, n+1), x, n):

%p seq(seq(T(n, 1+d-n), n=1..d), d=1..12); # _Alois P. Heinz_, Jun 11 2021

%t T[n_, k_] := Sum[DivisorSum[j, EulerPhi[j/#] * Binomial[k + # - 2, k - 1] &], {j, 1, n}]; Table[T[k, n - k + 1], {n, 1, 12}, {k, 1, n}] // Flatten (* _Amiram Eldar_, Jun 11 2021 *)

%o (PARI) T(n, k) = sum(j=1, n, sumdiv(j, d, eulerphi(j/d)*binomial(d+k-2, k-1)));

%o (PARI) T(n, k) = sum(j=1, n, eulerphi(j)*binomial(n\j+k-1, k)); \\ _Seiichi Manyama_, Sep 13 2024

%Y Columns k=1..4 give A000217, A272718, A344521, A344992.

%Y Main diagonal gives A345230.

%Y Cf. A343516, A344479.

%K nonn,tabl

%O 1,3

%A _Seiichi Manyama_, Jun 11 2021