sport komputerowo-matematyczny

[guru_ji]

W następnych postach poruszę konkretne problemy, tak że będziecie mogli zakasać rękawy i
główkować i rachować. W tej nocie dam wprowadzenie bardzo ogólne.

W różnych działach matematyki, w szczególności w kombinatoryce, teorii liczb i geometrii, pytamy o
o pewne parametry, powiedzmy o ciąg a(1) a(2) ...., których naukowcy i hobbyści nie są w stanie w
danym momencie policzyć. Następuje wtedy mnije lub bardziej intensywny wyścig, którego celem
jest dokładne policzenie nowej, dotąd nieznanej wartości, powiedzmy a(6), lub podanie lepszego
(ściślejszego) jej oszacowania, typu 66 < a(6) < 82.

W ostatnich latach polscy studenci informatyki fantastycznie spisują się na najważniejszych,
światowych zawodach w programowaniu. Natomiast polska obecność na listach światowych rekordów
w sportach komputerowo-matematycznych jest znikoma i oficjalnie ograniczona chyba do jednego
jedynego Stanisława P. Radziszowskiego, Profesora na wydziale Computer Science Instytutu
Technologii w Rochester (NY), który jest jednym z tych, którzy mają największy wkład do konkretnej,
klasycznej Teorii Ramsey'a. W szczególności, prowadzi on w Internecie stronę rekordów Teorii
Ramsey'a:

www.cs.rit.edu/~spr/ElJC/eline.html
Interesuje się on też Teorią Konfiguracji

[Gość: w++]

guru_ji napisał:

> ..e. kody poprawiające błędy (!)

Właśnie. Intryguje mnie, co w tej dziedzinie, może bardziej w zastosowaniach, ciekawego się teraz dokonuje. Przyznam że moje doświadczenia w tej materii nie wychodziły poza zwykłego Hamminga, ale jestem świadomy że to niezwykle teraz ważna dziedzina praktycznych zastowań matematyki. A to, zdaje się, Twój szczególny obiekt zainteresowań.

[guru_ji]

Gość portalu: w++ napisał(a):

> guru_ji napisał:
>
> > ..e. kody poprawiające błędy (!)
>
> Właśnie. Intryguje mnie, co w tej dziedzinie,
> może bardziej w zastosowaniach,
> ciekawego się teraz dokonuje.

Nie jestem specjalistą, nie śledzę postępu

[Gość: w++]

guru_ji napisał:

> W tym wątku też chcę znaleźć miejsce dla ECC (Error Correcting Codes), tyle że
> tutaj można pisać w
> sposób nieco bardziej zaawansowany, obliczony na zajmowanie się "rekordami".

Nie za bardzo w tej chwili mogę jakoś wyobrazić tą "sportową" rywalizację w tej dziedzinie.

> Li
> czę na uczestników,
> których nie odstraszą formuły ani rachunki, lecz raczej przyciągną.

Hmm.. Muszę, troche z żalem, uprzedzić, że jestem, niestety głównie praktykiem i bardziej mnie pociąga np. skuteczność gotowych algorytmów niż elegancja teorii na bazie której się opierają.

> PS. Podoba mi się Twój nick, w++, ładne.

