Twierdzenie o oszczędności baroku
Wlodzimierz Holsztynski
pierwszych. Z grubsza mówiąc, potęga
q^k, liczby pierwszej p, jest Q-rozrzutna, gdy
sd(p^k) ma dzielnik pierwszy p, nienależący
do Q, i spory w porównaniu z |Q|. Liczbę
naturalną n, o nośniku pierwszym zawartym
w Q, nazwę Q-oszczędną, gdy żadna
potęga q^ord_q(n) nie jest rozrzutna.
Przydam tym pojęciom ścisłe znaczenie.
By uniknąć znużenia formalnością, nie będę
cyzelował definicji abstrakcyjnie, lecz
uzalężnię ją od konkretnych wyników.
(Pełna definicja będzie jasna, mniejsza o nią).
W każdym razie, baroki okażą się oszczędne.
Zatem warto rozpatrywać tylko oszczędne
bazy barokowe, a przy lipcowo-sierpniowym
podejściu opartym bezpośrednio na potęgach
liczb pierwszych, to należy omijać wszelkie
Q-rozrzutne potęgi, gdzie Q jest zbiorem
liczb pierwszych, będącymi podstawami
potęg rozpatrywanych przez algorytm.
***
Niech p(0) := 2, p(1) := 3, ... będzie ciągiem
rosnącym wszystkich liczb pierwszych.
Tw. 0 Zachodzi p(n) >/ 2*n+1 dla każdego
===== n > 0. (Co więcej, nierówność jest ostra
dla każdego n > 3).
To jest oczywiste. Mocniejsze, wciąż elementarne
twierdzenia, dowodziłem pod psem. Klasycznie,
o wiele-wiele potężniejsze twierdzenia są dobrze
znane, bo są wersjami podstawowego twierdzenia
o rozkładzie (w sensie dystrybucji) liczb pierwszych.
Przypominam definicję współczynnika barokowego:
brq(n) := sd(n) / n
Liczba n jest b-barokowa, gdy brq(n) = b \in N.
Pamiętajmy też, że:
(i) (p+1)/p \< brq(p^k) < p/(p-1)
dla dowolnego pierwszego p, oraz k \in N.
Tw 1. brq( (p(t))^k ) < sqrt (t/(t-1))
=====
dla dowolnego t > 1.
Dowód
=====
brq( (p(t))^k ) < p(t) / (p(t)-1) \< (2*t+1)/(2*t)
< sqrt( ((2*t)/(2*t-1)) * (2*t+1)/(2*t) )
< sqrt(t/(t-1))
Koniec dowodu.
Na przykład dla p(2)=5 twierdzenie mówi, że
sd(5^k) < sqrt(2).
Tw. 2 Niech Q będzie nośnikiem pierwszym
===== liczby natiuralnej n. Wtedy:
(a) Jezeli |Q| = 1 lub 2, to brq(n) < |Q|+1;
(b) Jeżeli |Q| > 2, to brq(n) < 3 * sqrt (|Q|-1)
Dowód Część (a) jest łatwa. Udowodnię część (b).
===== Niech
q(0) < q(1) < q(2) < ... < q(|Q|-1)
będzie ciągiem wszystkich liczb pierwszych
należacych do Q. Wtedy p(t) \< q(t), więc
brq(q(t)^k) < sqrt(t/t-1) dla t=2 3...
Zatem
brq(n) < 3 * sqrt(2/1) * sqrt(3/2) * ... * sqrt((|Q|-1)/(|Q|-2)
= 3 * sqrt(|Q| - 1)
Koniec dowodu.
***
Potęgę q^k, gdzie p jest pierwsze, nazwę Q-rozrzutną,
gdy istnieje dzielnik pierwszy p | sd(q^k) (czyli
rekomendowany przez q^k) taki, że p nie należy
do Q, oraz p >/ 3*sqrt(|Q|-1).
Nazwijmy q^ord_q(n) pełnym q-czynnikiem
liczby n.
Liczbę n, o pierwszym nosniku Q, nazywamy
oszczędną, gdy nie ma żadnego Q-rozrzutnego
dzielnika pełnego.
Zachodzi oczywisty, trywialny lemat:
Tw. 3 Jeżeli p jest liczbą pierwszą, nienależącą do
==== nośnika pierwszego Q liczby barokowej n
(innymi słowy: p nie jest dzielnikiem n),
ale rekomendowaną (w pewnej potędze) przez
pewien pełny czynnik liczby n, to p | brq(n),
więc brq(n) >/ p.
Z powyższych wyników natychmiast wynika:
Tw. 4 Niech Q będzie nośnikiem pierwszym
===== liczby barokowej n. Wtedy n jest
Q-oszczędne.
***
Korzystając z mocnych twierdzeń analityxcznej
teorii liczb, można moje powyższe wyniki znacznie
wzmocnić, zwłaszcza dls sporych |Q|. Nawet ich
powyższa skromna wersja poważnie przyspiesza
algorytm, usuwając rozrzutne Q-potęgi (iteracja
daje dodatkowe redukcje, gdy pewne liczby pierwsze
kompletnie znikną, więc redukcję zastosuje się
znowu, ale już do mniejszego Q, aż Q i zbiór
potęg ustabilizuje się).
Pozdrawiam,
Włodek
Wlodzimierz Holsztynski
Q = {2 3 5} oraz |Q| = 3. Udowodniony
parametr Q-oszczędności wynosi więc
3 * sqrt(2)
(Tak naprawdę, to jest jeszcze mniejszy,
bo wynosi (2/1)*(3/2)*(5/4) = 15/4, ale nie
bądźmy chciwi :-) -- chciwość tu nawet nie
popłaca, bo nie ma liczby pierwszej
w przedziale od 3*sqrt(2) do 15/4).
Ponieważ pełny czynnik 3^2 jest Q-rozrzutny:
13 | sd(3^2), gdzie 13 > 3*sqrt(2),
to nie ma co rozpatrywać TWRu 2^3 * 3^2 * 5
jako bazy -- lepiej rozpatrywać 2^3 * 3 * 5,
i ewentualnie tę bazę zredukować do TWRu.
Tutaj akurat kazuje się, że otrzymaliśmy
nie tylko TWR, ale wręcz 3-barokową liczbę
2^3 * 3 * 5
(każdy barok jest świetną bazą dla mniejszych
barokow, będących jego dzielnikami).
Widzimy, że pojęcie oszczędności wychodzi
poza pojęcie TWR, i dobrze je dopełnia.
Pozdrawiam,
Wlodek