Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        STUDIA        

Funkcja PI - liczy pierwsze

Rachunek zdań Rachunek kwantyfikatorów

  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
3 odpowiedzi w tym temacie

#1 Damian Klimek

Damian Klimek

    Kombinator

  • Użytkownik
  • 174 postów
1
Neutralny
  • Płeć:Mężczyzna

Napisano 25.04.2016 - 16:42

Określić szacunkowa ilosc 200- cyfrowych liczb pierwszych


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 4210 postów
3410
Profesor
  • Płeć:Mężczyzna

Napisano 26.04.2016 - 09:42

Najpierw określmy ile jest liczb 200 cyfrowych - co nie powinno byc trydne

 

Dwucyfrowych jest 90

Trzycyfrowych jest 900

Czterocyfrowych jest 9000 itd.

 

A własciwie jest nam potrzena najmniejsza i największa liczba 200 cyfrowa

 

Teraz wystarczy skorzystać ze wzoru (przyblizonego) \pi(n)\approx \frac{n}{ln(n)} wzór ten "mówi" ile jest liczb pierwszych mniejszych on n

 

Czyli jeśli N to największa liczba 200 cyfrowa, a n najmniejsza 200 cyfrowa to \frac{N}{ln(N)}-\frac{n}{ln(n)} da ci ilość liczb pierwszych 200 cyfrowych. Proste prawda :).

 

Fakt ciężko to obliczyć choć wszystko jest jasne najmniejsza liczba 200 cyfrowa do 1 i 199 zer a największa liczba  mająca 200 dziewiątek w zapisie dziesiętnym.


Użytkownik Jarekzulus edytował ten post 26.04.2016 - 09:44

  • 1

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską


#3 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 4210 postów
3410
Profesor
  • Płeć:Mężczyzna

Napisano 26.04.2016 - 09:42

Można posłużyć się twierdzeniem Czebyszewa - no Gauss  zaproponował wzór - tylko dowód był nieco później udowodniony przez Hadamarda i de la Vallee Poussina.

Liczby 200-cyfrowe to liczby od 10^{199} a kończąc na 10^{200}-1 czyli mamy nierówność

 

a\cdot \frac{x}{ln(x)}<\pi(x)<b\cdot \frac{x}{ln(x)}

 

gdzie a,b są pewnymi stałymi bliskimi 1, oraz  a<b

 

Jeśli do obu stron (mini maxi) zastosujemy to oszacowanie to dostaniemy

 

a\cdot \frac{10^{199}}{ln(10^{199})}<\pi(10^{199})<b\cdot \frac{10^{199}}{ln(10^{199})}

 

oraz

 

a\cdot \frac{10^{200}-1}{ln(10^{200}-1)}<\pi(10^{200}-1)<b\cdot \frac{10^{200}-1}{ln(10^{200}-1)}

 

czyli po kilku przekształceniach a mianowicie z -b\cdot \frac{10^{199}}{ln(10^{199})}<-\pi(10^{199})<-a\cdot \frac{10^{199}}{ln(10^{199})} mamy

 

a\cdot \frac{10^{200}-1}{ln(10^{200}-1)}- b\cdot \frac{10^{199}}{ln(10^{199})}<\pi(10^{200}-1)-\pi(10^{199})<b\cdot \frac{10^{200}-1}{ln(10^{200}-1)}-a\cdot \frac{10^{199}}{ln(10^{199})}

 

Jest to oszacowanie ilości liczb pierwszych 200-cyfrowych

 

Oszacowania liczb a i b możesz poszukać w necie - są ciągle lepiej przybliżane

 

 

Ostatnie oszacowanie - wykorzystując wzór Stirlinga

 

\(\frac{\pi(n)}{e}\)^{\pi(n)}<(\pi(n))! < \prod_{p\in P_n}<4^n teraz logarytmując skrajne oszacowania mamy

 

ln(\pi(n)-1)<4\cdot ln(4)


  • 0

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską


#4 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 4210 postów
3410
Profesor
  • Płeć:Mężczyzna

Napisano 26.04.2016 - 10:01

A teraz trochę oszacowań na wzorach

 

\frac {x}{\ln x + 2} < \pi(x) < \frac {x}{\ln x - 4}

 

i mamy dwa oszacowania a górę i dół

 

\frac{10^{199}}{ln(10^{199})+2}<\pi(x)<\frac{10^{199}}{ln (10^{199})-4}

 

\frac{(10^{200}-1)}{ln(10^{200}-1)+2}<\pi(x)<\frac{10^{199}}{ln (10^{199})-4}

 

 

 

 

Możesz też użyć takiego oszacowania

 

\pi(x) < 1,25506 \frac {x} {\ln x}

 

 

 

 


  • 0

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską