oszacowac moc zbioru

[kriegor]

oszacowac \(\displaystyle{ \left| \left\{ \left\langle a,b,c\right\rangle\in\mathbb{N}^3_+ : abc\le n \right\} \right|}\) gdzie \(\displaystyle{ \mathbb{N}_+=\mathbb{N} \setminus \left\{ 0\right\}}\), z bledem wzglednym \(\displaystyle{ o(1)}\)

jak celowac w taki maly blad wzgledny?? jakies nielogiczne bo skoro mam tylko oszacowac a w bledzie wzglednym jest potrzebna dokladna wartosc

no chyba ze wystarczy jak wynik sie poda uzywajac notacji \(\displaystyle{ \Theta}\), tak sobie myslalem ze moze to bedzie ok
ale to nie zmienia faktu ze nie wiem jak to trzeba zrobic jakas dziwna ta asymptotyka ale w sumie fajnie byloby to umiec

moze jakos zaczac od przypadku dwuwymiarowego ?? wtedy liczba takich punktow kratowych ponizej wykresu funkcji \(\displaystyle{ f(x)=\frac{n}{x}}\) to jest chyba jakos powiazana z polem ktore latwo policzyc wtedy to nam daje okolo \(\displaystyle{ n\log n}\) takich punktow ale zupelnie nie umiem tego scisle uzasadnic ani uzyc tutaj notacji w jakiej dostane to \(\displaystyle{ n\log n}\)

[norwimaj]

moze jakos zaczac od przypadku dwuwymiarowego ??

Ok.

wtedy liczba takich punktow kratowych ponizej wykresu funkcji \(\displaystyle{ f(x)=\frac{n}{x}}\)

Jest dokładnie równa \(\displaystyle{ \sum_{x=1}^{\infty}\left\lfloor \frac nx\right\rfloor = \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor}\).

to jest chyba jakos powiazana z polem

Jeśli funkcja \(\displaystyle{ f}\) jest nierosnąca, to \(\displaystyle{ \int_k^{l+1}f(t)\mathrm{d}t\le\sum_{t=k}^l f(t) \le \int_{k-1}^l f(t)\mathrm{d}t}\).

[kriegor]

Jest dokładnie równa \(\displaystyle{ \sum_{x=1}^{\infty}\left\lfloor \frac nx\right\rfloor = \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor}\).

no racja faktycznie a to jest rowne \(\displaystyle{ \Theta (n\log n)}\) co nie ??

tzn w sumie to nie wiem do czego zmierzamy jak ma wygladac wynik z tak duza dokladnoscia jaka jest \(\displaystyle{ o(1)}\)??

[norwimaj]

Jeśli połączysz powyższe nierówności i nierówności \(\displaystyle{ x-1\le\lfloor x\rfloor\le x}\), to nie uzyskasz że \(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor=n\ln n (1+o(1))}\)?

[kriegor]

no jakos mi to nie wychodzi, imo powinno byc \(\displaystyle{ \sum_{x=1}^{n}\frac{n}{x}=n\log n + O(1)}\)

czyli \(\displaystyle{ n(\log n -O(1))-n\le\sum_{x=1}^n \lfloor n/x \rfloor\le n\log n +O(1)}\)

czyli chyba \(\displaystyle{ \sum_{x=1}^n \lfloor n/x \rfloor=n\log n + O(n)}\)

no ale moglbys jakos mniej tajemniczo pisac ?? bo to nowy temat dla mnie i czytajac sama teorie nie sposob raczej wiedziec jak takie zadanie zrobic

no i co do tego bledu to nawet jesli \(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor=n\ln n (1+o(1))}\) to wtedy mamy blad bezwzgledny \(\displaystyle{ o(n\log n)}\) i to jest to samo co wzgledny o ktory nas pytaja \(\displaystyle{ o(1)}\)?? no i czym taka postac jest lepsza od \(\displaystyle{ \Theta(n\log n)}\)?? jest bardziej dokladna ??

[norwimaj]

Że \(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor=n\ln n}\) z błędem względnym, to znaczy dokładnie tyle, że \(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor=n\ln n+o(1)\cdot\sum_{x=1}^n\left\lfloor \frac nx\right\rfloor}\). Równoważnie \(\displaystyle{ \lim_{n\to\infty}\frac{n\ln n}{\sum_{x=1}^n\left\lfloor \frac nx\right\rfloor}=1}\), albo jeszcze inaczej, \(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor=n\ln n (1+o(1))}\).

no i czym taka postac jest lepsza od \(\displaystyle{ \Theta(n\log n)}\)?? jest bardziej dokladna ??

Z równości \(\displaystyle{ f(n)=\Theta(n\log n)}\) nie wynika, że \(\displaystyle{ \lim_{n\to\infty}\frac{n\ln n}{f(n)}}\).

[kriegor]

ok to ja zaczynam juz to lapac powoli
tylko wciaz nie wiem jak dojsc do wyniku \(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor=n\ln n (1+o(1))}\) bo ciagle mi sie wydaje ze \(\displaystyle{ \sum_{x=1}^n n/x =n(\log n + O(1))}\) (tam na gorze bez sensu bylo teraz sie tego trzymam) tak wiec jakbys mogl to wyjasnic jeszcze

