recover index in triangular for loops

Question

Is there a simple way to recover an index in nested for loops? For example, in for loops which construct Pascals triangle

int index = 0;
for (int i = 0; i < N; ++i)
  for (int j = 0; j < N-i; ++j)
    index++;

is there a way to recover i and j given only index?

Answer 1

I am adding this as a second answer since it is in a different language (now C) and has a more direct approach. I am keeping the original answer since the following code is almost inexplicable without it. I combined my two functions into a single one to cut down on function call overhead. Also, to be 100% sure that it answers the original question, I used the loops from that question verbatim. In the driver function I show explicitly that the output is correct for N = 4 and then stress-test it for N = 10000 (with a total of 100,000,000 passes through the inner loop). I don't have any formal timing code, but it takes about 1 second on my machine to run through and test those 100 million cases. My code assumes a 32-bit int. Change to long if needed:

#include <stdio.h>
#include <math.h>

void from_index(int n, int index, int *i, int *j);

int main(void){
    int N;
    int ri,rj; //recovered i,j
    N = 4;
    int index = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N-i; ++j){
                    from_index(N,index,&ri,&rj);
                    printf("i = %d, j = %d, index = %d, ",i,j,index);
                    printf("recovered i = %d, recovered j = %d\n",ri,rj);
                    index++;
            }

    //stress test:

    N = 10000;
    index = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N-i; ++j){
                    from_index(N,index,&ri,&rj);
                    if(i != ri || j != rj){
                        printf("Don't post buggy code to Stack Overflow!\n");
                        printf("(i,j) = (%d,%d) but recovered indices are (%d,%d)\n",i,j,ri,rj);
                        return 0;
                    }
                    index++;
            }
    printf("\nAll %d tests passed!\n",N*N);
    return 0;
}

void from_index(int n, int index, int *i, int *j){
    double d;
    d = 4*n*(n+1) - 7 - 8 * index;
    *i = floor((-1 + sqrt(d))/2);
    *j = *i * (*i + 1)/2;
    *j = n*(n+1)/2 - 1 - index - *j;
    *j = *i - *j;
    *i = n - *i - 1;   
}

Output:

i = 0, j = 0, index = 0, recovered i = 0, recovered j = 0
i = 0, j = 1, index = 1, recovered i = 0, recovered j = 1
i = 0, j = 2, index = 2, recovered i = 0, recovered j = 2
i = 0, j = 3, index = 3, recovered i = 0, recovered j = 3
i = 1, j = 0, index = 4, recovered i = 1, recovered j = 0
i = 1, j = 1, index = 5, recovered i = 1, recovered j = 1
i = 1, j = 2, index = 6, recovered i = 1, recovered j = 2
i = 2, j = 0, index = 7, recovered i = 2, recovered j = 0
i = 2, j = 1, index = 8, recovered i = 2, recovered j = 1
i = 3, j = 0, index = 9, recovered i = 3, recovered j = 0

All 100000000 tests passed!