팩토리얼(factorial)의 비밀 - 스털링 근사 공식과 자리수 계산하기

1. 팩토리얼의 자리수

 

$$n! = 1\times2\times...\times n$$로 계산된다.

 

어떤 정수에 1~9까지 중 하나를 곱하면 자리수가 늘어날수도 있지만, 늘어나지 않을수도 있다

 

하지만 10 이상을 곱하면 최소한 1자리는 확실히 늘어난다.

 

이런 통찰에 근거해 10! 이상부터 생각해보면...

 

10! 이상은 이전 팩토리얼에 10 이상의 수가 계속해서 곱해진다는 특징이 있다

 

$$11! = 10! \times 11$$$$12! = 11! \times 12$$$$13! = 12! \times 13$$...

 

그러므로 10! 이상의 팩토리얼은 그 자리수가 유일하게 결정된다.

 

그 말은 팩토리얼의 자리수를 알면, 몇 팩토리얼인지도 계산이 가능하다.

 

 

2. 자리수를 계산하는 방법

 

123의 자리수는 3자리인데 $$123 = 1.23 \times 10^{2}$$이므로, 10에 대한 로그를 취하면

 

$$log_{10} 123 = 2 + log_{10} 1.23 = 2.xxxxx$$

 

12345의 자리수는 5자리인데, $$12345 = 1.2345 \times 10^{4}$$이므로, 10에 대한 로그를 취하면..

 

$$log_{10} 12345 = 4 + log_{10} 1.2345 = 4.xxxx$$

 

...

 

n자리 정수 $a_{1}a_{2}...a_{n}$은 $$a_{1}.a_{2}...a_{n} \times 10^{n-1}$$로 표현이 가능하고,

 

이에 대한 10의 로그를 취하면.. n-1 + 0.xxxx로 계산이 된다.

 

따라서 어떤 정수 m의 자리수 $L_{m}$은...

 

$$L_{m} = int(log_{10} m) + 1$$

 

여기서 int(k)는 파이썬의 int()함수를 의미한다.

 

어떤 실수 k보다 작거나 같은 최대의 정수

 

 

3. 스털링 근사

 

어떤 양의 정수 n에 대해 n!의 근삿값을 구하는 방법

 

일반적으로 알려진 근사 공식은

 

$$n! \approx \sqrt{2\pi n}(\frac{n}{e})^{n}$$

 

n이 4만 되도 오차가 1%라고 한다

 

n이 조금만 커도 사실상 동일한 값일 정도

 

 

4. 구현 예시

 

math 라이브러리를 이용해서 구현할 수 있다

 

그대로 계산할 수도 있고 필요에 따라 로그를 취해서 계산할 수도 있다

 

#stirling formula

import math

def factorial_approximation(n):
    
    return (n/math.e)**(n) * (2*math.pi*n)**(1/2)

#natural log approximation

def log_approximation(n):
    
    return math.log(2*math.pi*n)/2 + n*(math.log(n) - 1)

#10에 대한 log를 취한 스털링 근사
def log_approximation(n):
    
    return math.log10((2*math.pi*n))/2 + n * (math.log10(n)-math.log10(math.e))

 

 

5. 연습문제1

 

13294번: 역팩토리얼 (acmicpc.net)

13294번: 역팩토리얼

 

 

팩토리얼 값 n!이 주어졌을때, n을 구하는 문제

 

 

6. 풀이1

 

n이 10 이상일때는 n!의 자리수가 유일하게 결정된다는 사실을 이용하자

 

$n >= 10$일때, n!의 자리수가 $L_{n}$이라고 한다면...

 

$$L_{n} = log_{10} n!$$

 

그러면.. $(n+1)! = n! \times (n+1)$이므로... $$L_{n+1} = log_{10} (n+1)! = log_{10} n! + log_{10} (n+1) = L_{n} + log_{10} (n+1)$$ 

 

물론 n이 10 미만이면, 특수한 경우로 처리하면 된다

 

10!까지 구하는건 쉬우니까 비교해서 구하면 그만

 

import math
from sys import stdin

factorial = [1]*10
fact_dict = {}

#9!까지 모두 구해놓기

for i in range(1,10):
    
    factorial[i] = factorial[i-1] * i

    fact_dict[factorial[i]] = i

n = stdin.readline().rstrip()