Może i ładny ale całkiem nieprzydatny do logowania się :(

[guru_ji]

Gość portalu: w++ napisał:

> Nie za bardzo w tej chwili mogę jakoś
> wyobrazić tą "sportową" rywalizację w
> tej dziedzinie.

Popatrz:

www.research.att.com/~njas/codes/And/
oraz

www.research.att.com/~njas/codes/Andw/
Pozdrawiam,

guru_ji

PS. Otworzę nowy wątek dla ogólnej dyskusji kodów poprawiających błędy.

[Gość: w++]

Mam małe pytanie, a nie chcę zaburzać toku Twego wykładu więc piszę tutaj.
Skąd się bierze zaklasyfikowanie liczb doskonałych jako Brq_2. Nie rozumiem te k we wzorze sd(n) = k*n. Zauważyłem że w innych źródłach też wartością klasy, czyli Twojego piętra dla doskonałych jest również 2.

Tak na marginesie. Ponieważ nic nie słyszałem przedtem o tych liczbach i nie miałem pojęcia jaki mają rozkład, chciałem je sobie po prostu zobaczyć. Napisałem mały programik i zleciłem mojemu komputerowi by mi ich trochę znalazł z definicji. Co było wynikiem, doskonale wiesz. Komputer nawet długo nie myśląc wypluł 8 liczb, z tego 4 doskonałe i dalej męczył się już bez powodzenia. Sprawdziłem później w internecie, no i faktycznie, nie jest to na pewno dziedzina, w której metody siłowe mają sensowne zastosowanie. Za to coraz bardziej rozumiem sensowność dyscyplin sportowych z ich udziałem.

[Gość: w++]

Gość portalu: w++ napisał(a):

> Skąd się bierze zaklasyfikowanie liczb doskonałych jako Brq_2.

Już widzę co przeoczyłem. Pomyliłem po prostu sumę dzielników (Twoje sd() ) z sumą dzielników właściwych (w definicji l. doskonałej ) różniących się o wartość n.
Ok. Już nie zawracam głowy.

[guru_ji]

Gość portalu: w++ napisał(a):

> Mam małe pytanie, a nie chcę zaburzać
> toku Twego wykładu więc piszę tutaj.

Zawsze i wszędzie przyjemnie jest
czytać merytoryczne posty.

> Skąd się bierze zaklasyfikowanie liczb doskonałych
> jako Brq_2. Nie rozumiem te k we wzorze sd(n) = k*n.
> Zauważyłem że w innych źródłach też wartością klasy,
> czyli Twojego piętra dla doskonałych jest również 2.

Liczby pierwsze są ważne, obiektywnie. Liczby doskonałe wydają się być
błahostką, choć problemy z nimi związane, to już inna sprawa. Czyli liczby
doskonałe służą za pretekst do badania liczb naturalnych, liczb pierwszych,
funkcji liczbowych, itp.

Historycznie, definiowano liczby doskonałe jako równe sumie swoich dzielników
**właściwych**, czyli mniejszych od nich samych. Symbolicznie powinniśmy w tym
kontekście mieć funkcje sdw(n), oznaczającą Sumę Dzielników Właściwych liczby n.
Wtedy doskonałość n oznaczałaby równość sdw(n) = n. Byłoby prościej, jakby
bardziej elegancko. A jednak matematycy nie zajmują się sdw(n), tylko pokrewną
funkcją sd(n), będacą sumą **wszystkich** dzielników liczby n. Oczywiście sd(n)
= sdw(n) + n, oraz doskonałość n oznaqcza sd(n) = 2*n, jakby brzydziej.

Chodzi o to, że funkcja sd(n) ma ważną strukturalną własność:

jeżeli liczby naturalne a b mają tylko 1 jako wspólny dzielnik, to:

sd(a*b) = sd(a)*sd(b)

Mówimy, że funkcja sd, jak szereg innych funkcji podstawowych dla teorii liczb,
jest multiplikatywna. Funkcja sdw(n) czymś takim nie może się pochwalić.

Z tego właśnie (obiektywnego!) powodu używamy sd, a nie sdw. Z pomocą sd łatwiej
formułować i dowodzić twierdzeń, niż używając sdw.

> Tak na marginesie. Ponieważ nic nie słyszałem
> przedtem o tych liczbach i nie miałem pojęcia
> jaki mają rozkład, chciałem je sobie po prostu
> zobaczyć. Napisałem mały programik i zleciłem
> mojemu komputerowi by mi ich trochę znalazł z
> definicji. Co było wynikiem, doskonale wiesz.

:-) I tak ma sens pisanie takich programów na rozgrzewkę, raczej prostych, dla
motywacji, dla przyjemności, którą sprawia materialny, konkretny kontakt z
zagadnieniem matematycznym, jakby z przyrodą, fizyką czy inżynierią.

> Komputer nawet długo nie myśląc wypluł
> 8 liczb, z tego 4 doskonałe i dalej męczył
> się już bez powodzenia. Sprawdziłem później
> w internecie, no i faktycznie, nie jest to
> na pewno dziedzina, w której metody siłowe
> mają sensowne zastosowanie. Za to coraz bardziej
> rozumiem sensowność dyscyplin sportowych z ich
> udziałem.

Przede wszystkim liczy się matematyczny algorytm.
Od tego zależy najwięcej. Opierają sie takie algorytmy
na obserwacjach i głębokich twierdzeniach matematycznych.
Następnie liczy się czysto algorytmiczny aspekt wykonania
algorytmu na nieco bardziej detalicznym poziomie, ale
raczej już niezależnym od głębszej matematyki. Pomaga
nawet wyczucie języka komputerowego i wręcz architektury
komputera. Wreszcie liczy się teź szybkośc samego
języka komputerowego, kompilera czy innego wykonania języka
i szybkość samego komputera. Gdy w teorii liczb mamy do
czynienia ze sporuyymi liczbami, to na przykład 64-bitowy
komputer ma wyraźną przewagę nad 32-bitowym, z powodu
szybkości i z powodu łatwości programowania. O wiele
szybciej operuje się na 40-bitowych liczbach całkowitych,
gdy architektura jest 64-bitowa, i wolniej, gdy 32 bitowa,
gdy liczba wewnątrz komputera jest rozbita na dwie części
(to tak dla przykładu).

W kombinatoryce, wejściowe parametry mogą być małe, może od 1 do 15, ale
parametry indukowane mogą wybuchać eksponencjalnie albo jeszcze szybciej!

Dziękuję za uwagi i zainteresowanie, pozdrawiam,

guru_ji

