Skip to content

Instantly share code, notes, and snippets.

@codecakes
Created September 15, 2019 23:03
Show Gist options
  • Select an option

  • Save codecakes/26f8f7fa6bb71d43acfa74148a9d650a to your computer and use it in GitHub Desktop.

Select an option

Save codecakes/26f8f7fa6bb71d43acfa74148a9d650a to your computer and use it in GitHub Desktop.
digits in a factorial number result
# 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