약수의 합이 짝수인지 홀수인지 바로 알 수 있을까?(시그마 함수의 성질 + 제곱수의 개수 바로 구하기)

1. 문제

 

11692번: 시그마 함수 (acmicpc.net)

11692번: 시그마 함수

 

 

2. 약수의 합의 성질 - 언제 짝수이고 언제 홀수가 될 수 있는가?

 

정수 n의 모든 양의 약수의 합을 시그마 함수(sigma function)라고 부르는데 일반적인 정의로...

 

$$\sigma_{z}(n) = \sum_{d | n} d^{z}$$

 

z = 1이면 모든 양의 약수의 합을 나타내고 z = 0이면 n의 약수의 개수를 나타낸다.

 

편의상 지금부터 서술하는 모든 시그마 함수는 z = 1인 경우이다.

 

https://en.wikipedia.org/wiki/Divisor_function

Divisor function - Wikipedia

 

2-1) n이 2의 거듭제곱이면 $\sigma(n)$은 홀수이다.

 

n이 2의 거듭제곱이라는 것은 $\sigma(n) = (1+2+2^{2}+...+2^{k})$

 

그런데 홀수 + 짝수 = 홀수이다.

 

1 + 2 = 3 = 홀수

 

3 + 4 = 7 = 홀수

 

7 + 8 = 15 = 홀수

 

...

 

수학적 귀납법으로 정확히 증명할 수 있다.

 

k = 0이면 1 = 홀수

 

k = m에서 $\sigma(n)$이 홀수라면... k = m+1에서는?

 

$1 + 2 + 2^{2} + ... + 2^{m}$이 홀수이고 $2^{m+1}$은 짝수이므로... 홀수 + 짝수 = 홀수니까..

 

k = m+1에서도 홀수이다.

 

그러므로 n이 2의 거듭제곱이면, $\sigma(n)$은 홀수가 된다.

 

2-2) 2가 아닌 소수 p와 짝수 k에 대하여 $n = p^{k}$이면 $\sigma(n)$은 홀수이다.

 

마찬가지로 $\sigma(n) = (1 + p + p^{2} + ... + p^{k})$

 

2가 아닌 소수 p는 모두 홀수이다.

 

그런데 홀수 + 홀수 = 짝수이고 홀수 + 짝수 = 홀수이며 홀수 * 홀수 = 홀수이다.

 

그러니까 $\sigma(n)$은 홀수를 k + 1번 더하는 것이다.

 

k = 2이면 홀수 + 홀수 + 홀수 = 홀수

 

모든 짝수 k = m에서 $\sigma(n)$이 홀수라고 한다면, 여기에 홀수를 2번 더하면 그대로 홀수이므로

 

k = m + 2에서도 $\sigma(n)$은 홀수이다.

 

그러므로 2가 아닌 소수 p와 짝수 k에 대하여 $n = p^{k}$이면 $\sigma(n)$은 홀수이다.

 

비슷한 이유로 k가 홀수이면, $\sigma(n)$은 짝수가 된다. 

 

2-3) fundamental theorem of arithmetic

 

1보다 큰 모든 정수는 유일한 소인수분해를 가진다. 증명은 생략함... 언젠가 해볼기회가 있을려나

 

https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

Fundamental theorem of arithmetic - Wikipedia

 

 

2-4) sigma function is multiplicative

 

두 정수 a,b가 서로소이면 $$\sigma(ab) = \sigma(a)\sigma(b)$$

 

사실 너무나 당연한 결과이다.

 

a,b가 서로소라는 것은 a,b의 소인수분해가 각각 서로 다른 소인수를 가지고

 

$$a = p_{a_{1}}^{k_{1}}p_{a_{2}}^{k_{2}}...$$

 

$$b = p_{b_{1}}^{x_{1}}p_{b_{2}}^{x_{2}}...$$

 

$$ab = p_{a_{1}}^{k_{1}}p_{a_{2}}^{k_{2}}...p_{b_{1}}^{x_{1}}p_{b_{2}}^{x_{2}}...$$

 

 

a,b의 약수의 합은..

 

