먼저 n을 소인수 분해했을 때 n = (p1)^a * (p2)^b *....*(p3)^c 이라면,
Sn = (1+p1+..+p1^a) * (1+p2+..p2^b)*...(1+p3+...p3^c) 이다.
Sn 을 그냥 인수분해하면 여러가지 인수의 곱으로 표현할 수 있는데,
Sn=q*r*s = x*y = ... 라고 하자.
q,r,s 또는 x,y 모두가 1+p+p^2+...+p^m 형태로 표현이 가능하다면, 그 때 소인수의 곱이 약수의 합이 Sn을 만족하는 n이 된다.
따라서 Sn을 인수분해하고 각 인수가 1+p+p^2+...+p^m 형태로 표현이 가능한지 확인하면 된다.
이를 위해서
1. q-1을 소인수 분해하여 p를 찾는다.
2. 1에서 찾은 p들에 대해서 q*(p-1)-1 = (1+p+p^2+..+p^m)(p-1) + 1 = p^(m+1) 인지 확인한다.
예를 들어 Sn=42인 n을 찾는다고 하자.
42=6*7=3*14=1*42=2*21 인데, 2의 경우 1+p+p^2+.. 형태로 표현이 되지 않기 때문에 고려할 필요가 없다.
따라서 3,6,7,14,42 에 대해서만 확인해보면 된다.
<q> <q-1> <p> <q*(p-1)+1>
3 2 2 3*(2-1)+1 = 4 = 2^2 ok (3 = 1 + 2^(2-1))
6 5 5 6*(5-1)+1 = 25 = 5^2 ok (6 = 1 + 5^(2-1))
7 6 2,3 7*(2-1)+1 = 8 =2^3 ok (7 = 1 + 2^1 + 2^(3-1))
7*(3-1)+1 = 15 != 3^m reject
14 13 13 14*(13-1)+1 = 169 = 13^2 ok (14 = 1 + 13^(2-1))
42 41 41 42*(41-1)+1 = 1681 = 41^2 ok (42 = 1 + 41^(2-1))
<참고로 (p+1)(p-1)+1 = p^2>
따라서 Sn=42=6*7 = (1+5)(1+2+2^2) => n= 5*2^2 = 20
=3*14 = (1+2)(1+13) => n = 2*13 = 26
=42 = (1+41) => n= 41
결과적으로 Sn=42인 n은 20, 26, 41이다.
작은 수에 대해서는 그냥 노가다로 하는게 더 빠를 것 같지만, 큰 수에 대해서는 위 방법이 유용할 것이다.
마지막으로 정수론에서는 자연수 n의 약수의 합을 Sigma function이라고 정의하는 모양이다. n=250까지 그 형태는 다음과 같다.
태그 : 약수의합
최근 덧글