Funkcja Omega

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Funkcja Omega

Post autor: max123321 »

Funkcja \(\displaystyle{ \Omega (n)}\)-zlicza wszystkie dzielniki pierwsze \(\displaystyle{ n}\) z krotnościami, w szczególności \(\displaystyle{ \Omega (p^{\alpha})=\alpha}\)

Znalazłem pewien wniosek z dowodu, a mianowicie taki, że:
\(\displaystyle{ \Omega(n) \in \left[ (1-\epsilon)\log \log n,(1+\epsilon)\log\log n\right] }\) dla wszystkich \(\displaystyle{ n \le x}\) poza małym zbiorem wyjątków.

Chciałem przetestować ten wniosek dla \(\displaystyle{ n=75600=2^4 \cdot 3^3 \cdot 5^2 \cdot 7}\), no ale \(\displaystyle{ \Omega (75600)=10}\), natomiast \(\displaystyle{ \log \log (75600) \approx 0,69}\) i to się nijak nie ma do tej \(\displaystyle{ 10}\)-tki. Gdzie robię błąd?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Funkcja Omega

Post autor: Dasio11 »

Widocznie ta liczba należy do "małego zbioru wyjątków". Oczywiste jest, że szacowanie jest nieprawdziwe dla specjalnie skonstruowanych przykładów: liczb pierwszych, liczb postaci \(\displaystyle{ 2^n}\) lub \(\displaystyle{ n!}\) itd. W twierdzeniu zapewne chodzi o to, że takich przykładów jest mało w stosunku do liczb "przeciętnych", które szacowanie spełniają.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Funkcja Omega

Post autor: a4karo »

Warto też dodać, że w teorii liczb log oznacza zwykle logarytm naturalny
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Re: Funkcja Omega

Post autor: max123321 »

Masz rację a4karo to jest logarytm naturalny czyli \(\displaystyle{ \log \log (75600) \approx 2,42}\), ale to i tak dość mocno odbiega od tej \(\displaystyle{ 10}\)-tki.

Trochę jestem zaskoczony bo nie wybierałem tej liczby jakoś szczególnie, chciałem tylko, żeby miała kilka liczb pierwszych w rozkładzie i żeby ich wykładniki były różne parami. Wylosowałem sobie z głowy dwie inne liczby mianowicie \(\displaystyle{ 24}\) i \(\displaystyle{ 84}\), ale też nie spełniają tego wniosku:
\(\displaystyle{ \Omega(24)=4}\)
\(\displaystyle{ \log \log 24 \approx 1,16}\)
\(\displaystyle{ \Omega(84)=4}\)
\(\displaystyle{ \log \log 84 \approx 1,49}\)

Różnice są dość znaczące. Albo coś jest nie tak z tym wnioskiem, albo coś źle liczę. Chyba, że te \(\displaystyle{ \epsilon}\) można wziąć duże, ale to też raczej wątpliwe.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Funkcja Omega

Post autor: a4karo »

A jaki jest związek `x` z epsilonem?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Funkcja Omega

Post autor: Dasio11 »

Jeśli wylosujesz liczby około 10-cyfrowe (a jeśli masz możliwość, to większe) i nie z głowy, tylko w jakiś naprawdę losowy sposób, to będzie o wiele większa szansa, że szacowanie zadziała.

Ale może tak być, że dla sensownych epsilonów, powiedzmy w okolicy \(\displaystyle{ \frac{1}{10}}\), jest jakieś duże \(\displaystyle{ N_0}\) począwszy od którego szacowanie ma zachodzić (pomijając małą liczbę wyjątków). Jeśli przykładowo \(\displaystyle{ N_0 = 10^{100}}\), to czyniłoby cytowane twierdzenie mocno teoretycznym, a testowanie go na przykładach w zasięgu komputera - bezsensownym.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Funkcja Omega

Post autor: Brombal »

@Dasio
.. Jeśli przykładowo \(\displaystyle{ N_0=10^{100} }\), to czyniłoby cytowane twierdzenie mocno teoretycznym, a testowanie go na przykładach w zasięgu komputera - bezsensownym...
Nie do końca. Losowanie liczb, może się odbywać od strony losowych czynników pierwszych i ich wykładników. Można wykonać niezłą próbkę statystyczną. Stucyfrowa liczba to nie problem dla komputera. Schody zaczynają się okolicach 10k do 20k cyfr.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Funkcja Omega

Post autor: a4karo »

Tyle, że liczby między 10k i 20k to dokładnie 0% próbki
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Funkcja Omega

Post autor: Dasio11 »

Brombal pisze: 23 cze 2021, o 17:10Nie do końca. Losowanie liczb, może się odbywać od strony losowych czynników pierwszych i ich wykładników.
Na ile się znam na teorii liczb, mam silne przypuszczenie iż "mały zbiór wyjątków" oznacza, że jest bardzo mała szansa natrafienia na wyjątek przy losowaniu z rozkładem jednostajnym na zbiorze \(\displaystyle{ [1, N]}\) dla jakiegoś bardzo dużego \(\displaystyle{ N}\). Losowanie czynników pierwszych i ich wykładników da zupełnie inny rozkład, o którym twierdzenie nic ciekawego nie mówi.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Funkcja Omega

Post autor: Brombal »

Można powiedzieć, że
\(\displaystyle{ \Omega(N) }\) przyjmuje wartości z zakresu \(\displaystyle{ \left\langle 1, \frac{\log(N) }{\log(2)} \right\rangle }\)
Dodatkowo
\(\displaystyle{ \Omega(N) =1+\Omega( \frac{N} {p_i}) }\) z prawdopodobieństwem \(\displaystyle{ \frac{1}{p_i} }\), gdzie \(\displaystyle{ p_i}\) liczba pierwsza.

Dodano po 2 dniach 2 godzinach 1 minucie 41 sekundach:
\(\displaystyle{ Ω(n)∈[(1−ϵ)\log\log n,(1+ϵ)\log\log n]}\) dla wszystkich \(\displaystyle{ n⩽x}\) poza małym zbiorem wyjątków.
Tak sobie uświadomiłem, że ten mały zbiór wyjątków jest nieskończenie wielki. Przykładowo liczby pierwsze i liczby w postaci \(\displaystyle{ 2^n}\).

Dodano po 2 dniach 15 godzinach 39 minutach 6 sekundach:
Temat nieco umarniał.
Proponuję spojrzenie na zagadnienie od innej strony.
Dla jakiego najmniejszego \(\displaystyle{ \Delta_+}\) i \(\displaystyle{ \Delta_-}\),
\(\displaystyle{ \Omega(N) =\Omega(N-\Delta_-)=\Omega(N+\Delta_+) }\)?
Ostatnio zmieniony 27 cze 2021, o 16:05 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
ODPOWIEDZ