no ale wyprzedzajac fakty zeby skrocic twoja meczarnie ze mna to od razu spytam czy dobrze bedzie to:
majac rozwiazanie dla dwoch wymiarow jedziemy iterujac od \(\displaystyle{ c=1}\) do \(\displaystyle{ c=n}\) sumujac rozwiazania dla \(\displaystyle{ ab\le n/c}\) czyli:
\(\displaystyle{ \sum_{c=1}^n \left\lfloor\frac{n}{c}\right\rfloor\log\left( \left\lfloor\frac{n}{c}\right\rfloor\right)(1+o(1))}\) (mogie wyciagnac \(\displaystyle{ (1+o(1))}\) przed sume? bo chyba mam watpliwosci chyba nie zawsze mozna tak w asymptotyce) chyba z bledem bedzie ok bo sie nie nawarstwi (nie bylo to dla mnie od razu oczywiste) ale i tak nie umiem policzyc te sumy co pewnie wynika z tego ze nie umialem juz tamtej bo mi nie wychodzilo to co trzeba

i jeszcze jedno: da sie to zrobic od razu bez rozpatrywania wymiaru mniejszego ??

-- 26 sie 2012, o 15:38 --

nie wynika, że \(\displaystyle{ \lim_{n\to\infty}\frac{n\ln n}{f(n)}}\).

tu czegos chyba zabraklo tak na oko jakiegos \(\displaystyle{ =1}\)

[norwimaj]

tylko wciaz nie wiem jak dojsc do wyniku \(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor=n\ln n (1+o(1))}\)

Ja to sobie zapisałem tak:

\(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor\le
\sum_{x=1}^n \frac nx\le n + \int_1^n\frac nx\mathrm{d}x=n+n\ln n=n\ln n\left(1+\frac1{\ln n}\right),}\)

\(\displaystyle{ \sum_{x=1}^n\left\lfloor \frac nx\right\rfloor\ge
\sum_{x=1}^n \left(\frac nx-1\right) \ge \int_1^{n+1} \left(\frac nx-1\right)\mathrm{d}x=
n\ln(n+1)-n=n\ln n\left(1+\frac{\ln \left(1+\frac1n\right)}{\ln n}-\frac1{\ln n}\right).}\)

mogie wyciagnac \(\displaystyle{ (1+o(1))}\) przed sume?

Jeśli składników jest skończenie wiele, to tak, bo \(\displaystyle{ o(1)+o(1)=o(1)}\).

ale i tak nie umiem policzyc te sumy

Próbuj podobnie jak rozpisałem tę poprzednią.

i jeszcze jedno: da sie to zrobic od razu bez rozpatrywania wymiaru mniejszego ??

Ja nie potrafię.

nie wynika, że \(\displaystyle{ \lim_{n\to\infty}\frac{n\ln n}{f(n)}}\).

tu czegos chyba zabraklo tak na oko jakiegos \(\displaystyle{ =1}\)

Tak, miało być \(\displaystyle{ \lim_{n\to\infty}\frac{n\ln n}{f(n)}=1}\). Na przykład jeśli \(\displaystyle{ \lim_{n\to\infty}\frac{n\ln n}{f(n)}=2}\), to \(\displaystyle{ f(n)=\Theta(n\ln n)=\Theta(n\log n)}\), ale już nie \(\displaystyle{ f(n)=n\ln n(1+o(1))}\).

[kriegor]

o teraz to duzo sie wyjasnilo juz czaje nawet nie takie trudne
wszystko juz rozumiem co bylo do tej pory teraz pozostalo policzyc ta sume no to sprobuje (bo tam pozniej mam jednak jeszcze jeden moment zawachania, mimo ze by sie wydawalo ze dokonczyc juz prosto):

\(\displaystyle{ \sum_{c=1}^n \left\lfloor\frac{n}{c}\right\rfloor\ln\left( \left\lfloor\frac{n}{c}\right\rfloor\right) \le n\left( \ln n \sum_{c=1}^{n}\frac{1}{c}- \sum_{c=1}^{n}\frac{\ln c}{c} \right)=n\left(n\ln^2 n(1+o(1))+... \right)}\)

poniewaz: \(\displaystyle{ \sum_{c=1}^{n}\frac{\ln c}{c}=\frac{\ln 2}{2}+\sum_{c=3}^{n}\frac{\ln c}{c}}\) no i szacujemy ta sume zbadawszy wczesniej ze \(\displaystyle{ f(x)=\frac{\ln x}{x}}\) (a nawiasem mowiac \(\displaystyle{ \int_{}^{} f(x)=\frac{\ln^2 x}{2}}\)) jest nierosnaca dla \(\displaystyle{ x>e}\) wiec znowu sume szacuje calkami:

