두 개 이상의 연속된 자연수의 합으로 나타낼 수 없는 자연수를 '특이한 수'라 부르자.
예를 들어, 15 = 7 + 8, 12 = 3 + 4 + 5는 특이한 수가 아니다.
함수 S_k(m) = m + (m+1) + ... + (m+k-1) (k, m은 자연수, k > 1)을 생각하자. 에라토스테네스의 체 알고리즘에서 영감을 얻어 N개의 수 {1, 2, ... N}에 대해 S_2, S_3, ...에 해당되는 수를 차례대로 지워나간다.
1) 수 한 개를 지우는 과정을 한 번의 연산으로 칠 때 (중복 포함), 총 연산의 수를 f(N)이라 하자. f(N) = O(N ⋅ lnN)임을 보여라.
* Big O notation의 정의: 양의 실수 c, M이 존재하여 모든 실수 x ≥ c에 대해 0 ≤ f(x) ≤ M ⋅ g(x)이면, f(x) = O(g(x))라 쓴다.
2) 특이한 수의 필요충분조건을 찾고, 증명하여라.
즉, 특이한 수가 아니면 두 개 이상의 연속된 자연수의 합으로 나타낼 수 있는 방법을 찾고, 특이한 수라면 그럴 수 없음을 보여야 한다.
알고리즘 문제에 가까움
+ TMI
수 n이 지워지는 횟수를 h(n)이라 하자 (즉, 두 개 이상의 연속된 자연수의 합으로 표현 가능한 경우의 수). 1부터 10000까지 h(n)을 계산해보면 다음과 같다.
1)은 n/x 대충 적분해서 n*ln(n)정도 2) 특이한 수인지 판단할 수를 n이라고 둠 연속된 짝수개의 자연수의 합으로 나타낼 수 있는경우: n=len*(x/2) (len은 짝수, x는 홀수)의 꼴로 나타낼 수 있고 이때 n은 (x+1-len)/2부터 (x-1+len)/2까지 전부 더한것과 같음 이 때 (x+1-len)는 0보다 커야 하므로 x가 크고 len이 작은것이 이득임 즉 len=(2^p)*k (k는 홀수)꼴로 나타날 때 len에서 k를 나누고 x에 k를 곱하는것이 좋다는것 따라서 n=(2^p)*x (x는 홀수)꼴로 나타낼 수 있을 때 n=(2^(p+1))*(x/2) 이 때 x+1-2^(p+1)이 0보다 크면 특이한 수가 아님
연속된 홀수개의 자연수의 합으로 나타낼 수 있는경우: n=len*x (len은 홀수, x는 자연수)의 꼴로 나타낼 수 있고 이때 p=(len-1)/2라 할 때 n은 x-p부터 x+p까지 전부 더한것과 같음 이 때 x-p(=x-(len-1)/2)는 0보다 커야 하므로 x가 크고 len이 작은것이 이득임 따라서 len은 n의 가장 작은 홀수 소인수가 되는것이 이득임 (n의 소인수가 2밖에 없다면 불가능) k를 n의 가장 작은 홀수 소인수라고 할 때 x-(k-1)/2가 0보다 크다면 특이한 수가 아님 위에서 특이한 수 아님 판정 받지 못한수들은 모두 특이한 수
1)은 좀 더 tight한 bound를 찾으면 좋지만 그리 설명해도 얼추 맞음 2)는 특이한 수를 매우 단순한 형태의 식으로 표현할 수 있는데, N = 20일 때 문제의 알고리즘대로 직접 숫자 제거하다보면 규칙 쉽게 발견할 수 있음 (사실 첨부한 그림만 봐도 대강 알 수 있긴 함)
설마 n=2^p꼴일 때 특이한수인가
ㅇㅇㅋㅋ 필요충분조건 증명도 해볼만함 N 이하 소수 판별에는 효율적인 알고리즘이지만 간단한 규칙이 존재하는 문제의 경우 별로 쓸모없다는걸 보여주는 예시기도 함
n=(2^p)*k (k는 1보다 큰 홀수)라고 할 때 k가 합성수인 경우: k의 제일 작은 소인수를 x라고 하자 n/x를 중심으로 하는 x개의 연속된 자연수의 합은 n이다 아무튼 된다 k가 소수인 경우: (k-1)/2 < (2^p)인 경우: (2^p)를 중심으로 하는 k개의 연속된 자연수의 합은 n이다 (k+1)/2 > (2^p)인 경우: (k-1)/2과 (k+1)/2를 중심으로 하는 2^(p+1)개의 연속된 자연수의 합은 n이다
따라서 n=2^p 외에는 특이한 수가 없다 연속된 자연수 x개의 평균을 a라고 할 때 그 자연수들의 합은 xa이다 x가 홀수라면 a는 정수이고 xa에는 홀수인 소인수가 들어간다 x가 짝수라면 a는 홀수/2의 꼴이므로 xa에는 홀수인 소인수가 들어간다 홀수인 소인수가 없으니 n=2^p는 항상 특이한 수이다
굿굿 첨언하자면 n = (2^p) * k일 때 k를 합성수 / 소수로 나눌 필요는 없음 나도 (k-1) / 2와 2^p의 대소에 따라 두 가지 경우로 나누어 해를 구하긴 했는데, 이 두 경우 모두 다음의 한 가지 규칙으로 설명할 수도 있음
"2^p를 중심으로 k개의 연속된 정수를 나열하되, 음수는 같은 크기의 양수와 함께 제거한다" ex) 20 = 2² * 5 => 2, 3, 4, 5, 6 ex) 44 = 2² * 11 => -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 => 2, 3, 4, 5, 6, 7, 8, 9