A051731 Triangle read by rows: T(n, k) = 1 if k divides n, T(n, k) = 0 otherwise, for 1 <= k <= n.

1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Author

Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de)

Keywords

• easy
• nice
• nonn
• tabl

Comments

T(n, k) is the number of partitions of n into k equal parts. - Omar E. Pol, Apr 21 2018

This triangle is the lower triangular array L in the LU decomposition of the square array A003989. - Peter Bala, Oct 15 2023

Examples

			The triangle T(n, k) begins:
  n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1:  1
  2:  1  1
  3:  1  0  1
  4:  1  1  0  1
  5:  1  0  0  0  1
  6:  1  1  1  0  0  1
  7:  1  0  0  0  0  0  1
  8:  1  1  0  1  0  0  0  1
  9:  1  0  1  0  0  0  0  0  1
  10: 1  1  0  0  1  0  0  0  0  1
  11: 1  0  0  0  0  0  0  0  0  0  1
  12: 1  1  1  1  0  1  0  0  0  0  0  1
  13: 1  0  0  0  0  0  0  0  0  0  0  0  1
  14: 1  1  0  0  0  0  1  0  0  0  0  0  0  1
  15: 1  0  1  0  1  0  0  0  0  0  0  0  0  0  1
  ... Reformatted and extended. - _Wolfdieter Lang_, Nov 12 2014
		

Links

• Charles R Greathouse IV, Rows n = 1..100, flattened
• Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 2013, pp. 1667-1677.
• Mats Granvik, Illustration.
• Warren P. Johnson, An LDU Factorization in Elementary Number Theory, Mathematics Magazine, Vol. 76, No. 5 (Dec., 2003), pp. 392-394.
• Jeffrey Ventrella, Divisor Plot.

Crossrefs

Cf. A000007, A000203, A002260, A003989, A048158, A049820, A054525.

Cf. A074854, A101508, A115361, A129372, A172119, A175105.

Cf. A000005 (row sums), A032741(n+2) (diagonal sums).

Cf. A243987 (partial sums per row).

Cf. A134546 (A004736 * T, matrix multiplication).

Variants: A113704, A077049, A077051.

Programs

Haskell

a051731 n k = 0 ^ mod n k
a051731_row n = a051731_tabl !! (n-1)
a051731_tabl = map (map a000007) a048158_tabl
-- Reinhard Zumkeller, Aug 13 2013

Magma

[0^(n mod k): k in [1..n], n in [1..17]]; // G. C. Greubel, Jun 22 2024

Maple

A051731 := proc(n, k) if n mod k = 0 then 1 else 0 end if end proc:
# R. J. Mathar, Jul 14 2012

Mathematica

Flatten[Table[If[Mod[n, k] == 0, 1, 0], {n, 20}, {k, n}]]

PARI

for(n=1,17,for(k=1,n,print1(!(n%k)", "))) \\ Charles R Greathouse IV, Mar 14 2012

Python

from math import isqrt, comb
def A051731(n): return int(not (a:=(m:=isqrt(k:=n<<1))+(k>m*(m+1)))%(n-comb(a,2))) # Chai Wah Wu, Nov 13 2024

Sage

A051731_row = lambda n: [int(k.divides(n)) for k in (1..n)]
for n in (1..17): print(A051731_row(n)) # Peter Luschny, Jan 05 2018

Formula

{T(n, k)*k, k=1..n} setminus {0} = divisors(n).

Sum_{k=1..n} T(n, k)*k^i = sigma[i](n), where sigma[i](n) is the sum of the i-th power of the positive divisors of n.

Sum_{k=1..n} T(n, k) = A000005(n).

Sum_{k=1..n} T(n, k)*k = A000203(n).

T(n, k) = T(n-k, k) for k <= n/2, T(n, k) = 0 for n/2 < k <= n-1, T(n, n) = 1.

Rows given by A074854 converted to binary. Example: A074854(4) = 13 = 1101_2; row 4 = 1, 1, 0, 1. - Philippe Deléham, Oct 04 2003

From Paul Barry, Dec 05 2004: (Start)

Binomial transform (product by binomial matrix) is A101508.

Columns have g.f.: x^k/(1-x^(k+1)) (k >= 0). (End)

Matrix inverse of triangle A054525, where A054525(n, k) = MoebiusMu(n/k) if k|n, 0 otherwise. - Paul D. Hanna, Jan 09 2006

From Gary W. Adamson, Apr 15 2007, May 10 2007: (Start)

Equals A129372 * A115361 as infinite lower triangular matrices.

A054525 is the inverse of this triangle (as lower triangular matrix).

This triangle * [1, 2, 3, ...] = sigma(n) (A000203).

This triangle * [1/1, 1/2, 1/3, ...] = sigma(n)/n. (End)

From Reinhard Zumkeller, Nov 01 2009: (Start)

T(n, k) = 0^(n mod k).

T(n, k) = A000007(A048158(n, k)). (End)

From Mats Granvik, Jan 26 2010, Feb 10 2010, Feb 16 2010: (Start)

T(n, k) = A172119(n) mod 2.

T(n, k) = A175105(n) mod 2.

T(n, k) = Sum_{i=1..k-1} (T(n-i, k-1) - T(n-i, k)) for k > 1 and T(n, 1) = 1.

(Jeffrey O. Shallit kindly provided a clarification along with a proof of this formula.) (End)

A049820(n) = number of zeros in n-th row. - Reinhard Zumkeller, Mar 09 2010

The determinant of this matrix where T(n, n) has been swapped with T(1,k) is equal to the n-th term of the Mobius function. - Mats Granvik, Jul 21 2012

T(n, k) = Sum_{y=1..n} Sum_{x=1..n} [GCD((x/y)*(k/n), n) = k]. - Mats Granvik, Dec 17 2023

Extensions

Edited by Peter Luschny, Oct 18 2023