Алгоритм нахождения наименьшего N такого, что N! делится на простое число, возведенное в степень

Существует ли эффективный алгоритм для вычисления наименьшего целого числа N такое, что N! делится на p ^ k, где p - относительно небольшое простое число, а k - очень большое целое число. Другими словами,

factorial(N) mod p^k == 0

Если бы, учитывая N и p, я хотел бы узнать, сколько раз p делится на N !, я бы использовал известную формулу

k = Sum(floor(N/p^i) for i=1,2,...

. Я провел поиск методом грубой силы для малых значений k но этот подход очень быстро разрушается по мере увеличения k, и, похоже, нет шаблона, который я мог бы экстраполировать на большие значения.

Отредактировано 13.06.2011.

Используя предложения, предложенные Файвером и Хаммаром, я использовал квазибинарный поиск для решения проблемы, но не совсем так, как они предлагали. Используя усеченную версию второй формулы выше, я вычислил верхнюю границу N как произведение k и p (используя только первый член). Я использовал 1 как нижнюю границу. Используя классический алгоритм бинарного поиска, я вычислил среднюю точку между этими двумя значениями и вычислил, какое k будет использовать это значение средней точки как N во второй формуле, на этот раз со всеми используемыми терминами.

Если вычисленное k было слишком small, я поправил нижнюю границу и повторил. Слишком большой, я сначала проверил, было ли k, вычисленное в средней точке 1, меньше желаемого k. Если это так, средняя точка была возвращена как ближайшее N. В противном случае я скорректировал верхнюю точку и повторил.

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

Даже при очень больших значениях k (10 или более цифр) этот подход работает со скоростью O (n log (n)).