Найти минимальное число объектов n из которых можно составить C сочетаний по k

первый вариант

тупой перебор от k и до обеда:

import math

k = 100
с = 90548514656103281165404177077484163874504589675413336841320

n = k
while True:
    if math.comb(n, k) == с:
        break
    n += 1

print(n)

в принципе условно быстро работает до некоторых больших чисел

второй вариант

C(n, k) = n! / (n! / (n - k)!)

откуда

n! / (n - k)! = C(n, k) * k!

или

(n - k + 1) *  (n - k + 2) * ... * (n - 1) / n = C(n, k) * k!

Эту запись можно представить как уравнение x k-ой степени:

(x - k + 1) *  (x - k + 2) * ... * (x - 1) / n = C(n, k) * k!

Дальше остаётся только решить ПРИБЛИЖЁННО данное уравнение, после чего перебором проверить n в диапазоне от [x - 1; x + 1]

Например можно градиентный спуск помучить

Недостаток - может поехать точность вычислений с плавающей запятой при решении уравнения сверхвысоких степеней

Давайте я сформулирую задачу более строго. Итак, имеем некоторое значение С, и вопрос ставится так — в какой самой верхней строке треугольника Паскаля встретится это число?

Т.е. нужно найти пару (n,k), для которой число сочетаний из n по k равно C, при этом накладывается условие, чтобы n было минимально.

Я верно понял условие задачи? потому что все написанное далее — для нее.

Вопросов два.

1. Насколько точно должна быть решена задача, и
2. в каком диапазоне значений.

Теоретически у такой задачи (как ее сформулировал я) решение есть всегда, просто хотя бы потому, что

Это — n==C — верхняя граница решения. Нижнюю границу можно оценить, используя формулу Стирлинга, исходя из того, что максимальное число сочетаний при фиксированном n достигается при n=2k.

В принципе, решение относительно n записывается через функцию Ламберта, но это по сути для аналитического решения ничего не дает. Но это уравнение легко решается численно.

А дальше все зависит от пунктов 1 и 2. Если нужно точное решение — то по сути не остается ничего, кроме как перебирать возможные варианты от минимального n, полученного из решения уравнения, и до n == C. Определенную роль может сыграть информация о числе C — например, если оно простое, то, если я не ошибаюсь, ничего не остается, кроме как n==C. Или если оно, например, имеет вид p(p-1)/2 при простом p...

Небольшая оптимизация перебора состоит в том, что считать все k не нужно, можно идти от 1 до момента, когда число сочетаний превысит заданное значение, и, кроме того, можно легко и просто получать значение числа сочетаний из предыдущего:

так что считать страшные факториалы или просто разные значения сочетаний совершенно не нужно, что существенно ускорит вычисления.

Еще — самые лучшие методы могут считать сочетания с использованием встроенного 64-битного значения unsigned long long только до 64 (имею в виду максимальное значение сочетания), так что при таких C достаточно простого перебора. Большие числа будут требовать длинной арифметики и очень большого времени...

Если же точное решение не требуется (а мне кажется, что это именно так), а нужна оценка такого минимального значения n — то решайте численно показанное выше уравнение (кстати, оно отлично решается методом простых итераций).