Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

1 Answer 1

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)$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.