Note that if M is a nilpotent matrix of order n such that rank(M) = r, then M is similar to diag(S_(a_1), S_(a_2), ..., S_(a_(n-r))) for some (a_1, a_2, ..., a_(n-r)), where S_k = (s_ij) is a shift matrix of order k (i.e., s_ij = 1 if j = i+1 and 0 otherwise). Then the nilpotent index of M is l = max{a_1, a_2, ..., a_(n-r)}, so ceiling(n/(n-r)) <= l <= r+1.

On the other hand, if n/(n-r) <= l <= r+1, we're trying to find a nilpotent matrix M of order n whose rank is r and nilpotent index is l. Actually, we only need to find (a_1, a_2, ..., a_(n-r)) such that Sum_{i=1..n-r} a_i = n and max{a_1, a_2, ..., a_(n-r)} = l, then M can be diag(S_(a_1), S_(a_2), ..., S_(a_(n-r))).

If l = ceiling(n/(n-r)), let d = n mod (n-r), then let a_1 = a_2 = ... = a_d = ceiling(n/(n-r)), a_(d+1) = a_(d+2) = ... = a_(n-r) = floor(n/(n-r)). Now suppose we have found (a_1, a_2, ..., a_(n-r)) such that Sum_{i=1..n-r} a_i = n and l = a_1 >= a_2 >= ... >= a_(n-r) >= 1 for some ceiling(n/(n-r)) <= l <= r+1, then there are two cases:

(a) n-r = 1 or a_2 = 1, this gives l = a_1 = n-(n-r-1) = r+1.

(b) a_2 > 1, then l = a_1 < r+1. Suppose a_t is the last term larger than 1, consider (a'_1, a'_2, ..., a'_t, a'_(t+1), a'_(t+2), ..., a'_(n-r)) = ((a_1)+1, a_2, ..., (a_t)-1, a_(t+1), a_(t+2), ..., a_(n-r)), then we have found (a'_1, a'_2, ..., a'_(n-r)) such that Sum_{i=1..n-r} a'_i = n and l+1 = a'_1 >= a'_2 >= ... >= a'_(n-r) >= 1.