cp's OEIS Frontend

A061857 Triangle in which the k-th item in the n-th row (both starting from 1) is the number of ways in which we can add 2 distinct integers from 1 to n in such a way that the sum is divisible by k.

%I A061857 #44 Jan 29 2025 19:36:54
%S A061857 0,1,0,3,1,1,6,2,2,1,10,4,4,2,2,15,6,5,3,3,2,21,9,7,5,4,3,3,28,12,10,
%T A061857 6,6,4,4,3,36,16,12,8,8,5,5,4,4,45,20,15,10,9,7,6,5,5,4,55,25,19,13,
%U A061857 11,9,8,6,6,5,5,66,30,22,15,13,10,10,7,7,6,6,5,78,36,26,18,16,12,12,9,8,7,7
%N A061857 Triangle in which the k-th item in the n-th row (both starting from 1) is the number of ways in which we can add 2 distinct integers from 1 to n in such a way that the sum is divisible by k.
%C A061857 Since the sum of two distinct integers from 1 to n can be as much as 2n-1, this triangular table cannot show all the possible cases. For larger triangles showing all solutions, see A220691 and A220693. - _Antti Karttunen_, Feb 18 2013 [based on _Robert Israel_'s mail, May 07 2012]
%H A061857 Reinhard Zumkeller, <a href="/A061857/b061857.txt">Rows n = 1..150 of triangle, flattened</a>
%H A061857 Stackexchange, <a href="http://math.stackexchange.com/questions/142323/sequence-generation/142364">Question 142323</a>
%H A061857 <a href="/index/Su#subsetsums">Index entries for sequences related to subset sums modulo m</a>
%F A061857 From _Robert Israel_, May 08 2012: (Start)
%F A061857 Let n+1 = b mod k with 0 <= b < k, q = (n+1-b)/k.  Let k = c mod 2, c = 0 or 1.
%F A061857 If b = 0 or 1 then a(n,k) = q^2*k/2 + q*b - 2*q - b + 1 + c*q/2.
%F A061857 If b >= (k+3)/2 then a(n,k) = q^2*k/2 + q*b - 2*q + b - 1 - k/2 + c*(q+1)/2.
%F A061857 Otherwise a(n,k) = q^2*k/2 + q*b - 2*q + c*q/2. (End)
%e A061857 The second term on the sixth row is 6 because we have 6 solutions: {1+3, 1+5, 2+4, 2+6, 3+5, 4+6} and the third term on the same row is 5 because we have solutions {1+2,1+5,2+4,3+6,4+5}.
%e A061857 Triangle begins:
%e A061857    0;
%e A061857    1,  0;
%e A061857    3,  1,  1;
%e A061857    6,  2,  2,  1;
%e A061857   10,  4,  4,  2,  2;
%e A061857   15,  6,  5,  3,  3,  2;
%e A061857   21,  9,  7,  5,  4,  3,  3;
%e A061857   28, 12, 10,  6,  6,  4,  4,  3;
%e A061857   36, 16, 12,  8,  8,  5,  5,  4,  4;
%e A061857   45, 20, 15, 10,  9,  7,  6,  5,  5,  4;
%p A061857 [seq(DivSumChoose2Triangle(j),j=1..120)]; DivSumChoose2Triangle := (n) -> nops(DivSumChoose2(trinv(n-1),(n-((trinv(n-1)*(trinv(n-1)-1))/2))));
%p A061857 DivSumChoose2 := proc(n,k) local a,i,j; a := []; for i from 1 to (n-1) do for j from (i+1) to n do if(0 = ((i+j) mod k)) then a := [op(a),[i,j]]; fi; od; od; RETURN(a); end;
%t A061857 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], {n, 1, 13}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Mar 04 2014 *)
%o A061857 (Haskell)
%o A061857 a061857 n k = length [()| i <- [2..n], j <- [1..i-1], mod (i + j) k == 0]
%o A061857 a061857_row n = map (a061857 n) [1..n]
%o A061857 a061857_tabl = map a061857_row [1..]
%o A061857 -- _Reinhard Zumkeller_, May 08 2012
%o A061857 (Scheme) (define (A061857 n) (A220691bi (A002024 n) (A002260 n))) ;; _Antti Karttunen_, Feb 18 2013. Needs A220691bi from A220691.
%Y A061857 This is the lower triangular region of square array A220691. See A220693 for all nonzero solutions.
%Y A061857 The left edge (first diagonal) of the triangle: A000217, the second diagonal is given by C(((n+(n mod 2))/2), 2)+C(((n-(n mod 2))/2), 2) = A002620, the third diagonal by A058212, the fourth by A001971, the central column by A042963? trinv is given at A054425. Cf. A061865.
%K A061857 nonn,tabl
%O A061857 1,4
%A A061857 _Antti Karttunen_, May 11 2001
%E A061857 Offset corrected by _Reinhard Zumkeller_, May 08 2012