Udowodnij, że dla dowolnych \(\displaystyle{ a,b \in N}\) takich, że \(\displaystyle{ a<b}\) istnieje takie \(\displaystyle{ n\in N}\), że spełniona jest nierówność \(\displaystyle{ a<\frac{\varphi(n+2)}{\varphi(n)}<b}\)
Powodzenia
[Teoria liczb] Nierówność z funkcją Euler'a
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
Piotr Rutkowski
- Użytkownik
- Posty: 2086
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
[Teoria liczb] Nierówność z funkcją Euler'a
Zdaje mi się, że max rozwiązał to zadanko (ale niestety nie tutaj).
Żeby zachować pierwotnego autora rozwiązania może mógłbyś je tu przytoczyć?
Szczególnie, że warto je zobaczyć
Żeby zachować pierwotnego autora rozwiązania może mógłbyś je tu przytoczyć?
Szczególnie, że warto je zobaczyć
-
max
- Użytkownik
- Posty: 3242
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
[Teoria liczb] Nierówność z funkcją Euler'a
Hmm, po chwili zastanowienia mogę powiedzieć, że różne rzeczy się ze mną w moim życiu działy, ale chyba aż takich dziwów nie było, żebym rozwiązał zadanie, które uważam za naprawdę trudne i potem tego nie pamiętał;)
Faktycznie kiedyś się nad tym zastanawiałem, ale nie przypominam sobie, żebym zrobił to zadanie w całości... Pewnie chodzi Ci o to, że gdzieś kiedyś napisałem dowód, że to wyrażenie \(\displaystyle{ \frac{\varphi(n+2)}{\varphi(n)}}\) może przyjmować dowolnie duże wartości (z grubsza wynikało to z rozbieżności szeregu odwrotności kolejnych liczb pierwszych, szczegóły poniżej).
A jeśli Miśku mnie z kimś pomyliłeś, to tym lepiej, bo chciałbym zobaczyć pełne rozwiązanie tego, o ile byłbym w stanie w krótkim czasie zrozumieć metody jakie się w nim pojawiają:)
Niech \(\displaystyle{ \{p_{n}\}}\) będzie ciągiem kolejnych nieparzystych liczb pierwszych, i niech \(\displaystyle{ \mathbb{P} = \{p_{n} \ : \ n\in \mathbb{N} \}}\)
Kładąc \(\displaystyle{ n_{k} = p_{1}\cdot \ldots\cdot p_{k}}\), mamy:
\(\displaystyle{ \varphi(n_{k}) = n_{k}\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right)\\
\varphi(n_{k}+2) =(n_{k} + 2)\prod_{\substack{p \in \mathbb{P} \\ p| n_{k} + 2}} \left(1 - \frac{1}{p}\right)> (n_{k} + 2)\prod_{i = k+1}^{2k}\left(1 - \frac{1}{p_{i}}\right)}\)
ponieważ \(\displaystyle{ n_{k} + 2}\) jest nieparzysta, nie dzieli się przez żadną z liczb pierwszych \(\displaystyle{ p_{1}, \ldots, p_{k}}\), oraz ciąg \(\displaystyle{ \{p_{n}\}}\) jest rosnący i \(\displaystyle{ n_{k} + 2 < p_{k + 1}\cdot \ldots p_{2k}}\).
Teraz korzystając z rozbieżności szeregu \(\displaystyle{ \sum_{n = 1}^{\infty}\frac{1}{p_{n}}}\) dostajemy:
\(\displaystyle{ \lim_{k\to\infty}\ln\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right) = \sum_{i = 1}^{\infty}\ln\left(1 - \frac{1}{p_{i}}\right) = -\infty}\)
na mocy kryterium asymptotycznego. Stąd:
\(\displaystyle{ \lim_{k\to\infty}\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right) = 0^{+}}\)
Z drugiej strony:
\(\displaystyle{ \lim_{k\to }\prod_{i = k+1}^{2k}\left(1 - \frac{1}{p_{i}}\right) qslant \lim_{k\to\infty}\left(1 - \frac{1}{p_{k+1}}\right)^{k} =\\
= \lim_{k\to\infty}\left(\left(1 - \frac{1}{p_{k+1}}\right)^{p_{k+1}}\right)^{\frac{k}{p_{k+1}}} qslant \lim_{k\to\infty}\left(1 - \frac{1}{p_{k+1}}\right)^{p_{k+1}} = \frac{1}{e}}\)
Ostatecznie
\(\displaystyle{ \lim_{k\to\infty}\frac{\varphi(n_{k} + 2)}{\varphi(n_{k})}\geqslant \lim_{k\to\infty}\frac{n_{k} + 2}{n_{k}}\cdot \frac{\left(1 - \frac{1}{p_{k+1}}\right)^{p_{k+1}}}{\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right)} = \left[\frac{e^{-1}}{0^{+}}\right] = +\infty}\)
Tyle wymyśliłem we wrześniu.
W sumie niektóre z tych szacowań były dość grube.
Dosyć obiecującą drogą do ukończenia rozwiązania jest udowodnienie takiej nierówności (o ile jest ona prawdziwa - ja jestem w stanie w to uwierzyć;)):
\(\displaystyle{ \left|\frac{\varphi(n_{k + 1} + 2)}{\varphi(n_{k+1})} - \frac{\varphi(n_{k} + 2)}{\varphi(n_{k})}\right| < 1}\) dla wszystkich \(\displaystyle{ k}\), skąd wobec tego co jest już udowodnione, wynikałaby teza zadania dla \(\displaystyle{ a\geqslant 2}\) (pozostałe dwa przypadki załatwiają np \(\displaystyle{ n = 5}\) i \(\displaystyle{ n = 7}\)). Być może dałoby się to na upartego wyszacować, ale nie mam teraz do tego czasu i cierpliwości. W każdym razie wątek jest odkopany, może ktoś inny będzie miał jakiś pomysł, bądź udowodni tę nierówność.
A tak przy okazji, to przypomniał mi się taki wynik:
Zbiór \(\displaystyle{ \left\{\frac{\varphi(n+1)}{\varphi(n)} \ : \ n\in \mathbb{N}_{1}\right\}}\) jest gęsty w \(\displaystyle{ (0, )}\) (dowodu niestety nie znam).
edit. zjadło mi się dwa razy \(\displaystyle{ \varphi}\) w mianownikach, w tej hipotetycznej nierówności, teraz ma to większe szanse działać.
Faktycznie kiedyś się nad tym zastanawiałem, ale nie przypominam sobie, żebym zrobił to zadanie w całości... Pewnie chodzi Ci o to, że gdzieś kiedyś napisałem dowód, że to wyrażenie \(\displaystyle{ \frac{\varphi(n+2)}{\varphi(n)}}\) może przyjmować dowolnie duże wartości (z grubsza wynikało to z rozbieżności szeregu odwrotności kolejnych liczb pierwszych, szczegóły poniżej).
A jeśli Miśku mnie z kimś pomyliłeś, to tym lepiej, bo chciałbym zobaczyć pełne rozwiązanie tego, o ile byłbym w stanie w krótkim czasie zrozumieć metody jakie się w nim pojawiają:)
Niech \(\displaystyle{ \{p_{n}\}}\) będzie ciągiem kolejnych nieparzystych liczb pierwszych, i niech \(\displaystyle{ \mathbb{P} = \{p_{n} \ : \ n\in \mathbb{N} \}}\)
Kładąc \(\displaystyle{ n_{k} = p_{1}\cdot \ldots\cdot p_{k}}\), mamy:
\(\displaystyle{ \varphi(n_{k}) = n_{k}\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right)\\
\varphi(n_{k}+2) =(n_{k} + 2)\prod_{\substack{p \in \mathbb{P} \\ p| n_{k} + 2}} \left(1 - \frac{1}{p}\right)> (n_{k} + 2)\prod_{i = k+1}^{2k}\left(1 - \frac{1}{p_{i}}\right)}\)
ponieważ \(\displaystyle{ n_{k} + 2}\) jest nieparzysta, nie dzieli się przez żadną z liczb pierwszych \(\displaystyle{ p_{1}, \ldots, p_{k}}\), oraz ciąg \(\displaystyle{ \{p_{n}\}}\) jest rosnący i \(\displaystyle{ n_{k} + 2 < p_{k + 1}\cdot \ldots p_{2k}}\).
Teraz korzystając z rozbieżności szeregu \(\displaystyle{ \sum_{n = 1}^{\infty}\frac{1}{p_{n}}}\) dostajemy:
\(\displaystyle{ \lim_{k\to\infty}\ln\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right) = \sum_{i = 1}^{\infty}\ln\left(1 - \frac{1}{p_{i}}\right) = -\infty}\)
na mocy kryterium asymptotycznego. Stąd:
\(\displaystyle{ \lim_{k\to\infty}\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right) = 0^{+}}\)
Z drugiej strony:
\(\displaystyle{ \lim_{k\to }\prod_{i = k+1}^{2k}\left(1 - \frac{1}{p_{i}}\right) qslant \lim_{k\to\infty}\left(1 - \frac{1}{p_{k+1}}\right)^{k} =\\
= \lim_{k\to\infty}\left(\left(1 - \frac{1}{p_{k+1}}\right)^{p_{k+1}}\right)^{\frac{k}{p_{k+1}}} qslant \lim_{k\to\infty}\left(1 - \frac{1}{p_{k+1}}\right)^{p_{k+1}} = \frac{1}{e}}\)
Ostatecznie
\(\displaystyle{ \lim_{k\to\infty}\frac{\varphi(n_{k} + 2)}{\varphi(n_{k})}\geqslant \lim_{k\to\infty}\frac{n_{k} + 2}{n_{k}}\cdot \frac{\left(1 - \frac{1}{p_{k+1}}\right)^{p_{k+1}}}{\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right)} = \left[\frac{e^{-1}}{0^{+}}\right] = +\infty}\)
Tyle wymyśliłem we wrześniu.
W sumie niektóre z tych szacowań były dość grube.
Dosyć obiecującą drogą do ukończenia rozwiązania jest udowodnienie takiej nierówności (o ile jest ona prawdziwa - ja jestem w stanie w to uwierzyć;)):
\(\displaystyle{ \left|\frac{\varphi(n_{k + 1} + 2)}{\varphi(n_{k+1})} - \frac{\varphi(n_{k} + 2)}{\varphi(n_{k})}\right| < 1}\) dla wszystkich \(\displaystyle{ k}\), skąd wobec tego co jest już udowodnione, wynikałaby teza zadania dla \(\displaystyle{ a\geqslant 2}\) (pozostałe dwa przypadki załatwiają np \(\displaystyle{ n = 5}\) i \(\displaystyle{ n = 7}\)). Być może dałoby się to na upartego wyszacować, ale nie mam teraz do tego czasu i cierpliwości. W każdym razie wątek jest odkopany, może ktoś inny będzie miał jakiś pomysł, bądź udowodni tę nierówność.
A tak przy okazji, to przypomniał mi się taki wynik:
Zbiór \(\displaystyle{ \left\{\frac{\varphi(n+1)}{\varphi(n)} \ : \ n\in \mathbb{N}_{1}\right\}}\) jest gęsty w \(\displaystyle{ (0, )}\) (dowodu niestety nie znam).
edit. zjadło mi się dwa razy \(\displaystyle{ \varphi}\) w mianownikach, w tej hipotetycznej nierówności, teraz ma to większe szanse działać.
Ostatnio zmieniony 15 gru 2008, o 22:05 przez max, łącznie zmieniany 1 raz.
-
Piotr Rutkowski
- Użytkownik
- Posty: 2086
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
[Teoria liczb] Nierówność z funkcją Euler'a
Ach, no racja. Kiedyś to czytałem, teraz spojrzałem na to zadanko, wydało mi się znajome i zdawało mi się, że było tam całe rozwiązanie... Ale tak czy siak warto było wrzucić
Skoro problem jest otwarty wciąż otwarty to spróbuję się wspomóc jakąś "wyższą instancja".
Swoją drogą dzięki za dowód.
Pozdro
Skoro problem jest otwarty wciąż otwarty to spróbuję się wspomóc jakąś "wyższą instancja".
Swoją drogą dzięki za dowód.
Pozdro
Ostatnio zmieniony 15 gru 2008, o 14:20 przez Piotr Rutkowski, łącznie zmieniany 1 raz.
-
max
- Użytkownik
- Posty: 3242
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
[Teoria liczb] Nierówność z funkcją Euler'a
Daj znać jak coś znajdziesz. Może ktoś mądrzejszy znajdzie jakiś zgrabniejszy pomysł. Tak w ogóle, to wczoraj postulowałem nie tą nierówność co chciałem, teraz jest już tak jak chcę (patrz mój poprzedni post).
-
xiikzodz
- Użytkownik
- Posty: 1862
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
[Teoria liczb] Nierówność z funkcją Euler'a
Co do tego:
\(\displaystyle{ \left|\frac{\varphi(n_{k + 1} + 2)}{\varphi(n_{k+1})} - \frac{\varphi(n_{k} + 2)}{\varphi(n_{k})}\right| < 1}\)
Rozwazmy otoczke wypukla wszystkich punktow wykresu funkcji \(\displaystyle{ \psi(n)=\frac{\varphi(n+2)}{\varphi(n)}}\) dla naturalnych argumentow, \(\displaystyle{ N_{\ge 0}}\). Brzegiem tego zbioru sa dwie funkcje, nazwijmy je: \(\displaystyle{ \psi_{min}(x)}\) i \(\displaystyle{ \psi_{max}(x)}\). Mozna pokazac, ze \(\displaystyle{ \psi_{min}(x)}\) asymptotycznie jest funkcja stala rowna \(\displaystyle{ y=1}\), zas \(\displaystyle{ \psi_{max}}\) to funkcja rosnaca (asymptotycznie) wolniej od wszystkich funkcji postaci \(\displaystyle{ y=x\sqrt[k]{x}}\) dla \(\displaystyle{ k\in\mathbb{N}}\) (w razie czego mozna podac dosc dokladne szacowanie).
Jesli wiec rozwazymy punkty \(\displaystyle{ \frac{\varphi(n_k+2)}{\varphi(n_k)}}\), to beda one musialy sie zmiescic w calkiem waskim pasku na mocy nierownosci wyprowadzonych przez maxa:
\(\displaystyle{ \varphi(n_{k}) = n_{k}\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right)}\)
\(\displaystyle{ \varphi(n_{k}+2) > (n_{k} + 2)\prod_{i = k+1}^{2k}\left(1 - \frac{1}{p_{i}}\right)}\)
Byc moze wystarczy zobaczyc, ze ten pasek niegrubszy niz \(\displaystyle{ 1}\). Jesli nie, to moze wystarczy zastosowac te techniki ograniczajace tempo wzrostu \(\displaystyle{ \psi_{max}}\) do ciagu punktow \(\displaystyle{ p_k}\). Widac w kazdym razie, ze tam jest ciasno i ze rozwiazanie moze juz byc calkiem blisko.
\(\displaystyle{ \left|\frac{\varphi(n_{k + 1} + 2)}{\varphi(n_{k+1})} - \frac{\varphi(n_{k} + 2)}{\varphi(n_{k})}\right| < 1}\)
Rozwazmy otoczke wypukla wszystkich punktow wykresu funkcji \(\displaystyle{ \psi(n)=\frac{\varphi(n+2)}{\varphi(n)}}\) dla naturalnych argumentow, \(\displaystyle{ N_{\ge 0}}\). Brzegiem tego zbioru sa dwie funkcje, nazwijmy je: \(\displaystyle{ \psi_{min}(x)}\) i \(\displaystyle{ \psi_{max}(x)}\). Mozna pokazac, ze \(\displaystyle{ \psi_{min}(x)}\) asymptotycznie jest funkcja stala rowna \(\displaystyle{ y=1}\), zas \(\displaystyle{ \psi_{max}}\) to funkcja rosnaca (asymptotycznie) wolniej od wszystkich funkcji postaci \(\displaystyle{ y=x\sqrt[k]{x}}\) dla \(\displaystyle{ k\in\mathbb{N}}\) (w razie czego mozna podac dosc dokladne szacowanie).
Jesli wiec rozwazymy punkty \(\displaystyle{ \frac{\varphi(n_k+2)}{\varphi(n_k)}}\), to beda one musialy sie zmiescic w calkiem waskim pasku na mocy nierownosci wyprowadzonych przez maxa:
\(\displaystyle{ \varphi(n_{k}) = n_{k}\prod_{i = 1}^{k}\left(1 - \frac{1}{p_{i}}\right)}\)
\(\displaystyle{ \varphi(n_{k}+2) > (n_{k} + 2)\prod_{i = k+1}^{2k}\left(1 - \frac{1}{p_{i}}\right)}\)
Byc moze wystarczy zobaczyc, ze ten pasek niegrubszy niz \(\displaystyle{ 1}\). Jesli nie, to moze wystarczy zastosowac te techniki ograniczajace tempo wzrostu \(\displaystyle{ \psi_{max}}\) do ciagu punktow \(\displaystyle{ p_k}\). Widac w kazdym razie, ze tam jest ciasno i ze rozwiazanie moze juz byc calkiem blisko.