$k$-th number in $N \times M$ Table Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq  i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in increasing value ?
 A: A really interesting question. I thought that it should be possible to write this in "closed form" - here meaning that it should be possible to compute it in constant time. I did not manage to do so, but still think that it might be possible - maybe based on A000005, A061017, or the derived ones like A006218...
Until someone finds such a closed form: Each value $a$ appears in the matrix when it can be written as $a = i\cdot j$ with $i \leq N$ and $j \leq M$. The idea is now to count the number of divisors $i,j$ of each value $a = 1 ... k$ that satisfy this criterion (the $k$ here is just an upper bound). These numbers will be summed up, until the sum is greater than or equal to $k$. The current $a$ is then the value we have been looking for. 
The asymptotic running time of this should be $\mathcal{O}(kM)$.
Here is the the brute force solution (with sorting) and the solution by counting the divisors, implemented in Java, for those who are interested. 
import java.util.Arrays;

public class KthEntryTest
{
    public static void main(String[] args)
    {
        for (int N=1; N<=10; N++)
        {
            for (int M=1; M<=10; M++)
            {
                for (int k=1; k<=M*N; k++)
                {
                    int resultA = computeBruteForce(N, M, k);
                    int resultB = computeByCount(N, M, k);
                    System.out.println("N="+N+", M="+M+", k="+k+", resultA="+resultA+", resultB="+resultB);
                    if (resultA != resultB)
                    {
                        System.out.println("ERROR!");
                    }
                }
            }
        }
    }

    private static int computeBruteForce(int N, int M, int k)
    {
        int A[][] = new int[N][M];
        for (int i=1; i<=N; i++)
        {
            for (int j=1; j<=M; j++)
            {
                A[i-1][j-1] = i*j;
            }
        }
        int a[] = flatten(A); 
        Arrays.sort(a);
        return a[k-1];
    }


    private static int[] flatten(int A[][])
    {
        int N = A.length;
        int M = A[0].length;
        int result[] = new int[N*M];
        for (int i=0; i<N; i++)
        {
            System.arraycopy(A[i], 0, result, i*M, M);
        }
        return result;
    }

    private static int computeByCount(int N, int M, int k)
    {
        int sum = 0;
        for (int i=1; i<=k; i++)
        {
            int count = 0;
            for (int j=1; j<=M; j++)
            {
                if (i%j == 0)
                {
                    int d = i/j;
                    if (d <= N)
                    {
                        count++;
                    }
                }
            }
            sum += count;
            if (sum >= k)
            {
                return i;
            }
        }
        return -1;
    }
}

A: Interesting Problem :) 
We can solve it using binary search as Ross Milikan indicated. 
The main thing left is to find $n(p)$ which can be done simply in $O(M)$ complexity ,
where 
$$n(p) = \sum_{i=1}^M min(floor(p/i),N)$$
The logic used over here is to find count of elements less than or equal to $p$ in $jth$ column , which will be equivalent to $min(floor(p,i),N)$ . 
This comes from the fact that the number multiples of $i$ less than equal to $p$ is equal to $floor(p,i)$ and we take minimum since a column can contain at maximum $N$ elements.
So , we can solve this in $O(M log (NM))$ .
A: Hint to anyone who has more time than me: it would appear that if $A[i][j]$ is the $k$-th term then the $(k+1)$-th term is a neighbour of $A[i][j]$. In which case it may be possible to do this in $\mathcal{O}(k)$ using a recursive algorithm.

That failing, here's a naive solution:


*

*Construct $\tilde{A}$ which is the upper-left $\min(N,k)\times\min(M,k)$ matrix of $A$.

*Sort $\tilde{A}$ into the single array $B$.

*Quicksort $B$.

*Pick the $k$-th element of ordered $B$.


The bottleneck is the quicksort which is, on average, $\mathcal{O}(NM\log(NM))$. 
A: This is basically selection in a Young's tableaux, and also selection in X+Y sorted SUM matrix (taking $X[i] = Y[i] = \log i$, the sums being $S[i,j] = \log i + \log j$), the latter of which has known $O(M+N)$ time algorithms for selecting the $k^{th}$ largest element.
This paper: Generalize Selection and Ranking: Sorted Matrices has an $O(M+N)$ time algorithm for sorted sums selection.
An explanation of that algorithm (called the FJ-Algorithm, for the initials of the authors of the above paper) can be found in section 2 of this paper: Cache oblivious selection in sorted X+Y matrices.
