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,6

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

Formula

See Robert Israel's formula at A061857.

Example

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}.

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 *)

Prog

(Scheme function, written after Robert Israel's formula given at A061857):
(define (A220691 n) (A220691bi (A002260 n) (A004736 n)))
(define (A220691bi n k) (let* ((b (modulo (+ 1 n) k)) (q (/ (- (+ 1 n) b) k)) (c (modulo k 2))) (cond ((< b 2) (+ (* q q k (/ 1 2)) (* q b) (* -2 q) (* -1 b) 1 (* c q (/ 1 2)))) ((>= b (/ (+ k 3) 2)) (+ (* q q k (/ 1 2)) (* q b) (* -2 q) b -1 (* (/ k -2)) (* c (+ 1 q) (/ 1 2)))) (else (+ (* q q k (/ 1 2)) (* q b) (* -2 q) (* c q (/ 1 2)))))))

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.

Sequence in context: A242782 A011256 A294212 * A271023 A370041 A143624

Adjacent sequences: A220688 A220689 A220690 * A220692 A220693 A220694

Keyword

nonn,tabl

Author

Antti Karttunen, Feb 18 2013

Status

approved