find the smallest integer N, such that

Question

I am stuck for quite a while now on the following task:

find the smallest integer N, such that A^N < N!

I want to do this in C# and A can be so big that there is no type that can store the results. I also know that this can be solved without actually calculating A^N and N! but I have absolutely no clue how to do this...

Answer 1

To avoid checking all possible values of N, you can estimate it's value using Stirling's approximation

A^N < N!
ln(A^N) < ln(N!)
N*ln(A) < N*ln(N) - N + some small addition
ln(A) < ln(N) - 1 + some small addition
ln(A)+1 < ln(N)
ln(A*e) < ln(N)
N > A*e

So get initial value of N = A*e (Math.E in c#), and you need to check rather small range of N's to find exact value