PS. Chyba napiszę trochę o tym co wiadomo o liczbach barokowych (oficjalnie
nazywają się wielo-doskonałe, ale wolę własną nazwę :-) i o nieparzystych
liczbach doskonałych. Postaram się podać ich historię, choćby w skrócie.
Wspaniałym źródłem informacji jest 3-tomowa "Historia Teorii Liczb" Leonarda
Eugene Dicksona. Zamierzam z niej skorzystać oraz z jeszcze jednego źródła.

[guru_ji]

W zakresie Teorii Liczb zaproponowałem następujące polowania na rekordy:

> 2. Teoria Liczb
>
> ..a. nowe wielkie liczby pierwsze (naj-największe, bliźniaki, ...)
> ..b. rozkłady pierwsze liczb losowych, Fermata, Mersenne'a, itp.
> ..c. szacowanie nieparzystej liczby doskonałej
> ......(i) szacowanie od dołu (od góry?!!) wartości n.l. doskonałej
> ......(ii) szacowanie od dołu liczby czynników pierwszych n.l. doskonałej
> ......(iii) inne oszacowania dzielników pierwszych n.l.doskonałej
> ..d. polowania na liczby zaprzyjaźnione, itp.

Dodam:

..e. liczby barokowe (które wprowadzę poniżej)
..f. hipoteza abc (!!!)

O niezwykle ważnej hipotezie abc, szeroko uogólniającej t.zw. Ostatnie Twierdzenie Fermata (zwane
też "Wielkim", a udowodnione głównie przez Wilesa), napiszę osobno.

Teraz wprowadzę liczby barokowe i podam dwa niestandardowe przyklady.

Liczbę naturalną n nazywam barokową, gdy suma sd(n) jej wszystkich dzielników jest jej
wielokrotnością, sd(n) = k*n, gdzie k jest liczbą naturalną. Liczbę k nazywam piętrem ("floor") liczby
barokowej n. Zbiór wszystkich liczb barokowych z piętra k oznaczam przez Brq_k. Tak więc BRq_2 to
zbiór liczb doskonałych. Ponadto:

Brq_1 = {1}

Na początek podam przykłady z piętra 3 i 4, które dojrzałem gołym okiem:

120 \in Brq(3)

30240 = 2^5 * 3^3 * 5 * 7 \in Brq_4

Ciekawe dla jakie piętra k mają choćby jedną liczbę? Czy istnieje największe takie piętro? (Innymi słowy,
które piętra barokowe Brq_k są niepuste?)

Które piętra barokowe Brq_n są skończone? Wszystkie?

Będziemy mieć dużo zabawy, a przy okazji nauczymy się czegoś o liczbach naruralnych

Pytania barokowe /Re: sport komp.-matematyczny

[guru_ji]

guru_ji napisał:

> jakie piętra k mają choćby jedną liczbę?
> Czy istnieje największe ta
> kie piętro? (Innymi słowy,
> które piętra barokowe Brq_k są niepuste?)
>
> Które piętra barokowe Brq_n są skończone? Wszystkie?

Piętro drugie, czyli zbiór liczb doskonałych, ma dobrą szansę być nieskończonym.
Lepiej jednak sformułuję pytania ogólniej.

Niech sd(n) oznacza sumę dzielników liczby naturalnej n. Niech

brq(n) := sd(n) / n

UWAGA Przedtem, w wątku obok, używałem oznaczenia prf(n), a na pl.sci.matematyka
nawet perf(n). Wolę jednak tę wielkość nazywać współczynnikiem barokowości niż
doskonałości. Teraz jest logiczniej.

Pytam o strukturę funkcji

brq : {1 2 ...} --> Q \cap [1;oo)

ze zbioru liczb naturalnych w zbiór liczb wymiernych niemniejszych od 1. W
szczególności:

Liczby barokowe

[guru_ji]

