오일러 토션트 함수
오일러 토션트 함수 (Euler's Totient Function) 는 정수론 함수로, 다음과 같이 정의합니다.
$$
\varphi(n) = \sum_{m = 1}^{n} \left[ \gcd(m, n) = 1 \right]
$$
$\left[ P \right]$는 아이버슨 괄호 , $\gcd(m, n)$는 최대공약수 입니다.
$n$과 서로소 인 $n$ 이하의 자연수 의 개수라는 이야기 입니다. (아이버슨 괄호는 괄호 내의 명제가 참이면 1, 거짓이면 0)
오일러 토션트 함수는 다음과도 동치입니다.
$$
\varphi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right)
$$
이에 의해서 $n$을 나누는 소인수 $p$가 필요하므로 토션트 함수를 구하고자 한다면 소인수분해는 거의 필수입니다.
factorize 함수로 어떻게든 소인수분해를 한 결과를 리스트로 받았다고 치고 (ex. factorize(120) = [2, 2, 2, 3, 5]) 중복을 제거([2, 2, 2, 3, 5] -> [2, 3, 5])하여 토션트 함수를 구하는 파이썬 함수입니다.
소인수분해를 할 수 있는 여러가지 방법이 있기때문에, 소인수분해 함수와 오일러 토션트 함수는 되도록이면 따로 분리를 하는 것을 추천드립니다.
기본적인 소인수분해법 함수와 합치면 다음과 같이 토션트 함수 값을 구할 수 있습니다. 물론, Lehman 소인수분해법이든 폴라드-로 소인수분해법이든 소인수분해는 어떻게든지 구하시면 됩니다.
오일러 피 함수라고 불리기도 합니다.
오일러 토션트 함수의 연속합으로 Totient Summatory Function 가 있습니다.
오일러 토션트 함수의 일반화로 조르당 토션트 함수 가 있습니다.
오일러 토션트와 아주 닮은 함수로 데데킨트 프사이 함수 가 있습니다.