고합성수

고합성수(Highly composite number)는 어떤 자연수가 존재해서 자기 자신보다 작은 어떤 수보다 약수가 많은 수를 일컫는다. 1과 자기자신만을 약수로 갖는 소수의 안티체제라 할 수 있다.

12를 예로 들면 약수는 6개이고, 그 밑으로는 모두 약수가 6개보다 적으므로 12는 고합성수이다. 18도 약수가 6개이지만 12가 더 작기에 18은 고합성수가 아니다.

특징

[math]\displaystyle{ p_k }[/math]를 [math]\displaystyle{ k }[/math]번째 소수라 하고, 어떤 자연수가 [math]\displaystyle{ N=p_1^{e_1} \cdot p_2^{e_2} \cdot \cdots p_n^{e_n} }[/math]과 같이 소인수분해가 된다고 하면, 약수의 개수는 [math]\displaystyle{ d(N)=(e_1+1)(e_2+1) \cdots (e_n+1) }[/math]이다. 즉 각 소인수의 지수에서 1을 더한 값들의 곱이 되므로, [math]\displaystyle{ (e_1, e_2, \cdots e_n) }[/math]의 항들을 순서만 섞어서 자연수를 새로 지정하더라도 약수의 개수는 변하지 않는다.

• 진술: [math]\displaystyle{ N }[/math]이 고합성수이기 위한 필요조건은 [math]\displaystyle{ e_1 \geq e_2 \geq \cdots \geq e_n }[/math]인 것이다. 즉 소인수가 커질수록 지수는 이전 항과 같거나 작아져야 한다.
• 증명: [math]\displaystyle{ N }[/math]의 소인수 중 [math]\displaystyle{ e_r\lt e_s, p_r\lt p_s }[/math]인 두 인덱스 [math]\displaystyle{ r, s }[/math]가 존재한다고 하자. 주어진 자연수를 [math]\displaystyle{ N=Mp_r^{e_r}p_s^{e_s} }[/math]과 같이 쓰고, 지수를 맞바꾼 [math]\displaystyle{ N'=Mp_r^{e_s}p_s^{e_r} }[/math]을 불러온다. 그러면 [math]\displaystyle{ \frac{N'}{N}=\left(\frac{p_r}{p_s}\right)^{e_s-e_r}\lt 1 }[/math]이므로 [math]\displaystyle{ N'\lt N }[/math]이다. 그런데 [math]\displaystyle{ d(N)=d(N') }[/math]이므로, [math]\displaystyle{ N }[/math]은 고합성수가 될 수 없다.
• 따름정리: 고합성수는 소수 계승의 곱으로 표현할 수 있다. (예: [math]\displaystyle{ 120=(2\text{#})^2 \cdot 5\text{#} = 2^2 \cdot 30 }[/math])

참고로 고합성수의 정의에서는 자연수가 반드시 합성수여야 한다는 조건은 들어가 있지 않다. 그렇기에 1, 2도 고합성수에 포함된다. 물론 그 이상은 모두 합성수이다.

목록

아래 표는 가장 작은 고합성수 25개를 나열한 것이다. (OEIS의 수열 A002182)

순번	고합성수	소인수분해	약수의 개수
1	1		1
2	2		2
3	4	[math]\displaystyle{ 2^2 }[/math]	3
4	6	[math]\displaystyle{ 2 \cdot 3 }[/math]	4
5	12	[math]\displaystyle{ 2^2 \cdot 3 }[/math]	6
6	24	[math]\displaystyle{ 2^3 \cdot 3 }[/math]	8
7	36	[math]\displaystyle{ 2^2 \cdot 3^2 }[/math]	9
8	48	[math]\displaystyle{ 2^4 \cdot 3 }[/math]	10
9	60	[math]\displaystyle{ 2^2 \cdot 3 \cdot 5 }[/math]	12
10	120	[math]\displaystyle{ 2^3 \cdot 3 \cdot 5 }[/math]	16
11	180	[math]\displaystyle{ 2^2 \cdot 3^2 \cdot 5 }[/math]	18
12	240	[math]\displaystyle{ 2^4 \cdot 3 \cdot 5 }[/math]	20
13	360	[math]\displaystyle{ 2^3 \cdot 3^2 \cdot 5 }[/math]	24
14	720	[math]\displaystyle{ 2^4 \cdot 3^2 \cdot 5 }[/math]	30
15	840	[math]\displaystyle{ 2^3 \cdot 3 \cdot 5 \cdot 7 }[/math]	32
16	1260	[math]\displaystyle{ 2^2 \cdot 3^2 \cdot 5 \cdot 7 }[/math]	36
17	1680	[math]\displaystyle{ 2^4 \cdot 3 \cdot 5 \cdot 7 }[/math]	40
18	2520	[math]\displaystyle{ 2^3 \cdot 3^2 \cdot 5 \cdot 7 }[/math]	48
19	5040	[math]\displaystyle{ 2^4 \cdot 3^2 \cdot 5 \cdot 7 }[/math]	60
20	7560	[math]\displaystyle{ 2^3 \cdot 3^3 \cdot 5 \cdot 7 }[/math]	64
21	10080	[math]\displaystyle{ 2^5 \cdot 3^2 \cdot 5 \cdot 7 }[/math]	72
22	15120	[math]\displaystyle{ 2^4 \cdot 3^3 \cdot 5 \cdot 7 }[/math]	80
23	20160	[math]\displaystyle{ 2^6 \cdot 3^2 \cdot 5 \cdot 7 }[/math]	84
24	25200	[math]\displaystyle{ 2^4 \cdot 3^2 \cdot 5^2 \cdot 7 }[/math]	90
25	27720	[math]\displaystyle{ 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 }[/math]	96