\(\displaystyle{ \int_{3}^{n+1}\frac{\ln x}{x} \mbox{d}x \le \sum_{c=3}^{n}\frac{\ln c}{c} \le \int_{2}^{n} \frac{\ln x}{x} \mbox{d}x}\)

\(\displaystyle{ \sum_{c=3}^{n}\frac{\ln c}{c} \le \frac{\ln^2 n}{2}-\frac{\ln^2 2}{2}=\frac{1}{2}\ln^2 n(1+o(1))}\)

\(\displaystyle{ \sum_{c=3}^{n}\frac{\ln c}{c} \ge \frac{\ln^2(n+1)}{2}-\frac{\ln^2 3}{2}=\frac{1}{2}(\ln^2 n +\ln^2(1+1/n)+2\ln n\ln(1+1/n)-\ln^2 3)=\frac{1}{2}\ln^2 n (1+o(1))}\)

czyli reasumujac \(\displaystyle{ \sum_{c=1}^n \frac{\ln c}{c}=\frac{1}{2}\left( \ln^2 n (1+o(1))+\ln 2\right)}\)

to majac to chyba bedzie uzasadnione jak napisze: \(\displaystyle{ \sum_{c=1}^n \left\lfloor\frac{n}{c}\right\rfloor\ln\left( \left\lfloor\frac{n}{c}\right\rfloor\right) \le n^2\ln^2 n(1+o(1))}\)
??


z drugiej strony:

\(\displaystyle{ \sum_{c=1}^n \left\lfloor\frac{n}{c}\right\rfloor\ln\left( \left\lfloor\frac{n}{c}\right\rfloor\right) \ge \sum_{c=1}^n \left(\frac{n}{c}-1\right)\ln\left( \frac{n}{c}-1\right)}\)

no i w sumie nie wiem jak ta sume szacowac, wydaje mi sie ze najladniej wyglada \(\displaystyle{ \sum_{c=1}^n \frac{n-c}{c}\ln \frac{n-c}{c}}\)
ale wtedy nei wiem jakie granice calkowania, czy tak sie da

czy do tej pory cos jets dobrze ??

[norwimaj]

\(\displaystyle{ n\left( \ln n \sum_{c=1}^{n}\frac{1}{c}- \sum_{c=1}^{n}\frac{\ln c}{c} \right)=n\left(n\ln^2 n(1+o(1))+... \right)}\)

Zdaje mi się, że o jeden \(\displaystyle{ n}\) za dużo tam jest po prawej stronie. To ma potem wpływ na wynik.

\(\displaystyle{ \int_{3}^{n+1}\frac{\ln x}{x} \mbox{d}x \le \sum_{c=3}^{n}\frac{\ln c}{c} \le \int_{2}^{n} \frac{\ln x}{x} \mbox{d}x}\)

Prawe szacowanie nie jest uzasadnione, bo funkcja nie jest nierosnąca na \(\displaystyle{ (2,n]}\). Trzeba jeszcze jeden wyraz rozpisać, ale na oko widać że to niewiele zmienia.

to majac to chyba bedzie uzasadnione jak napisze: \(\displaystyle{ \sum_{c=1}^n \left\lfloor\frac{n}{c}\right\rfloor\ln\left( \left\lfloor\frac{n}{c}\right\rfloor\right) \le n^2\ln^2 n(1+o(1))}\)
??

Jeśli mam rację że tam na początku jest błąd, to chyba będzie \(\displaystyle{ \sum_{c=1}^n \left\lfloor\frac{n}{c}\right\rfloor\ln\left( \left\lfloor\frac{n}{c}\right\rfloor\right) \le \frac n2\ln^2 n(1+o(1))}\).
Teraz jeśli się uda zrobić takie samo oszacowanie z drugiej strony, to będzie koniec zadania, ale obawiam się, że jednak trzeba będzie ten wynik poprawić przynajmniej o stały czynnik.

z drugiej strony:

\(\displaystyle{ \sum_{c=1}^n \left\lfloor\frac{n}{c}\right\rfloor\ln\left( \left\lfloor\frac{n}{c}\right\rfloor\right) \ge \sum_{c=1}^n \left(\frac{n}{c}-1\right)\ln\left( \frac{n}{c}-1\right)}\)

Zauważ, że po lewej stronie jest sporo składników równych zero, więc można zmniejszyć przedział sumowania (to jest właśnie źródło powyższych obaw). Najpierw ogranicz przedział a potem szacuj (pewnie z drugiej strony też trzeba będzie to poprawić, ale może później).

no i w sumie nie wiem jak ta sume szacowac, wydaje mi sie ze najladniej wyglada \(\displaystyle{ \sum_{c=1}^n \frac{n-c}{c}\ln \frac{n-c}{c}}\)
ale wtedy nei wiem jakie granice calkowania, czy tak sie da

Ja bym próbował tu wydzielić składnik, który wygląda tak samo jak w szacowaniu z drugiej strony. Wtedy część roboty mamy już prawie załatwioną.

Dawno już nie grzebałem się w takich rachunkach. Skąd to zadanie pochodzi? Może istnieje jakiś sprytniejszy sposób, ale ja nie widzę.