$$\sigma(a) = (1+p_{a_{1}}+p_{a_{1}}^{2}+...+p_{a_{1}}^{k_{1}})(1+p_{a_{2}}+p_{a_{2}}^{2}+...+p_{a_{2}}^{k_{2}})...$$

 

$$\sigma(b) = (1+p_{b_{1}}+p_{b_{1}}^{2}+...+p_{b_{1}}^{x_{1}})(1+p_{b_{2}}+p_{b_{2}}^{2}+...+p_{b_{2}}^{x_{2}})...$$

 

따라서 ab의 약수의 합은 두 시그마의 곱으로 나타난다.

 

$$\sigma(ab) = (1+p_{a_{1}}+p_{a_{1}}^{2}+...+p_{a_{1}}^{k_{1}})...(1+p_{b_{1}}+p_{b_{1}}^{2}+...p_{b_{1}}^{x_{1}})... = \sigma(a)\sigma(b)$$

 

 

2-5) $\sigma(n)$이 홀수이면 n은 2의 거듭제곱과 2가 아닌 소수의 짝수지수 거듭제곱의 곱으로 나타난다.

 

2는 유일한 짝수 소수이며 2보다 큰 모든 소수는 홀수라는 것은 잘 알려져있다.

 

여기에 모든 정수 n이 유일한 소인수분해를 가지므로 n은 다음과 같이 4가지 경우로 나뉘어진다.

 

1) 2의 거듭제곱 x

 

2) 2가 아닌 소수 p의 짝수지수 거듭제곱 y

 

3) 2가 아닌 소수 p의 홀수지수 거듭제곱 z

 

4) 1),2),3)으로 나타난 수 x,y,z들의 곱

 

2-1)에 의해 $\sigma(x)$는 홀수이고 2-2)에 의해 $\sigma(y)$는 홀수이며 $\sigma(z)$는 짝수이다.

 

홀수와 짝수를 곱해보면 다음과 같은 관계를 얻는다.

 

짝수 * 짝수 = 짝수

 

짝수 * 홀수 = 짝수

 

홀수 * 홀수 = 홀수

 

즉 모든 요소가 홀수여야 이들의 곱이 홀수일 수 있다.

 

2-4)에 의해 $\sigma(n)$이 홀수라는 것은 x,y들만의 곱으로 나타나야한다. 

 

즉, $\sigma(n)$이 홀수이면, n은 2의 거듭제곱과 2가 아닌 소수의 짝수지수 거듭제곱의 곱으로 나타난다.

 

 

2-6) 음이 아닌 정수 k와 자연수 p에 대하여 $n = 2^{k}p^{2}$으로 표현되면 $\sigma(n)$은 홀수이다.

 

2-3)에 의해 정수 n이 유일한 소인수분해를 가지므로.. $p_{1} \leq p_{2} ... \leq p_{m}$이라 가정하고

 

$$n = p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{m}^{k_{m}}$$

 

모든 소수들은 서로소이므로.. 2-4)에 의해

 

$$\sigma(n) = \sigma(p_{1}^{k_{1}})\sigma(p_{2}^{k_{2}})...\sigma(p_{m}^{k_{m}})$$

 

그런데 짝수와 홀수를 곱해보면 다음을 알 수 있다.

 

짝수 * 짝수 = 짝수

 

짝수 * 홀수 = 짝수

 

홀수 * 홀수 = 홀수

 

그러므로 $\sigma(n)$이 홀수일려면, 모든 요소가 홀수여야한다. 

 

즉, 모든 i = 1,2,...,m에 대하여 $\sigma(p_{i}^{k_{i}})$가 홀수이다.

 

따라서 $\sigma(n)$이 홀수일려면, 2-1), 2-2)에 의해 n의 소인수분해가 2의 거듭제곱 * 소수의 짝수 거듭제곱 형태이다.

 

즉, $p_{i} = 2$이거나 $p_{i} > 2$라면, $k_{i}$가 짝수이다.

 

$p_{i} > 2$에서 $k_{i}$가 짝수라는 것은

 