n_digit = len(n)

n = int(n)

value = fact_dict.get(n,-1)

#들어온 값이 9! 이내의 값이라면...
if value != -1:
    
    print(value)

#9!이내의 값이 아니라면..
else:
    
    #n >= 10의 log n!값 저장
    digit_list = [0]*(1000001)

    k = factorial[-1]*10
    
    digit = math.log10(k)
    
    #10!의 로그 값을 구해놓고 저장
    digit_list[10] = digit
    
    #입력의 자리수와 비교해서 일치하면 인덱스를 출력
    if n_digit == int(digit)+1:
        
        print(10)
    
    else:

        for i in range(11,1000000):
            
            #L(k+1) = L(k) + log10(k+1) 점화식으로 구하기
            digit_list[i] = digit_list[i-1] + math.log10(i)

            if n_digit == int(digit_list[i]) + 1:
                
                break
        
        print(i)

 

 

7. 풀이2

 

int() 함수가 시간복잡도가 $O(n^{2})$이라는 소리가 있더라

 

int()만 사용 안해봤거든? 그런데 5000ms 걸리던 풀이가 120ms정도 걸리더라

 

문자열 길이가 매우 크면... 단순한 int()함수도 신중하게 사용해야겠다

 

import math
from sys import stdin

factorial = [1]*10
fact_dict = {}

for i in range(1,10):
    
    factorial[i] = factorial[i-1] * i

    fact_dict[str(factorial[i])] = i

n = stdin.readline().rstrip()

n_digit = len(n)

value = fact_dict.get(n,-1)

if value != -1:
    
    print(value)

else:
    
    digit_list = [0]*(1000001)

    k = factorial[-1]*10
    
    digit = math.log10(k)

    digit_list[10] = digit

    if n_digit == int(digit)+1:
        
        print(10)
    
    else:

        for i in range(11,1000000):
            
            digit_list[i] = digit_list[i-1] + math.log10(i)

            if n_digit == int(digit_list[i]) + 1:
                
                break
        
        print(i)

 

 

8. 풀이3

 

조금 더 깔끔하게...

 

10!부터 자리수가 확실하게 변한다고 할 수 있는데

 

사실 1!부터 계산해보면

 

6! = 720까지는 규칙이 없는데 7!부터는 자리수가 계속 달라진다

 

그래서 6! = 720까지는 계산해놓고 7!부터 10에 대한 로그를 계산해서 자리수를 구해서 비교해본다.

 

import math
from sys import stdin

fact_dict = {}

fact_dict = {'1':1, '2':2, '6':3, '24':4, '120':5, '720':6}

n = stdin.readline().rstrip()

n_digit = len(n)

value = fact_dict.get(n,-1)

#입력이 6! 이내의 값이라면..
if value != -1:
    
    print(value)

else:
    
    #7!부터는 자리수가 유일하게 결정된다.
    digit = math.log10(5040)
    
    i = 7
    
    while 1:
        
        if n_digit == int(digit) + 1:
            
            break
        
        else:
            
            digit += math.log10(i+1)
            
            i += 1
    
    print(i)

 

 

9. 연습문제2

 

7894번: 큰 수 (acmicpc.net)

7894번: 큰 수

 

 

n!의 자리수를 계산하는 문제

 

 

10. 풀이

 

n이 $10^{7}$까지라서, 당연히 n!을 그냥 계산하면 시간 초과다

 

그리고 위에서 구한 로그를 이용한 자리수 점화식 쓸려고 해도 $10^{7}$ 배열 만들면 메모리 초과로 통과를 못함

 

그래서 스털링의 근사 공식을 이용해서 n!의 근삿값을 구하자.

 

이때, n!의 자리수는 위에서 배운대로

 

10에 대한 로그를 취하고 int()함수를 취한 뒤에 1을 더하면 구할 수 있다는 점을 이용하자

 

import math
from sys import stdin

#10에 대한 log를 취한 스털링 근사
def log_approximation(n):
    
    return math.log10((2*math.pi*n))/2 + n * (math.log10(n)-math.log10(math.e))

t = int(stdin.readline())

for _ in range(t):
    
    m = int(stdin.readline())

    print(int(log_approximation(m))+1)

 

 

참조

 

 

스털링 근사, Stirling Formula (tistory.com)

스털링 근사, Stirling Formula