솟수 공식

[재후]

솟수 공식

δ(x, y)의 값: x, y가 같으면 1, 다르면 0

τ(x, y)의 값: x, y가 같으면 0, 다르면 1

r(b, a)의 값: b를 a로 나눈 나머지

<에라토스테네스의 체>에 대한 공식은

곧바로

솟수 공식이 되는 것입니다.

이를테면

1부터 24까지 솟수에 대한 

솟수 공식은

다음과 같습니다.

root(24) ≒ 4.9 이므로

4 이하의 솟수인

2 및 3을 동원하면

1부터 24까지

솟수 공식을 다음과 같이 구성할 수 있습니다.

1부터 24까지 솟수 공식:

P(n) = n×τ(n, 1)×{ δ(n, 2) + τ(r(n, 2), 0) }×{ δ(n, 3) + τ(r(n, 3), 0) }

( P(n)=n이면 n은 솟수입니다. )

혹은

유효한 n의 범위를 표시하여

P(1≤n≤24) = n×τ(n, 1)×{ δ(n, 2) + τ(r(n, 2), 0) }×{ δ(n, 3) + τ(r(n, 3), 0) }

1은 솟수도 합성수도 아니므로

제외시키면

τ(n, 1) = 1 이므로

다음과 같이 유효한 n의 범위에서 1을 제외시킬 수 있습니다.

P(2≤n≤24) = n×{ δ(n, 2) + τ(r(n, 2), 0) }×{ δ(n, 3) + τ(r(n, 3), 0) }

만약 검사하고자 하는 n의 값이

동원된 솟수 2 및 3보다 크다면

P(3<n≤24) = n×τ(r(n, 2), 0)×τ(r(n, 3), 0)

---

p(23)의 값을 계산해보겠습니다.

p(23)

=

p(1≤23≤24)

=

23×τ(23, 1)×{ δ(23, 2) + τ(r(23, 2), 0) }×{ δ(23, 3) + τ(r(23, 3), 0) }

=

23×1×{ 0 + τ(1, 0) }×{ 0 + τ(2, 0) }

=

23×1×{ 0 + 1 }×{ 0 + 1 }

=

23

p(23) = 23 이므로

23은 솟수입니다.

---

1부터 120까지 솟수 공식:

root(120) ≒ 10.??? 이므로

10 이하의 솟수인 2, 3, 5를 이용하여

솟수 공식을 구성할 수 있습니다.

p(1≤n≤120) = n×τ(n, 1)×{δ(n, 2)+τ(r(n, 2), 0)}×{δ(n, 3)+τ(r(n, 3), 0)×{δ(n, 3)+τ(r(n, 5), 0)}

( p(n)=n이면 n은 솟수입니다. )

혹은

p(2≤n≤120) = n×{δ(n, 2)+τ(r(n, 2), 0)}×{δ(n, 3)+τ(r(n, 3), 0)×{δ(n, 3)+τ(r(n, 5), 0)}

( p(n)=n이면 n은 솟수입니다. )

혹은

테스트할 n의 값이

동원된 솟수 2, 3, 5 보다 크다면

p(5<n≤120) = n×τ(r(n, 2), 0)×τ(r(n, 3), 0)×τ(r(n, 5), 0)

( p(n)=n이면 n은 솟수입니다. )

위의 솟수 공식을 사용하여

87과 97을 살펴보겠습니다.

---

p(87)

=

p(5<87≤120)

=

87×τ(r(87, 2), 0)×τ(r(87, 3), 0)×τ(r(87, 5), 0)

=

87×τ(1, 0)×τ(0, 0)×τ(2, 0)

=

87×τ(1, 0)×0×τ(2, 0)

=

0

따라서

P(87)=0은 솟수가 아닙니다.

---

p(97)

=

p(5<97≤120)

=

97×τ(r(97, 2), 0)×τ(r(97, 3), 0)×τ(r(97, 5), 0)

=

97×τ(1, 0)×τ(1, 0)×τ(2, 0)

=

97×1×1×1

=

97

따라서

P(97)=97은 솟수입니다.

---

ω(b, a)의 새로운 정의

나머지 함수와 타우 함수를 결합한 형태는 약간 복잡한 형태이므로

새로운 오메가 함수를 다음과 같이 정의하겠습니다.

ω(b, a)의 값:

b를 a로 나눈 나머지가 0이면 0, 그렇지 않으면 1

그러면

τ(r(b, a), 0) = ω(b, a)

따라서

솟수 공식은 다음과 같이 바꿔 쓸 수 있습니다.

---

1부터 24까지 솟수 공식:

P(1≤n≤24) = n×τ(n, 1)×{ δ(n, 2) + ω(n, 2) }×{ δ(n, 3) + ω(n, 3) }

P(2≤n≤24) = n×{ δ(n, 2) + ω(n, 2) }×{ δ(n, 3) + ω(n, 3) }

P(3<n≤24) = n×ω(n, 2)×ω(n, 3)

( P(n)=n이면 n은 솟수입니다. )

---

1부터 120까지 솟수 공식:

P(1≤n≤120) = n×τ(n, 1)×{ δ(n, 2) + ω(n, 2) }×{ δ(n, 3) + ω(n, 3)×{ δ(n, 3) + ω(n, 5) }

P(2≤n≤120) = n×{ δ(n, 2) + ω(n, 2) }×{ δ(n, 3) + ω(n, 3)×{ δ(n, 3) + ω(n, 5) }

P(5<n≤120) = n×ω(n, 2)×ω(n, 3)×ω(n, 5)

( P(n)=n이면 n은 솟수입니다. )

---

동원된 솟수는

이미 솟수임을 알고 있기 때문에

세 번 째 공식을 주로 사용하는 것이 좋을 듯 싶습니다.

그러면...

동원된 솟수보다 크고

동원되지 않은 최소 솟수의 제곱보다 작은 범위에서의

안전한 솟수 공식이 됩니다.

혹은...

동원된 솟수보다 크고

발견될 최소 솟수의 제곱보다 작은 범위에서의

안전한 솟수 공식이 됩니다.

즉

4부터 24까지 솟수 공식:

P(3<n≤24) = n×ω(n, 2)×ω(n, 3)

( P(n)=n이면 n은 솟수입니다. )

6부터 120까지 솟수 공식:

P(5<n≤120) = n×ω(n, 2)×ω(n, 3)×ω(n, 5)

( P(n)=n이면 n은 솟수입니다. )