Here is more optimized PR inspired by PR 29020. It would be too long to explain how PR 29020 can be improved, so I write a new PR.

Basically it implements Raymond's idea #1, but supports n>62 for smaller k.

How to calculate limits:

import math
n = m = 2**64
k = 1
while True:
    nmax = int(math.ceil((m * math.factorial(k-1)) ** (1/k) + (k-1)/2)) + 100
    n = min(n, nmax)
    while math.comb(n, k) * k >= m:
        n -= 1
    if n < 2*k: break
    print(k, n)
    k += 1