Udowodnić nierówność
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Udowodnić nierówność
Udowodnić, że istnieje bezwzględna dodatnia stała \(\displaystyle{ C}\), że
\(\displaystyle{ \phi (n) \ge C \frac{n}{\log n} }\)
Czy można poprawić \(\displaystyle{ \log n}\) w mianowniku?
Jak to zrobić? Może mi ktoś pomóc?
\(\displaystyle{ \phi (n) \ge C \frac{n}{\log n} }\)
Czy można poprawić \(\displaystyle{ \log n}\) w mianowniku?
Jak to zrobić? Może mi ktoś pomóc?
Ostatnio zmieniony 31 mar 2021, o 21:55 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Udowodnić nierówność
Wynika to łatwo z pewnej klasycznej armaty. Twierdzenie o Liczbach Pierwszych (jak miałeś funkcje analityczne, to się za bardzo nie zdziwisz, jak sądzę):
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Prime_number_theorem
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Re: Udowodnić nierówność
Nie jestem pewien, ale chyba nie miałem jeszcze Twierdzenia o Liczbach Pierwszych na wykładzie, więc nie wiem czy mogę z tego korzystać. Miałem na razie takie rzeczy jak twierdzenie Czebyszewa i tym podobne, więc jak można to jakoś zrobić bez korzystania z TLP to będę wdzięczny.
- Janusz Tracz
- Użytkownik
- Posty: 4075
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: Udowodnić nierówność
Ze wzoru Legendrea wynika, że wykładnik \(\displaystyle{ p}\)-adyczny (tj.: wykładnik \(\displaystyle{ p}\) w kanonicznej faktoryzacji) \(\displaystyle{ {n \choose k} }\) to:
lemat: Dla dowolnych \(\displaystyle{ x,y\in\RR}\) liczba \(\displaystyle{ \left\lfloor x+y \right\rfloor-\left\lfloor x \right\rfloor-\left\lfloor y \right\rfloor}\) jest równa \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\).
Zatem w sumie tej występują jedynie zera i jedynki. Więc \(\displaystyle{ p_i^{ \alpha _i} \le n}\) oraz \(\displaystyle{ {n \choose k} \le n^{\pi (n)}}\). Ostatecznie:
\(\displaystyle{ \mu_p \left( {n \choose k} \right) = \sum_{i=1}^{ \infty } \left( \left\lfloor \frac{n}{p^i} \right\rfloor - \left\lfloor \frac{k}{p^i} \right\rfloor -\left\lfloor \frac{n-k}{p^i} \right\rfloor \right) }\)
lemat: Dla dowolnych \(\displaystyle{ x,y\in\RR}\) liczba \(\displaystyle{ \left\lfloor x+y \right\rfloor-\left\lfloor x \right\rfloor-\left\lfloor y \right\rfloor}\) jest równa \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\).
Zatem w sumie tej występują jedynie zera i jedynki. Więc \(\displaystyle{ p_i^{ \alpha _i} \le n}\) oraz \(\displaystyle{ {n \choose k} \le n^{\pi (n)}}\). Ostatecznie:
\(\displaystyle{ 2^n = \sum_{k=0}^{n} {n \choose k} \le (n+1)n^{\pi (n)} }\)
zlogarytmuj i oszacuj to co trzeba tak by po jednaj stronie dostać oczekiwane \(\displaystyle{ C \cdot n/ \ln n}\).- Janusz Tracz
- Użytkownik
- Posty: 4075
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: Udowodnić nierówność
Nie wiem ja tylko wypisie znaczki w odpowiedzi na Twoje znaczki. Ale mam pomysł. Zadzwoń do wykładowcy i się spytaj.
-
- Użytkownik
- Posty: 14
- Rejestracja: 3 mar 2021, o 21:09
- Płeć: Mężczyzna
- wiek: 24
- Pomógł: 1 raz
Re: Udowodnić nierówność
Wygląda jak jedna z nierówności z twierdzenia Czebyszewa, stąd pewnie intuicja chłopaków, że chodzi o \(\displaystyle{ \pi(n).}\) Natomiast co oznacza \(\displaystyle{ \phi (n),}\) to chyba najlepiej właśnie spytać prowadzącego.
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Re: Udowodnić nierówność
Ok, pytałem wykładowcy, \(\displaystyle{ \phi (n)}\) to funkcja Eulera. Jak zatem to zrobić?
Dodano po 2 dniach 19 godzinach 1 minucie 6 sekundach:
Może mi ktoś z tym pomóc?
Dodano po 2 dniach 19 godzinach 1 minucie 6 sekundach:
Może mi ktoś z tym pomóc?