0
$\begingroup$

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

  • 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.2012-05-07

1 Answers 1

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

  • 0
    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}$.2012-05-09