Given an integer z<=10^100, find the smallest row of Pascal's triangle that contains z

How can I find an algorithm to solve this problem using C++: given an integer z<=10^100, find the smallest row of Pascal's triangle that contains the number z.

For example if z=6 => result is on the 4th row.

Another way to describe the problem: given integer z<=10^100, find the smallest integer n: exist integer k so that C(k,n) = z.

C(k,n) is combination of n things taken k at a time without repetition

Solution

EDIT This solution needs Logarithmic time, it's O(Log z). Or maybe O( (Log z)^2 ).

Say you are looking for n,k where Binomial(n,k)==z for a given z.

Each row has its largest value in the middle, so starting from n=0 you increase the row number, n, as long as the middle value is smaller than the given number. Actually, 10^100 isn't that big, so before row 340 you find a position n0,k0=n0/2 where the value from the triangle is larger than or equal to z: Binomial(n0,k0)>=z
You walk to the left, i.e. you decrease the column number k, until eventually you find a value smaller than z. If there was a matching value in that row you would have hit it by now. k is not very large, less than 170, so this step won't be executed more often than that and does not present a performance problem.
From here you walk down, increasing n. Here you will find a steadily increasing value of Binomial[n,k]. Continue with 3 until the value gets bigger than or equal to z, then goto 2.

EDIT: This step 3 can loop for a very long time when the row number n is large, so instead of checking each n linearly you can do a binary search for n with Binomial(n,k) >= z > Binomial(n-1,k), then it only needs Log(n) time.

A Python implementation looks like this, C++ is similar but somewhat more cumbersome because you need to use an additional library for arbitrary precision integers:

# Calculate (n-k+1)* ... *n
def getnk( n, k ):
    a = n
    for u in range( n-k+1, n ):
        a = a * u
    return a

# Find n such that Binomial(n,k) >= z and Binomial(n-1,k) < z
def find_n( z, k, n0 ):
    kfactorial = k
    for u in range(2, k):
        kfactorial *= u

    xk = z * kfactorial            

    nk0 = getnk( n0, k )
    n1=n0*2
    nk1 = getnk( n1, k )

    # duplicate n while the value is too small
    while nk1 < xk:
        nk0=nk1
        n0=n1
        n1*=2
        nk1 = getnk( n1, k )
    # do a binary search
    while n1 > n0 + 1:
        n2 = (n0+n1) // 2
        nk2 = getnk( n2, k )
        if nk2 < xk:
            n0 = n2
            nk0 = nk2
        else:
            n1 = n2
            nk1 = nk2

    return n1, nk1 // kfactorial


def find_pos( z ):
    n=0
    k=0
    nk=1

    # start by finding a row where the middle value is bigger than z
    while nk < z:
        # increase n
        n = n + 1
        nk = nk * n // (n-k)
        if nk >= z:
            break
        # increase both n and k
        n = n + 1
        k = k + 1
        nk = nk * n // k

    # check all subsequent rows for a matching value
    while nk != z:
        if nk > z:
            # decrease k
            k = k - 1
            nk = nk * (k+1) // (n-k)
        else:
            # increase n
            # either linearly
            #  n = n + 1
            #  nk = nk * n // (n-k)
            # or using binary search:
            n, nk = find_n( z, k, n )
    return n, k

z = 56476362530291763837811509925185051642180136064700011445902684545741089307844616509330834616
print( find_pos(z) )

It should print

(5864079763474581, 6)