A220691 Table A(i,j) read by antidiagonals in order A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ..., where A(i,j) is the number of ways in which we can add 2 distinct integers from the range 1..i in such a way that the sum is divisible by j.

0, 0, 1, 0, 0, 3, 0, 1, 1, 6, 0, 0, 1, 2, 10, 0, 0, 1, 2, 4, 15, 0, 0, 1, 1, 4, 6, 21, 0, 0, 0, 2, 2, 5, 9, 28, 0, 0, 0, 1, 2, 3, 7, 12, 36, 0, 0, 0, 1, 2, 3, 5, 10, 16, 45, 0, 0, 0, 0, 2, 2, 4, 6, 12, 20, 55, 0, 0, 0, 0, 1, 3, 3, 6, 8, 15, 25, 66, 0, 0, 0, 0

Offset: 1

Author

Antti Karttunen, Feb 18 2013

Keywords

• nonn
• tabl

Examples

			The upper left corner of this square array starts as:
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
   1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...
   3, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ...
   6, 2, 2, 1, 2, 1, 1, 0, 0, 0, 0, ...
  10, 4, 4, 2, 2, 2, 2, 1, 1, 0, 0, ...
  15, 6, 5, 3, 3, 2, 3, 2, 2, 1, 1, ...
Row 1 is all zeros, because it's impossible to choose two distinct integers from range [1]. A(2,1) = 1, as there is only one possibility to choose a pair of distinct numbers from the range [1,2] such that it is divisible by 1, namely 1+2. Also A(2,3) = 1, as 1+2 is divisible by 3.
A(4,1) = 2, as from [1,2,3,4] one can choose two pairs of distinct numbers whose sum is even: {1+3} and {2+4}.
		

Links

• A. Karttunen, The first 150 antidiagonals of the square array, flattened
• Stackexchange, Question 142323
• Index entries for sequences related to subset sums modulo m

Crossrefs

Transpose: A220692. The lower triangular region of this square array is given by A061857, which leaves out about half of the nonzero terms. A220693 is another variant giving 2n-1 terms from the beginning of each row, thus containing all the nonzero terms of this array.

The left column of the table: A000217. The following cases should be checked: the second column: A002620, the third column: A058212 (after the first two terms), the fourth column: A001971.

Programs

Mathematica

a[n_, 1] := n*(n-1)/2; a[n_, k_] := Module[{r}, r = Reduce[1 <= i < j <= n && Mod[i + j, k] == 0, {i, j}, Integers]; Which[Head[r] === Or, Length[r], Head[r] === And, 1, r === False, 0, True, Print[r, " not parsed"]]]; Table[a[n-k+1, k], {n, 1, 13} , {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Mar 04 2014 *)

Formula

See Robert Israel's formula at A061857.