Created
September 15, 2019 23:03
-
-
Save codecakes/26f8f7fa6bb71d43acfa74148a9d650a to your computer and use it in GitHub Desktop.
digits in a factorial number result
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # See: https://mathoverflow.net/questions/19170/how-good-is-kamenetskys-formula-for-the-number-of-digits-in-n-factorial/44927#44927 | |
| # See: https://math.stackexchange.com/questions/661227/factorial-length | |
| import math | |
| import functools | |
| _LIMIT = 5*pow(10, 7) | |
| def digitsInFactorial(N: int) -> int: | |
| cache_ln = functools.lru_cache(maxsize=None)(math.log) | |
| cache_log = functools.lru_cache(maxsize=None)(math.log10) | |
| sum_log = functools.lru_cache(maxsize=None)(lambda n: sum(cache_log(i) for i in range(2, n+1))) | |
| fact_exact = lambda n: math.floor(sum_log(n)) + 1 | |
| fact_approx = lambda n: math.floor(((cache_ln(2*math.pi*n)/2)+n*(cache_ln(n)-1))/cache_ln(10))+1 | |
| return fact_approx(N) if N < _LIMIT else fact_exact(N) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment