Closed form expression for an algorithmically-constructed integer sequence

Question

Consider the following sequence construction:

for i = 1 to (N-1)
   for j = (i+1) to N
        k = k + 1
   end
end

for example, if $N = 6$, then $k = 1,...,15 (15 = N*(N-1)/2)$ and the corresponding $i, j $ are :

 k     i     j
 --------------
 1     1     2
 2     1     3
 3     1     4
 4     1     5
 5     1     6
 6     2     3
 7     2     4
 8     2     5
 9     2     6
10     3     4
11     3     5
12     3     6
13     4     5
14     4     6
15     5     6

As you can see, the way $ k$ is constructed, every $k$ maps to a unique pair $(i,j).$

Question

I need to infer $i, j$ from $N, k$:

i = f(k,N)
j = g(k,n)

Can you think of such a closed form expressions ?

To put it simply, if I tell you $N = 200$. Can you find the $(i, j)$ that correspond to $k = 18241$ without having to run the algorithm that I mentioned.

Any suggestions are welcome. Thank you.

Answer 1

The required formula is: $$k=N(i-1)-\frac{(i-1)i}2+j-i$$ with $1\leq i\leq N-1$ and $i+1\leq j\leq N$.

To solve the inverse problem get $j$ from the first equation and put it in $i+1\leq j\leq N$: $$i+1\leq k-N(i-1)+\frac{i(i+1)}2\leq N$$ from which: $$i^2-(2N+1)i+2(N+k-1)\geq 0$$ $$i^2-(2N-1)i+2k\leq 0$$ Solving respect to $i$ gives: $$i\leq\frac{2N+1-\sqrt{4N^2-4N-8k+9}}2\vee i\geq\frac{2N+1+\sqrt{4N^2-4N-8k+9}}2$$ $$\frac{2N-1-\sqrt{4N^2-4N-8k+1}}2\leq i\leq\frac{2N-1+\sqrt{4N^2-4N-8k+1}}2$$ which reduces to $$\frac{2N-1-\sqrt{4N^2-4N-8k+1}}2\leq i\leq\frac{2N+1-\sqrt{4N^2-4N-8k+9}}2$$

For $N=200$ and $k=18241$ we get $i=142$ and $j=194$.

Answer 2

You can compute $k$ by the formula

$$k=N(i-1)-\frac{i(i+1)}{2}+j,$$

for $1 \le i \le N-1$ and $i+1 \le j \le N.$