Seskupení přirozených čísel do n/2 vzájemně nesoudělných skupin

Seskupování přirozených čísel do dvojic nesoudělných čísel

Rozdělení posloupnosti {1, 2, 3, ..., n} na n/2 skupin, kde jsou všechna čísla uvnitř každé skupiny navzájem nesoudělná, lze dosáhnout pomocí jednoduchého algoritmu. Prvočísla a 1 jsou umístěna do první skupiny. Sudá čísla >2 tvoří startovní prvky zbývajících skupin. Lichá složená čísla jsou rozdělena podle vzorce pos_{x_i} = ⌊x_i/4 + 0,5⌋. Tím je zajištěno, že největší společný dělitel každého lichého čísla se sudým vedoucím skupiny je 1.

Logika rozdělení

Algoritmus se opírá o vlastnosti lichých složených čísel: všechna mají tvar 4k ± 1 pro nějaké k. Zde k odpovídá číslu skupiny. Pro sudého vedoucího skupiny 2k platí gcd(2k, 4k ± 1) = 1, protože 4k ± 1 ≡ ±1 (mod 2k).

První skupina obsahuje:

• 1
• Všechna prvočísla

Zbývající skupiny (k ≥ 2):

• První pozice: sudé číslo 2k
• Druhá pozice (volitelně): lichá složená čísla x, kde pos_x = k

Některé skupiny mohou obsahovat 0 nebo 2 lichá čísla (příklady: k=3,7 — prázdné; k=14,16 — po dvou).

Příklad pro n=24

Tabulka ukazuje rozdělení:

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

| Skupina 2 | 4, 9, 15, 21 |

| Skupina 3 | 6 |

| Skupina 4 | 8, 25? (pro n=24: 8) |

| ... | ... |

Ověření vzájemné nesoudělnosti uvnitř skupin je potvrzeno vlastnostmi: prvočísla jsou po dvojicích nesoudělná, gcd(2k, 4k±1)=1.

Matematické zdůvodnění

• Prvočísla: Libovolná dvě prvočísla p, q (p ≠ q) mají gcd(p,q)=1.
• Sudí vedoucí: 2k s k≥2 je liché, ale 2k je sudé.
• Lichá složená: x = 4k ±1, gcd(2k, x) = gcd(2k, ±1 mod 2k) =1.
• Mezi lichými ve skupině: Možné dvojice (vzácně) jsou také nesoudělné podle konstrukce, protože jsou rozděleny podle modulu.

To vyplývá z Dirichletovy věty o prvočíslech v aritmetických posloupnostech nepřímo, ale přímo — z tvaru lichých čísel.

Implementace v Pythonu

Pro automatizaci rozdělení:

def group_naturals(n):
    primes = [1]  # 1 + prvočísla
    composites_odd = []
    evens = []
    
    for i in range(2, n+1):
        if i % 2 == 0:
            evens.append(i)
        elif is_prime(i):
            primes.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]  # ořízneme přebytečné

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

Kód generuje skupiny pro dané n a ověřuje vlastnosti.

Co je důležité

• Všechny skupiny obsahují pouze navzájem nesoudělná čísla.
• Počet skupin je přesně n/2 pro jakékoli přirozené n.
• Lichá složená čísla jsou rozdělena podle pos = ⌊x/4 + 0,5⌋.
• Zdůvodnění: x=4k±1 ⇒ gcd(2k, x)=1.
• První skupina — 1 a všechna prvočísla.

— Editorial Team