$$p_{i}^{k_{i}} = (p_{i}^{k_{i}/2})^{2} = p^{2}$$을 만족하는 정수 $p$가 존재하는 것이다.

 

그러므로 자연수 k,p에 대해 $n = 2^{k}p^{2}$으로 표현된다면, p를 소인수분해하여, 

 

$$n = 2^{k}(p_{0}^{k_{0}}p_{1}^{k_{1}}...p_{m}^{k_{m}})^{2} = 2^{x}p_{1}^{2k_{1}}p_{2}^{2k_{2}}...p_{m}^{2k_{m}}$$

 

으로 2의 거듭제곱과 홀수인 소수 $p_{i}$의 짝수지수 거듭제곱의 곱으로 나타난다.

 

그러므로 2-2), 2-3), 2-4)에 의해 $\sigma(n)$은 홀수이다. 

 

2-5), 2-6)에 의해 다음과 같다.

 

$\sigma(n)$이 홀수일 필요충분조건은 음이 아닌 정수 k와 자연수 p에 대하여 $n = 2^{k}p^{2}$으로 표현되는 것이다.

 

만약 k가 짝수이면.. $n = ((2^{k/2})p)^{2} = m^{2}$으로 표현할 수 있으므로 n은 완전제곱수이다. 

 

만약 k가 홀수이면.. k-1이 짝수이므로 $n = 2*(2^{(k-1)/2}p)^{2} = 2*m^{2}$으로 표현할 수 있으므로 n은 완전제곱수의 2배이다.

 

 

3. 풀이

 

문제에서 요구하는 것은 1부터 m이하의 모든 자연수 n에 대하여 $\sigma(n)$이 짝수인 n의 개수

 

$\sigma(n)$이 홀수일 필요충분조건을 유도했으니

 

전체 n의 개수 - $\sigma(n)$이 홀수인 n의 개수 = $\sigma(n)$이 짝수인 n의 개수로 구한다.

 

$\sigma(n)$이 홀수인 경우는

 

1) n이 제곱수인 경우

 

2) n이 제곱수의 2배인 경우

 

먼저 m이하의 모든 자연수에서 제곱수의 개수는 어떻게 구할 수 있을까?

 

1부터 m까지 하나하나 순회해서 제곱수인지 판단해봐야할까?

 

m이 최악의 경우 10의 12승이라 1초안에 안돌아간다

 

예를 들어 생각해보자.

 

m = 9이면 1,4,9로 3개

 

m = 10부터 15까지도 여전히 3개

 

m = 16이면 1,4,9,16으로 4개

 

m = 16 ~ 24까지도 여전히 4개

 

m = 25이면 1,4,9,16,25로 5개..

 

1,4,9,16,25,36,...$k^{2}$까지 $m = k^{2}$에서야 최초로 k개가 된다.

 

그 이후로 $m = (k+1)^{2} - 1$까지는 여전히 k개이다.

 

즉 m이하의 자연수에서 제곱수의 개수는 $\sqrt{m}$개로 바로 유도할 수 있다.

 

비슷하게 m이하의 자연수에서 제곱수의 2배인 경우의 개수는...

 

m = 2이면 2*1로 1개

 

m = 8이면 2*1, 2*4로 2개

 

m = 18이면 2*1, 2*4, 2*9로 3개

 

...

 

$m = 2*k^{2}$이면 2*1,2*4,2*9,...,$2*k^{2}$으로 최초로 k개

 

바꿔말하면... $m/2 = k^{2}$이면 최초로 k개

 

m/2에서 제곱수의 개수를 세면 된다. 즉, $\sqrt{m/2}$개로 바로 유도할 수 있다.

 

m = int(input())

print(m - int(m**(1/2)) - int((m//2)**(1/2)))

 

 

 

https://math.stackexchange.com/questions/301151/how-to-find-how-many-number-has-even-value-of-sigma-function%EF%BB%BF

How to find how many number has even value of sigma function?

 

https://math.stackexchange.com/questions/345016/when-the-sum-of-all-divisors-of-a-natural-number-is-odd%EF%BB%BF

When the sum of all divisors of a natural number is odd