Mają długą i bogatą historię, którą może
opiszę oddzielnie. Nazywają je klasycznie
brzydziej: liczby krotnie-doskonałe lub
wielo-doskonałe ("multiply perfect" u
Dicksona

[guru_ji]

guru_ji napisał:

> TWIERDZENIE 3 Liczba barokowa
> ============= b := p^k * q^m * r^n,
> gdzie b > 1 oraz p < q < r są liczbami
> pierwszymi, spełnia następujące warunki:
>
> (i) p=2, q=3;
>
> (ii) k > 2.
>
> PRZYKŁAD Liczba b := 2^3 * 3 * 5 = 120
> ======== jest najmniejszą liczbą prawdziwie
> barokową: brq(120) = 3.

Zachodzi też:

TWIERDZENIE Jedyną liczbą b := 2^k*3^m*5^n,
=========== spełniającą równość brq(b) = 3,
jest b=120.

DOWÓD
=====

Wiemy, że k>/3, m >/ 1, n >/ 1. Równość
brq(b) zachodzi dla k=3, m=1, n=1. Dla
każdego innego barokowego b danej postaci
mielibyśmy (k m n) > (3 1 1), skąd
braq(b) > brq(120) = 3.

KONIEC DOWODU

UWAGA (notacja) (k m n) > (k' m' n') oznacza,
że k >/ k' oraz m > m' oraz n > n' oraz jedna
z tych trzech nierówności jest ostra.

guru_ji

Suma dzielników, wspołczynnik barokowy, asceza

[guru_ji]

Własności funkcji sd(n) i brq(n) tu podane przydadzą się w następnych postach.

NOTACJA:

litery k m n będą oznaczać liczby naturalne; litery p q

[guru_ji]

guru_ji napisał:

> (-10-) sd(p^k) = 1 mod p
>
> (-11-) sd(p^k) = k+1 mod 2 dla p =/= 2
>
> Następna własność wymaga wstępu: zachodzi n^2=1 mod 8 dla nieparzystych n (dla
> parzystych n mamy n^2 = 0 mod 4, ale to dla nas tutaj nieważne). W wyrażeniu:
>
> sd(p^n) = 1 + p + ... + p^n
>
> co drugi składnik (parzyste potęgi) jest kwadratem. Zatem dla p =/= 2
> zachodzi:
>
> p^k = 1 mod 8 dla k parzystego
> p^k = p mod 8 dla k nieparzystego
>
> Niech PARZ(n) będzie liczba liczb parzystych w zakresie 0..n, oraz
> NIEP(n)

tylko liczby pierwsze są ascetyczne

[guru_ji]

Powiedzmy, że:

<*> brq(n) = (p+1)/p

dla pewnej liczby pierwszej p. Wtedy p|n, gdyż p występuje w mianowniku brq(n).
Gdyby jednak n = p*m dla pewnego m > 1, to zaszłaby nierówność

brq(n) > brq(p) = (p+1)/p

wbrew nierówności <*>. Zatem n=p. Dowiodłem więc, żer zachodzi:

TWIERDZENIE 1. Dla dowolnej liczby pierwszej p, jedyną liczba naturalną n, dla
k†órej brq(n) = (p+1)/p jest n=p.

Popatrzmy teraz, co się dzieje gdy

<**> brq(n) = (k+1)/k

gdzie k jest liczbą złożoną: k = p*m dla pewnej liczby pierwszej p, oraz
naturalnej m > 1. Ale wtedy

brq(n) > brq(p) = (p+1)/p > (k+1)/k

w sprzeczności z <**>. Zatem równośc <**> jest dla złożonego k niemożliwa. Stąd:

TWIERDZENIE 2 Jedynie liczby pierwsze są barokowe.

Hej, to było łatwe, czyli w żargonie matematycznym "trywialne" :-)

guru_ji

[guru_ji]

W tytule jest dobrze. Natomiast
wewnątrz postu znowu się przejęzyczyłem"

> TWIERDZENIE 2 Jedynie liczby pierwsze są barokowe.

Miało by:

TWIERDZENIE 2 Jedynie liczby pierwsze są ascetyczne.

Pozdrawiam,

guru_ji

brq(p^k) mod 8 /Re: ... wspołczynnik barokowy...

[guru_ji]

guru_ji napisał:

> dla p =/= 2 zachodzi:
>
> p^k = 1 mod 8 dla k parzystego
> p^k = p mod 8 dla k nieparzystego

Chodzi o liczbę pierwszą p.

> Niech PARZ(n) będzie liczba liczb parzystych
> w zakresie 0..n, oraz
> NIEP(n)

nieparzyste liczby doskonałe

[guru_ji]

WSTĘP

Pójdę dalej niż w moim wątku forumowym "Twierdzenie Fermata o dwóch kwadratach",
który zawiera moje posty także o liczbach doskonałych (niestety, po łajdacku
s/paskudzi/ł mi tamten wątek niejaki dwojako w nim podpisujący się Robakks =
pies_na_teorie). Więcej niż we wspomnianym wątku podałem swojego czasu na
pl.hum.matematyka. Wszystko jedno te wyniki o nieparzystych liczbach
doskonałych, to tylko mały ułamek tego co wiadomo, zarówno matematycznie jak i
"sportowo". Wszystko jedno piszę na ten temat, gdyż chodzi o najstarszy bodajże,
problem naukowy, nierozwiązany od około dwóch i pół tysiącleci.

Niech sd(n) będzie sumą dzielników liczby naturalnej n. Na przykład sd(6) =
1+2+3+6 = 12. Niech barokowy współczynnik liczby n będzie zdeiniowany tak:

brq(n) := sd(n)/n

Na przykład brq(6) = 2. Liczba naturalną n nazywamy doskonałą, gdy brq(n) = 2.
Zatem 6 jest doskonałe.

Będę korzystał z własności funkcji sd oraz brq podanych obok, w tym wątku.

***

PARZYSTOŚĆ CZYNNIKÓW sd(p^k) LICZBY sd(n)

Niech n będzie nieparzystą liczbą doskonałą. Ponieważ brq(n) = 2, a mianowniki
liczb brq(p^k), gdzie liczby pierwsze p dzielą n, są nieparzyste, to istnieje
dokładnie jeden dzielnik pierwszy p liczby n, taki że sd(p^k) jest parzyste,
gdzie k jest największym wykładnikiem dla którego p^k |n.

Co więcej, dla takiego p^k, liczba 4 nie jest dzielnikiem sd(p^k).

Wynika stąd, że takie p=1 mod 4 oraz k=1 lub 5 mod 8. Jest tak głównie na mocy
równości z tego wątku (-14-), podczas gdy nieparzystośc k wynika z (-11-) (także
z (-13-).


***

NIEDOSKONAŁOŚĆ POTĘGI LICZBY PIERWSZEJ

brq(p^k) < 2

dla dowolnej liczby pierwszej p. Zatem liczba doskonała nigdy nie jest potęgą
liczby pierwszej.

***

NIEDOSKONAŁOŚĆ ILOCZYNU DWÓCH POTĘG NIEPARZYSTYCH LICZB PIERWSZYCH

Niech 2 < p < q będą dwoma różnymi liczbami pierwszymi. Wtedy p >/ 3 oraz q >/
5. Zatem:

brq(p^k * q^n) = brq(p^k) * brq(q^n) \<

brq(3^k) * brq(5^n) < (3/2) * (5/4) = 15/8 < 2

Widzimy, że liczba p^k * q^n nie jest doskonała.

***

ILOCZYN TRZECH POTĘG NIEPARZYSTYCH LICZB PIERWSZYCH

Niech 2 < p < q < r będą trzema liczbami pierwszymi. Jeżeli

n := p^k * q^m * r^n

jest doskonałe, to:

2 = brq(n) \<

brq(p^k) * brq(q^m) * brq(r^n) <

(3/2)*(5/4)*r/(r-1) = (15/8)*r/(r-1)

Stąd

r/(r-1) > 16/15

czyli

r < 16.

Ponieważ r jest liczbą pierwszą > 5, to r=7 lub 11 lub 13.

***

Gdyby q > 5, to mielibyśmy:

brq(n) \< brq(3^k) * brq(7^m) * brq(11^m)

< (3/2)*(7/6)*(11/10) = 77/40 < 2

A więc n nie byłoby doskonałę. Wynika stąd, że jeżeli

n := p^k * q^m * r^n,

dla pierwszych r > q > p > 2, jest doskonałe, to

p=3 oraz q=5 oraz r=7 lub 11 lub 13.

***

PRZYPADEK p=3,q=5,r=7

Niech n := 3^k * 5^m * 7^n będzie doskonałe. Na mocy paragrafu "Parzystość
Czynników..." (zaraz po Wstępie powyżej), dokładnie jeden z wykładników k m n
jest nieparzysty, i jest nim wykładnik m, podczas gdy k r muszą być parzyste.
Nawet wiemy, że m=1 lub 5 mod 8.

Ponieważ mianowniku brq(n) jest podzielny przez 5, to 5 jest dzielnikiem sd(3^k)
lub sd(7^n). Ale ciagi potęg 3 (odpowiednio 7) są mod 5 okresowe, i łatwo
sprawdzić, że:

5 | 3^j - 1 <==> 4 | j

Ponieważ 5 | sd(3^k) oznaczałoby, że

5 | 2*sd(3^k) = 3^(k+1) - 1

to k musiałoby być nieparzyste, sprzeczność. Zatem 5 nie jest dzielnikiem sd(3^k).

Podobnie:

5 | 7^j <==> 4 | j

skąd znowu 5 nie może być dzielnikiem sd(7^n). Widzimy, że n nie jest liczbą
doskonałą.

***

Dla produktów trzech potęg liczb pierwszych pozostały tylko dwa wypadki:

(p q r) = (3 5 11) oraz (3 5 13)

Tyle na teraz,

guru_ji

--

zima na mej twarzy. (wh)

przypadek 3 liczb/Re: nieparzyste liczby doskonałe

[guru_ji]

guru_ji napisał:

> PARZYSTOŚĆ CZYNNIKÓW sd(p^k) LICZBY sd(n)
>
> Niech n będzie nieparzystą liczbą doskonałą.
> Ponieważ brq(n) = 2, a mianowniki liczb brq(p^k),
> gdzie liczby pierwsze p dzielą n, są nieparzyste,
> to istnieje dokładnie jeden dzielnik pierwszy p
> liczby n, taki że sd(p^k) jest parzyste, gdzie k
> jest największym wykładnikiem dla którego p^k |n.
>
> Co więcej, dla takiego p^k, liczba 4 nie jest
> dzielnikiem sd(p^k).
>
> Wynika stąd, że takie p=1 mod 4 oraz k=1 lub 5 mod 8.

Czyli takie k=1 mod 4. Euler to wszystko
odkrył daaawno temu :-)

Ponadto:

> Dla produktów trzech potęg liczb pierwszych
> pozostały tylko dwa wypadki:
>
> (p q r) = (3 5 11) oraz (3 5 13)

PRZYPADEK p=3, q=5, r=11

Wtedy dla liczby doskonałej

n := 3^k * 5^m * 11^n

wykładniki k n są parzyste, a wykładnik m
jest nieparzysty. Jak we poprzedniej nocie,
5 nie jest dzielnikiem liczby sd(3^k), ani
(oczywiście) liczby sd(5^m). Doskonałośc n
oznacza równość:

sd(3^k)*sd(5^m)*sd(11^n) = 2*3^k * 5^m * 11^n

Zatem 5 jest dzielnikiem sd(11^n).

Ponieważ 11=1 mod 5, to 11^j=1 mod 5,
więc sd(11^n) = n+1 mod 5, skąd 5 jest
dzielnikiem n+1, a więc sd(11^4) jest
dzielnikiem sd(11^n), i ostatecznie:

sd(11^4) | 2*n

Ale sd(11^4) = 5*3221, gdzie 3221 jest
liczbą pierwszą. Ponieważ 3221 nie jest
dzielnikiem liczby 2*n, to otrzymaliśmy
sprzeczność. Wynika stąd, że n := 3^k*5^m*11^n
nie może by liczbą doskonałą.

PRZYPADEK p=3, q=5, r=13

Doskonałość liczby

n := 3^k * 5^m * 13^n

oznacza:

sd(3^k)*sd(5^m)*sd(13^n) = 2*n

Ponieważ, jak poprzednio, 5 nie jest
dzielnikiem sd(3^k) ani sd(5^m), to
jest dzielnikiem sd(13^n), gdzie

sd(13^n) = (13^(n+1) - 1) / 12

zatem 5 | 13^(n+1) - 1, skąd 4|n+1.
Stąd sd(13^3) | sd(13^n), a więc sd(13^3) | 2*n.

Ale:

sd(13^3) = 1+13+13^2+13^3 = 14*(1+169) = 4*5*7*17

Poniewa≈ 2*n nie dzieli si´przez 7 (ani przez 17),
to dostaliśmy sprzeczność

gsum, itd. / Re: nieparzyste liczby doskonałe

[guru_ji]

Litery p q r będą oznaczać liczby pierwsze;
litery a b c d k m n

gsum, itd. / Re: nieparzyste liczby doskonałe

[robakks]

guru_ji napisał:

> Zatem liczba d jednak nie może być doskonała.
>
> ***
>
> Tyle na teraz,
>
> guru_ji
>
>

gsum, itd. / Re: nieparzyste liczby doskonałe

[mamusiu]

robakks napisał:

> guru_ji napisał:
>
> > Zatem liczba d jednak nie może być doskonała.
> >
> > ***
> >
> > Tyle na teraz,
> >
> > guru_ji
> >
> >

gsum, itd. / Re: nieparzyste liczby doskonałe

[robakks]

mamusiu napisała:
| robakks napisał:
|| guru_ji napisał:

||| Zatem liczba d jednak nie może być doskonała.
|||
||| ***
|||
||| Tyle na teraz,
|||
||| guru_ji
|||
|||

gsum, itd. / Re: nieparzyste liczby doskonałe

[guru_ji]

guru_ji napisał:

> Popatrzmy na nld postaci:
>
> d := 3^j * 5^k * 7^m * 19^n
>
> gdzie j k m n są liczbami naturalnymi (więc > 0).
> [...] liczba d jednak nie może być doskonała.

Możemy łatwo(!) pokazać o wiele więcej:

TWIERDZENIE Nie istnieje liczba doskonała
=========== d podzielna przez 3*5*7

DOWÓD

Liczba podzielna przez 3*5*7 nie jest
parzystą (euklidesową) liczbą doskonałą
na mocy twierdzenia Eulera.

Gdyby d była nld, to wiemy, że 3 i 7
wystąpiłyby w niej z parzystymi, a więc
równymi co najmniej 2, wykładnikami.
Stąd:

brq(d) >/ brq(3^2)*brq(5)*brq(7^2)

= (13/9)*(6/5)*(57/49) = 2 * 247/245 > 2

Skoro brq(d) > 2, to d nie jest doskonałe.

KONIEC DOWODU

***

guru_ji

Twierdzenie k+1 | n+1 ==> sd(p^(k+1) | sd(p^(n+1)

[guru_ji]

Zdefiniowałem:

gsum(x; d, n) := 1 + x^d + ... + x^((n-1)*d)

i podałem:

TWIERDZENIE 1

gsum(x; 1, a*b) = gsum(x; 1, a) * gsum(x; a, b)


Przypominam, że sd(n) jest sumą wszystkich
dzielników liczby n. W szczególności:

sd(p^n) = gsum(p; 1, n+1)

dla dowolnej liczby pierwszej p.

Zatem z Twierdzenia 1 natychmiast
wynika:

TWIERDZENIE 2

k+1 | n+1 ==> sd(p^(k+1) | sd(p^(n+1)

gdzie znowu p jest dowolną liczbą pierwszą.

***

Twierdzenie 2 będę intensywnie wykorzystywał
w następnych notkach bijących nasze lokalne
rekordy dotyczące nieparzystych liczb
doskonałych (nld).

Pozdrawiam,

guru_ji

liczby doskonałe, podzielne przez 3*5

[guru_ji]

Jest to raczej najważniejszy przypadek
badania nieparzystych liczb doskonałych
(nld).

Będę korzystał z poprzedniego postu:

> TWIERDZENIE 2
>
> k+1 | n+1 ==> sd(p^(k+1) | sd(p^(n+1)
>
> gdzie znowu p jest dowolną liczbą pierwszą.

Tak więc niech

d := 3^k * 5^m * ...

będzie nld, podzielną przez 3*5 (t.zn. k m > 0);
innymi słowy:

brq(d) = brq(3^k) * brq(5^m) * ... = 2

Wiemy z poprzedniej dyskusji, że

(O) Poza 3 5 istnieją co najmniej dwa inne,
różne dzielniki pierwsze liczby d.

(I) k jest parzyste.

(II) 7 nie jest dzielnikiem liczby d.

Udowodnię co następuje:

(III) 9 nie jest dzielnikiem sd(5^m)

DOWÓD

9 | 5^t-1 <==> 6 | t

Innymi słowy:

9 | sd(5^m) <==> 6 | m+1

Na mocy cytowanego wyżej Twierdzenia 2:

9 | sd(5^m) ==> sd(5^5) | sd(m)

Ponieważ 7 | sd(5^5) = 7*558, to założenie
9 | sd(5^m) prowadziłoby do 7 | sd(5^m),
co jest w sprzeczności z niepodzielnością
liczby d przez 7.

KONIEC DOWODU

(IV_1) Istnieje liczba pierwsza p
oraz wykładnik n taki, że p^n jest
dzielnikiem liczby d, p^(n+1) nie jest,
oraz 3|sd(p^n).

DOWÓD_1 brq(d) = 2 jest liczbą całkowitą.
======= Mianownik sd(3^k) jest podzielny
przez 3*3. Musi się z czymś skrócić
we wzorze na brq(d) powyżej. Ale sd(3^k)
jest niepodzielne przez 3, oraz sd(5) nie
jest przez 9.

KONIEC DOWODU_1

(IV_2) Istnieje liczba pierwsza p
oraz wykładnik n taki, że p^n jest
dzielnikiem liczby d, p^(n+1) nie jest,
oraz 5|sd(p^n).

DOWÓD_2 Liczba 3 wyklucza 5 (patrz
======= wcześniejszy post)

KONIEC DOWODU_2

UWAGA Liczby p^n w (IV_1) i w (IV_2)
===== mogą być różne.

*************************************

Niewiele napisałem, ale ziarnko do ziarnka...

guru_ji

[guru_ji]

W obu wypadkach poniżej zapomniałem dodać
do tezy (ale udowodnilem), że istnieje
wspomniane p różne od 3 i od 5.

guru_ji napisał:

> (IV_1) Istnieje liczba pierwsza p
> oraz wykładnik n taki, że p^n jest
> dzielnikiem liczby d, p^(n+1) nie jest,
> oraz 3|sd(p^n).

> (IV_2) Istnieje liczba pierwsza p
> oraz wykładnik n taki, że p^n jest
> dzielnikiem liczby d, p^(n+1) nie jest,
> oraz 5|sd(p^n).

guru_ji

Historia doskonałości i nowsze wyniki

[guru_ji]

Chodzi oczywiście o liczby doskonałe i pokrewne. Moim źródłem informacji
historycznej jest wspaniała "Historia Teorii Liczb" (ang.) Leonarda Eugene'a
Dicksona.

O nowszych wynikach wiem z pracy "More on the total number of prime factors of
an odd perfect number", której autorem jest Kevin G. Hare. Ukazała się lub miała
się ukazać w MATHEMATICS OF COMPUTATION. Jest dostępna w Internecie, w formacie pdf.

***

Zgodnie z obecnym stanem wiedzy historycznej, poważniejsza teoria liczb została
zapoczątkowana przez szkołę Pitagorasa. Pitagoras z Samos żył w latach -569 do
-475, a więc zaawansowana matematyka i teoria liczb w szczególności liczą sobie
dwa i pół tysiąca lat. Żadna inna dziedzina nie może poszczycić się tego typu
długim, ciągłym i intensywnym postępem.

W szczególności wprowadzili pitagorejczycy liczby doskonałe: liczba naturalna n
jest doskonała, gdy suma jej dzielników właściwych (mniejszych od n) jest równa
właśnie n. Dziś wolimy to ująć równoważnie, ale na oko mniej elegancko: niech
sd(n) będzie sumą wszystkich dzielników liczby n; liczbę n nazywamy doskonałą,
gdy sd(n) = 2*n. Powodem do wprowadzenia funkcji sd jest t.zw. teorioliczbowa
multiplikatywność funkcji sd, o czym pisałem w tym wątku i w wątku "Twierdzenie
Fermata o dwóch kwadratach", na Forum. Na przykład 6 jest liczbą doskonałą, gdyż
sd(6) = 1+2+3+6 = 12 = 2*6. Liczba 6 jest najmniejsza wśród doskonałych.

Zajmowano się liczbami doskonałymi w każdym stuleciu naszej ery. To przy okazji
zajmowania się nimi, Fermat odkrył swoje "Małe Twierdzenie Fermata", które mówi,
że jeżeli liczba pierwsza p nie jest dzielnikiem liczby naturalnej a, to jest
dzielnikiem liczby a^(p-1) - 1. Nawet czytałem list Fermata do Mersenne'a, w
którym wielce ożywiony Fermat pisze o swoich trzech odkryciach, w tym o
wspomnianym "M.T.F.". Można wyczuć jak szczęśliwy był przy tej okazji.

Już Euklides z Aleksandrii (od -325r do -265r) podał w swoich słynnych
Elementach postać wszystkich parzystych liczb doskonałych: 2^(p-1)*(2^p-1),
gdzie M(p) := 2^p-1 jest liczbą pierwszą (wtedy p też musi być pierwsze). Do
dziś nie wiemy, czy istnieją inne liczby doskonałe. Ba, Euler pokazał, że wśród
parzystych liczb doskonałych, wszystkie są euklidesowe, jak wyżej. Manuskript
Eulera z tym wynikiem znaleziono już po jego śmierci (nawet dwa, ale jeden był
niekompletny). Leonhard Euler żył w latach 1707-1783. Popatrzcie na te dystanse
czasowe i zadumajcie się. Na koniec podaję tabelkę biograficzną.

Zdawałoby się, że Euklides i Euler zakończyli temat parzystych liczb
doskonałych. W pewnym sensie owszem, ale mimo to nie wiemy, czy jest ich
nieskończenie wiele. Panowie E-E zredukowali kwestię parzystych liczb
doskonałych do kwestii liczb pierwszych postaci

M(n) := 2^n - 1

Liczby pierwsze M(p) nazywamy liczbami pierwszymi Mersenne'a, by uczcić mnicha
francuskiego, który żył w latach 1588 - 1648. Panowie E-E ustanowili wzajemnie
jednoznaczną odpowiedniość (bijekcję) pomiędzy liczbami doskonałymi i liczbami
pierwszymi Mersenne'a. Tyle, że nie wiemy czy liczb pierwszych Mersenne'a jest
nieskończenie wiele. Dalsza, post-eulerowska historia parzystych liczb
doskonałych, to już historia liczb Mersenne'a. Na ogół, największa znana liczba
pierwsza jest mersenne'owska, ale to już jest oddzielny rozdział historii.

***

Hm, pora mi odzipnąć, więc jeszcze podam tylko obiecaną tabelkę (tych którzy już
się pojawili

[guru_ji]

guru_ji napisał:

> Już Euklides z Aleksandrii (od -325r do -265r) [...]

Zgadza się.

Ale w tabelce przejęzyczyłem się:

> Euklides z Samos (-375 do -265)

Miało oczywiście być "z Aleksandrii".

guru_ji

--
zima na mej twarzy. (wh)

sport komputerowo-matematyczny

[robakks]

guru_ji napisał:

| W następnych postach poruszę konkretne problemy, tak że będziecie
| mogli zakasać rękawy i główkować i rachować. W tej nocie dam
| wprowadzenie bardzo ogólne.
|
| W różnych działach matematyki, w szczególności w kombinatoryce, teorii
| liczb i geometrii, pytamy o o pewne parametry, powiedzmy o ciąg a(1)
| a(2) ...., których naukowcy i hobbyści nie są w stanie w danym momencie
| policzyć. Następuje wtedy mnije lub bardziej intensywny wyścig,
| którego celem jest dokładne policzenie nowej, dotąd nieznanej wartości,
| powiedzmy a(6), lub podanie lepszego (ściślejszego) jej oszacowania,
| typu 66 < a(6) < 82.
|
| W ostatnich latach polscy studenci informatyki fantastycznie spisują
| się na najważniejszych, światowych zawodach w programowaniu.
| Natomiast polska obecność na listach światowych rekordów w sportach
| komputerowo-matematycznych jest znikoma i oficjalnie ograniczona
| chyba do jednego jedynego Stanisława P. Radziszowskiego, Profesora na
| wydziale Computer Science Instytutu Technologii w Rochester (NY),
| który jest jednym z tych, którzy mają największy wkład do konkretnej,
| klasycznej Teorii Ramsey'a. W szczególności, prowadzi on w Internecie
| stronę rekordów Teorii Ramsey'a:
|
| www.cs.rit.edu/~spr/ElJC/eline.html
| Interesuje się on też Teorią Konfiguracji