A344527 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of ordered k-tuples (x_1, x_2, ..., x_k) with gcd(x_1, x_2, ..., x_k) = 1 (1 <= {x_1, x_2, ..., x_k} <= n).

1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 25, 11, 1, 1, 31, 79, 55, 19, 1, 1, 63, 241, 239, 115, 23, 1, 1, 127, 727, 991, 607, 181, 35, 1, 1, 255, 2185, 4031, 3091, 1199, 307, 43, 1, 1, 511, 6559, 16255, 15559, 7501, 2303, 439, 55, 1, 1, 1023, 19681, 65279, 77995, 45863, 16531, 3823, 637, 63, 1

Offset

1,5

Links

Seiichi Manyama, Antidiagonals n = 1..140, flattened.

Formula

G.f. of column k: (1/(1 - x)) * Sum_{i>=1} mu(i) * ( Sum_{j=1..k} A008292(k, j) * x^(i*j) )/(1 - x^i)^k.

T(n,k) = Sum_{j=1..n} mu(j) * floor(n/j)^k.

T(n,k) = n^k - Sum_{j=2..n} T(floor(n/j),k).

Example

G.f. of column 3: (1/(1 - x)) * Sum_{i>=1} mu(i) * (x^i + 4*x^(2*i) + x^(3*i))/(1 - x^i)^3.
Square array begins:
  1,  1,   1,    1,    1,     1, ...
  1,  3,   7,   15,   31,    63, ...
  1,  7,  25,   79,  241,   727, ...
  1, 11,  55,  239,  991,  4031, ...
  1, 19, 115,  607, 3091, 15559, ...
  1, 23, 181, 1199, 7501, 45863, ...

Mathematica

T[n_, k_] := Sum[MoebiusMu[j] * Quotient[n, j]^k, {j, 1, n}]; Table[T[k, n - k + 1], {n, 1, 11}, {k, 1, n}] // Flatten (* Amiram Eldar, May 22 2021 *)

Prog

(PARI) T(n, k) = sum(j=1, n, moebius(j)*(n\j)^k);
(PARI) T(n, k) = n^k-sum(j=2, n, T(n\j, k));
(Python)
from functools import lru_cache
from itertools import count, islice
@lru_cache(maxsize=None)
def A344527_T(n, k):
    if n == 0:
        return 0
    c, j, k1 = 1, 2, n//2
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A344527_T(k1, k)
        j, k1 = j2, n//j2
    return n*(n**(k-1)-1)-c+j
def A344527_gen(): # generator of terms
    return (A344527_T(k+1, n-k) for n in count(1) for k in range(n))
A344527_list = list(islice(A344527_gen(), 30)) # Chai Wah Wu, Nov 02 2023

Crossrefs

Columns k=1..6 give A000012, A018805, A071778, A082540, A082544, A343978.

T(n,n) gives A332468.

Cf. A343510, A343516, A344479.

Sequence in context: A157836 A205497 A063394 * A193871 A108470 A328300

Adjacent sequences: A344524 A344525 A344526 * A344528 A344529 A344530

Keyword

nonn,tabl

Author

Seiichi Manyama, May 22 2021

Status

approved