Znaleźć wartość \(\displaystyle{ \pi(x)}\) dla argumentu 37.
Odczytując z wykresu funkcji \(\displaystyle{ \pi(x)}\) wiem, że szukana wartość jest równa 12. Pytanie, czy można ją znaleźć jakoś inaczej, np. korzystając z funkcji Eulera?
znaleźć wartość funkcji π(x)
znaleźć wartość funkcji π(x)
Można... zaraz spróbuję opisać.
zauważ, że \(\displaystyle{ [\sqrt{37}]=6}\), a \(\displaystyle{ prime(\pi(6))=prime(3)=5}\). Dlatego od \(\displaystyle{ 37}\) wystarczy odjąć liczby podzielne przez \(\displaystyle{ 2}\), podzielne przez \(\displaystyle{ 3}\), podzielne przez \(\displaystyle{ 5}\), do tego dodać liczby podzielne przez \(\displaystyle{ 2\cdot3=6}\), i dodać te podzielne przez \(\displaystyle{ 2\cdot5=10}\) oraz te podzielne przez \(\displaystyle{ 3\cdot5=15}\) (bo wszystkie one zostały odjęte po dwa razy - raz z powodu jednej liczby pierwszej, a drugi raz z powodu drugiej), a na koniec odjąć te podzielne przez \(\displaystyle{ 2\cdot3\cdot5=30}\) (bo te zostały dodane 3 razy, a nie 2). Nie trzeba rozważać liczb podzielnych przez kolejną liczbę pierwszą tj. \(\displaystyle{ 7}\), bo liczby nie przekraczające \(\displaystyle{ 37}\) i podzielne przez \(\displaystyle{ 7}\) mają najmniejszy dzielnik pierwszy mniejszy od \(\displaystyle{ 7}\), więc już zostały wzięte pod uwagę.
Do ostatecznego wyniku należy dodać liczbę liczb pierwszych \(\displaystyle{ \pi([\sqrt{37}])}\) bo je też odjęliśmy niepotrzebnie, no i odjąć \(\displaystyle{ 1}\) (ponieważ \(\displaystyle{ 1}\) nie jest liczbą pierwszą )
Trochę zbyt dużo zbędnego gadania.
Przejdźmy do obliczeń:
Aby obliczyć ile liczb jest podzielnych przez zadaną liczbę \(\displaystyle{ k}\) wśród liczb naturalnych nie przekraczających zadanej liczby \(\displaystyle{ M}\) należy posłużyć się formułą: \(\displaystyle{ [\frac{M}{k}]}\). Nadajmy odpowiednie indeksy kolejnym liczbom pierwszym do \(\displaystyle{ 5}\), tj: \(\displaystyle{ p_{1}=2}\), \(\displaystyle{ p_{2}=3}\), \(\displaystyle{ p_{3}=5}\). Teraz możemy obliczyć:
\(\displaystyle{ \pi(37)=37-\sum_{i=1}^{\pi([\sqrt{37}])=3}[\frac{37}{p_{i}}]+\sum_{i=1}^{3}\sum_{j=i+1 \wedge i \neq j}^{3}[\frac{37}{p_{i}\cdot p_{j}}]-\sum_{i=1}^{3}\sum_{j=i+1 \wedge i \neq j}^{3}\sum_{k=j+1 \wedge j \neq k}^{3}[\frac{37}{p_{i}\cdot p_{j}\cdot p_{k}}]+\pi([\sqrt{37}])-1=37-[\frac{37}{2}]-[\frac{37}{3}]-[\frac{37}{5}]+[\frac{37}{2\cdot3}]+[\frac{37}{2\cdot5}]+[\frac{37}{3\cdot5}]-[\frac{37}{2\cdot3\cdot5}]+3-1=37-18-12-7+6+3+2-1+3-1=12}\)
pozdrawiam
Aha, \(\displaystyle{ [x]}\) oznacza całość z liczby \(\displaystyle{ x}\) tzn. największą liczbę całkowitą, która nie przekracza zadanej liczby \(\displaystyle{ x}\).
-- 23 lis 2009, o 23:48 --
Czy widzisz jak przenieść tę metodę na ogólny przypadek liczenia \(\displaystyle{ \pi(x)}\)?
zauważ, że \(\displaystyle{ [\sqrt{37}]=6}\), a \(\displaystyle{ prime(\pi(6))=prime(3)=5}\). Dlatego od \(\displaystyle{ 37}\) wystarczy odjąć liczby podzielne przez \(\displaystyle{ 2}\), podzielne przez \(\displaystyle{ 3}\), podzielne przez \(\displaystyle{ 5}\), do tego dodać liczby podzielne przez \(\displaystyle{ 2\cdot3=6}\), i dodać te podzielne przez \(\displaystyle{ 2\cdot5=10}\) oraz te podzielne przez \(\displaystyle{ 3\cdot5=15}\) (bo wszystkie one zostały odjęte po dwa razy - raz z powodu jednej liczby pierwszej, a drugi raz z powodu drugiej), a na koniec odjąć te podzielne przez \(\displaystyle{ 2\cdot3\cdot5=30}\) (bo te zostały dodane 3 razy, a nie 2). Nie trzeba rozważać liczb podzielnych przez kolejną liczbę pierwszą tj. \(\displaystyle{ 7}\), bo liczby nie przekraczające \(\displaystyle{ 37}\) i podzielne przez \(\displaystyle{ 7}\) mają najmniejszy dzielnik pierwszy mniejszy od \(\displaystyle{ 7}\), więc już zostały wzięte pod uwagę.
Do ostatecznego wyniku należy dodać liczbę liczb pierwszych \(\displaystyle{ \pi([\sqrt{37}])}\) bo je też odjęliśmy niepotrzebnie, no i odjąć \(\displaystyle{ 1}\) (ponieważ \(\displaystyle{ 1}\) nie jest liczbą pierwszą )
Trochę zbyt dużo zbędnego gadania.
Przejdźmy do obliczeń:
Aby obliczyć ile liczb jest podzielnych przez zadaną liczbę \(\displaystyle{ k}\) wśród liczb naturalnych nie przekraczających zadanej liczby \(\displaystyle{ M}\) należy posłużyć się formułą: \(\displaystyle{ [\frac{M}{k}]}\). Nadajmy odpowiednie indeksy kolejnym liczbom pierwszym do \(\displaystyle{ 5}\), tj: \(\displaystyle{ p_{1}=2}\), \(\displaystyle{ p_{2}=3}\), \(\displaystyle{ p_{3}=5}\). Teraz możemy obliczyć:
\(\displaystyle{ \pi(37)=37-\sum_{i=1}^{\pi([\sqrt{37}])=3}[\frac{37}{p_{i}}]+\sum_{i=1}^{3}\sum_{j=i+1 \wedge i \neq j}^{3}[\frac{37}{p_{i}\cdot p_{j}}]-\sum_{i=1}^{3}\sum_{j=i+1 \wedge i \neq j}^{3}\sum_{k=j+1 \wedge j \neq k}^{3}[\frac{37}{p_{i}\cdot p_{j}\cdot p_{k}}]+\pi([\sqrt{37}])-1=37-[\frac{37}{2}]-[\frac{37}{3}]-[\frac{37}{5}]+[\frac{37}{2\cdot3}]+[\frac{37}{2\cdot5}]+[\frac{37}{3\cdot5}]-[\frac{37}{2\cdot3\cdot5}]+3-1=37-18-12-7+6+3+2-1+3-1=12}\)
pozdrawiam
Aha, \(\displaystyle{ [x]}\) oznacza całość z liczby \(\displaystyle{ x}\) tzn. największą liczbę całkowitą, która nie przekracza zadanej liczby \(\displaystyle{ x}\).
-- 23 lis 2009, o 23:48 --
Czy widzisz jak przenieść tę metodę na ogólny przypadek liczenia \(\displaystyle{ \pi(x)}\)?
Ostatnio zmieniony 24 lis 2009, o 15:59 przez czeslaw, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.