n/2 쌍별 서로소 그룹으로 자연수 그룹화

자연수를 서로소 쌍으로 그룹화하기

수열 {1, 2, 3, ..., n}을 n/2개의 그룹으로 나누어 각 그룹 내 모든 숫자가 서로소가 되도록 하는 것은 간단한 알고리즘으로 가능합니다. 소수와 1은 첫 번째 그룹에 배치됩니다. 2보다 큰 짝수는 나머지 그룹의 시작 요소를 형성합니다. 홀수 합성수는 공식 pos_{x_i} = ⌊x_i/4 + 0.5⌋를 사용하여 분배됩니다. 이를 통해 각 홀수와 짝수 그룹 리더의 최대공약수가 1이 됩니다.

분배 논리

이 알고리즘은 홀수 합성수의 성질에 의존합니다: 모든 홀수 합성수는 어떤 k에 대해 4k ± 1 형태를 가집니다. 여기서 k는 그룹 번호에 해당합니다. 짝수 그룹 리더 2k에 대해, gcd(2k, 4k ± 1) = 1입니다. 왜냐하면 4k ± 1 ≡ ±1 (mod 2k)이기 때문입니다.

첫 번째 그룹에는 다음이 포함됩니다:

• 1
• 모든 소수

나머지 그룹 (k ≥ 2):

• 첫 번째 위치: 짝수 2k
• 두 번째 위치 (선택적): pos_x = k인 홀수 합성수 x

일부 그룹은 0개 또는 2개의 홀수를 포함할 수 있습니다 (예: k=3,7 — 비어 있음; k=14,16 — 각각 두 개).

n=24 예시

분배를 보여주는 표:

| 그룹 1 | 1, 2, 3, 5, 7, 11, 13, 17, 19, 23 |

| 그룹 2 | 4, 9 |

| 그룹 3 | 6 |

| 그룹 4 | 8, 15 |

| ... | ... |

그룹 내 서로소 여부는 다음 성질로 확인됩니다: 소수는 쌍별로 서로소이며, gcd(2k, 4k±1)=1입니다.

수학적 근거

• 소수: 임의의 두 소수 p, q (p ≠ q)는 gcd(p,q)=1입니다.
• 짝수 리더: k≥2인 2k는 짝수입니다.
• 홀수 합성수: x = 4k ±1, gcd(2k, x) = gcd(2k, ±1 mod 2k) =1.
• 그룹 내 홀수 간: 가능한 쌍(드물게)도 구성에 의해 서로소입니다. 왜냐하면 모듈로 분배되기 때문입니다.

이는 디리클레의 등차수열 내 소수 정리에서 간접적으로 따르지만, 홀수 형태에서 직접적으로 도출됩니다.

파이썬 구현

분할을 자동화하기 위한 코드:

def group_naturals(n):
    primes = [1]  # 1 + 소수
    composites_odd = []
    evens = []
    
    for i in range(2, n+1):
        if is_prime(i):
            primes.append(i)
        elif i % 2 == 0:
            evens.append(i)
        else:
            composites_odd.append(i)
    
    groups = [primes]
    pos = {}
    for x in composites_odd:
        k = int(x / 4 + 0.5)
        if k not in pos:
            pos[k] = []
        pos[k].append(x)
    
    for k in range(2, n//2 +1):
        group = [2*k]
        if k in pos:
            group.extend(sorted(pos[k]))
        groups.append(group)
    
    return groups[:n//2]  # 초과분 제거

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True

이 코드는 주어진 n에 대한 그룹을 생성하며, 성질을 검증합니다.

핵심 포인트

• 모든 그룹은 서로소 숫자만 포함합니다.
• 그룹 수는 자연수 n에 대해 정확히 n/2입니다.
• 홀수 합성수는 pos = ⌊x/4 + 0.5⌋로 분배됩니다.
• 근거: x=4k±1 ⇒ gcd(2k, x)=1.
• 첫 번째 그룹: 1과 모든 소수.

— Editorial Team