Uživatelské nástroje

Nástroje pro tento web


prog:dok_cisla

Dokonalá čísla

Pro přirozené číslo n ≥ 2 vytvoříme součet všech jeho dělitelů (včetně 1 a čísla samotného) a označíme jej Sn.

  • Pro většinu čísel je Sn < 2n, např. pro 9: 1 + 3 + 9 = 13 < 2.9,
  • méně často platí Sn > 2n, např. pro 24: 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = 60 > 2.24
  • a jen výjimečně nastává Sn = 2n, např. pro 28: 1 + 2 + 4 + 7 + 14 + 28 = 56 = 2.28.

Zajímat nás nyní budou čísla, pro která platí rovnost (tj. nastává třetí případ). Těm se říká dokonalá čísla a zabývali se jimi matematici už v antickém Řecku.

Pomocí počítače budeme hledat dokonalá čísla přímočaře tak, že u každého zkoumaného čísla nalezneme všechny dělitele a jejich součet porovnáme s dvojnásobkem čísla.

Nejprve se budeme zabývat dílčí úlohou, v rámci které určíme součet všech dělitelů zadaného čísla. Vzpomeneme si přitom na úvahy učiněné při hledání prvočísel. Postačuje hledat dělitele menší než odmocnina zadaného čísla a kromě dělitele samotného pak započíst i podíl, který je také dělitelem čísla. Zvlášť musíme ošetřit případ, kdy číslo je druhou mocninou přirozeného čísla, takový dělitel započítáme pouze jednou.

soucet_delitelu.py
# pro zadané číslo vypočte součet všech jeho dělitelů
 
# vstup dat
cislo = int(input('Zadejte přirozené číslo: '))
 
soucet = 1 + cislo # 1 i samotné číslo jsou univerzálními děliteli
delitel = 2
# v cyklu zkoušíme dělitele až do odmocniny
while delitel * delitel < cislo:
    if cislo % delitel == 0:
        # při dělitelnosti přičteme dělitele i podíl (je také dělitelem)
        soucet = soucet + delitel + cislo // delitel
    delitel = delitel + 1 # další dělitel
 
# je-li zadané číslo čtvercem
if delitel * delitel == cislo:
    # přičteme dělitele jenom jednou
    soucet = soucet + delitel
 
# tisk výsledků
print('Součet dělitelů čísla', cislo, 'je', soucet)

Nyní již můžeme v cyklu zkoumat čísla od 2 do určené horní hranice a vypisovat nalezená dokonalá čísla dokonala_cisla.py.

V rozsahu do 100 000 takto relativně rychle nalezneme čtyři čísla: 6, 28, 496, 8128. Zvyšování horní hranice je již nad možnosti našeho programu.

Tato čtyři čísla znali již řečtí matematici. Eukleidés si povšimnul, že všechna lze zapsat ve tvaru 2n-1.(2n - 1) pro n postupně 2, 3, 5, 7. Navíc dokázal, že pokud je člen v závorce pro nějaké n prvočíslem, tak výsledný součin vždy tvoří dokonalé číslo. Číslo ve tvaru 2n - 1 se často nazývá Mersennovým číslem a pro zkoumání jeho prvočíselnosti existují velmi efektivní algoritmy. Pro každé nalezené Mersennovo prvočíslo tedy můžeme vytvořit odpovídající dokonalé číslo. Euler prokázal, že všechna sudá dokonalá čísla musí mít výše uvedený tvar. Každému sudému dokonalému číslu tak odpovídá jedno Mersennovo prvočíslo a naopak. V současné době není známo, zda existují nějaká lichá dokonalá čísla.

prog/dok_cisla.txt · Poslední úprava: 03.11.2017 05:51 autor: Ivana Stefanová

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki