# Sequence generation

Can anybody suggest a fast algorithm for generating this Triangle where the $k$-th item at $n$-th row (both starting from 1) tells in how many ways we can add $2$ distinct integers from $1$ to $n$, in such way that the sum is divisible by $k$.

-
oeis.org/A061857 – user30828 May 7 '12 at 19:04
There's a Maple algorithm given there, no? – TMM May 7 '12 at 19:17
Not a complete one though... trinv is not defined. And not fast because it's $O(n^2)$ to get one entry of the triangle. – Robert Israel May 7 '12 at 19:29

The number of ways $g(n,s)$ to add two distinct integers from $1$ to $n$ to get the sum $s$ is $\lfloor \dfrac{s-1}{2} \rfloor$ for $3 \le s \le n+1$ and $\lfloor n - \dfrac{s-1}{2} \rfloor$ for $n+1 \le s \le 2n-1$. In time $O(n)$ you can compute this for each $s$ from $3$ to $2n-1$. Then for each $k$ from $1$ to $2n-1$ you add $g(n,jk)$ for $j$ from $1$ to $\lfloor (2n-1)/k \rfloor$ in time $O(n/k)$, giving a row of the table in $O(n \log n)$.

-
thnx for reply i made a code according to it bit still it is not that fast enough. i need to generate the no of ways for given n and k . the number of test cases are 100000 and n<=10^9 and 2<=k<=10^9. #include<stdio.h> int main() { long long int n,k; int t; long long int i,j,s=0,m=0,l,p; scanf("%d",&t); while(t--) { scanf("%lld%lld",&n,&k); s=0; p=n+1; for(i=k;i<=p;i=i+k) { s=s+((i-1)/2); } m=(n+1)%k; m=n+1-m+k; l=2*n-1; for(i=m;i<=l;i=i+k) { s=s+(long long int)((float)n-((float)(i-1)/2.0)); } printf("%lld\n",s); } } – user30828 May 8 '12 at 20:02
is their a way out – user30828 May 8 '12 at 20:06
Your code seems to be for producing a single element of the table, rather than a whole row. Which do you really want? Also you're using the same index variable i in two nested loops. Do you really want to do that? – Robert Israel May 9 '12 at 0:27
Also note that e.g. if $k$ and $j$ are odd, $\lfloor \dfrac{jk-1}{2} \rfloor = \dfrac{jk-1}{2}$, otherwise $\lfloor \dfrac{jk-1}{2} \rfloor = \dfrac{jk-2}{2}$. – Robert Israel May 9 '12 at 0:39