에라토스테네스-신촌우왕 체식
(참조: https://gall.dcinside.com/board/view/?id=mathematics&no=361875 )
다음과 같은
(유한)자연수열을 생각해보자.
N = 21
n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
초항 1을 0으로 바꾼 수열을 f(n)이라 하면
f(n) = 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
f(n)에서 2를 제외하고 2의 배수를 모두 0으로 바꾼 수열을 g(n)이라고 하면
g(n) = 0, 2, 3, 0, 5, 0, 7, 0, 9, 0, 11, 0, 13, 0, 15, 0, 17, 0, 19, 0, 21
g(n)에서 3을 제외하고 3의 배수를 모두 0으로 바꾼 수열을 h(n)이라고 하면
h(n) = 0, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 0
√(21)보다 작거나 같은 소수는 2, 3 이다.
따라서
이쯤 되면
소수는 그대로 있고, 비소수는 0으로 바뀌어 있게 된다.
수열 h(n)을 구할 수 있는가?
있다.
바로
[에라토스테네스-신촌우왕 체식]이다.
(참조: https://gall.dcinside.com/board/view/?id=mathematics&no=361875 )
h(n) = n × τ(n, 1) × ∏_p∈P ω(n, p) = n × τ(n, 1) × ω(n, 2) × ω(n, 3)
p ≤ √N
(p는 소수)
공집합 = Φ = {g | g≠g}
∏g∈Φ g = 1
공집합의 원소를 모두 곱하면 1
다음과 같은 경우
p ≤ √N (p는 소수)을 만족하는 소수 p는 존재하지 않는다.
N = 1
N = 2
N = 3
이 경우
p는 공집합의 원소로 간주될 수도 있다.
따라서 아래 공식은 이제 공집합의 원소들을 대상으로 곱을 구해야 하는 상황을 맞이하게 된다.
h(n) = n × τ(n, 1) × ∏_p∈Φ ω(n, p)
간단히
N = 3인 경우를 생각해보자.
n = 1, 2, 3
f(n) = 0, 2, 3
g(n) = 0, 2, 3
h(n) = 0, 2, 3
즉
h(1) = 0
h(2) = 2
h(3) = 3
h(n) = n × τ(n, 1) × ∏_p∈Φ ω(n, p)
x = y 이면 τ(x, y) = 0
x ≠ y 이면 τ(x, y) = 1
h(1) = 1 × τ(1, 1) × ∏_p∈Φ ω(n, p) = 1 × 0 × ∏_p∈Φ ω(n, p) = 0
h(2) = 2 × τ(2, 1) × ∏_p∈Φ ω(n, p) = 2 × 1 × ∏_p∈Φ ω(n, p) = 2
h(3) = 3 × τ(3, 1) × ∏_p∈Φ ω(n, p) = 3 × 1 × ∏_p∈Φ ω(n, p) = 3
이상의 내용을 종합하면
∏_p∈Φ ω(n, p) = 1
공집합의 원소를 대상으로
어떤 함수 값의 모든 곱을 구하면 1이 되는 경우를 본 셈이다.
◈◈◈◈◈◈
일반적으로
대상으로 하는 함수 ω에 관계없이
공집합의 공원소를 모두 곱하면 1로 본다.
댓글 0