Liczba liczb z przedziału o danej własności.

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
MKultra
Użytkownik
Użytkownik
Posty: 130
Rejestracja: 1 lut 2017, o 13:27
Płeć: Mężczyzna
Lokalizacja: Zielona Góra
Podziękował: 2 razy

Liczba liczb z przedziału o danej własności.

Post autor: MKultra »

Cześć.

Dany jest przedział: \(\displaystyle{ \left\{ a,a+1,...,b\right\}}\) .
Czy jest jakiś wzór zliczający te liczby z tego przedziału co są bezkwadratowe i które mają dokładnie \(\displaystyle{ k}\) dzielników pierwszych?

Dzięki za odpowiedzi.

Pozdrawiam.
Awatar użytkownika
Legisl
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 6 cze 2019, o 15:41
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 15 razy
Pomógł: 1 raz

Re: Liczba liczb z przedziału o danej własności.

Post autor: Legisl »

Niech \(\displaystyle{ A}\) będzie tym ciągiem \(\displaystyle{ A=\left\{ a,a+1,...,b\right\}}\) , wtedy liczba liczb bezkwadratowych to dokładnie \(\displaystyle{ s=\left| A\right| -(\lfloor\sqrt{b}\rfloor+\lfloor\sqrt{a}\rfloor)}\)
Oznaczmy przez \(\displaystyle{ \mathfrak{B_{k}}}\) zbiór wszystkich tych liczb o podanej przez Ciebie własności, wtedy \(\displaystyle{ \mathfrak{B_{1}}=\frac {b} {ln(b)}-\frac{a}{ln(a)}}\) , wynika to stąd, że tylko liczby pierwsze mają dokładnie 1 dzielnik pierwszy, a to właśnie wzór na przybliżoną ilość ich w przedziale \(\displaystyle{ [a,b]}\) , przybliżenie staje się coraz dokładniejsze wraz ze wzrostem argumentu. Dla \(\displaystyle{ \mathfrak{B_{2}}}\) będzie to zbiór wszystkich liczb złożonych z dwóch róznych liczb pierwszych, zatem \(\displaystyle{ \mathfrak{B_{2}}=\sum_{\substack{n=1 \\ p\in \PP}} \bigg\lfloor\frac{b-a} {p_{n}}\bigg\rfloor}\) i teraz łatwo to rozwinąc rekurencyjnie na dowolne \(\displaystyle{ k}\) pięknym wzorem, bo moim zdaniem każdy wzór, który posiada jakiś szereg ma już kilka plusów do wyglądu.
\(\displaystyle{ \mathfrak{B_{k}}=\sum_{\substack{ 1 \le m \le ...\le s\le n \le k \\ p\in \PP}} \bigg\lfloor\frac{b-a} {p_{n}p_{s}p_{m}...}\bigg\rfloor}\)
Życzę wszystkim miłego dnia i chwała matematyce!
Awatar użytkownika
Legisl
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 6 cze 2019, o 15:41
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 15 razy
Pomógł: 1 raz

Re: Liczba liczb z przedziału o danej własności.

Post autor: Legisl »

Znalazłem prostszy wzór opisujący dane zagadnienie. Najpierw powiedzmy, czym są liczby prawie pierwsze. Liczby te są iloczynem \(\displaystyle{ k}\) liczb pierwszych. Oznaczmy \(\displaystyle{ k}\)-prawie liczbę pierwszą przez \(\displaystyle{ p(k)}\) , wtedy z twierdzenia Hardy'iego-Ramanujan'a, ilość liczb co najwyżej \(\displaystyle{ p(k)}\) zawierających się w przedziale \(\displaystyle{ [1,n]}\) jest podana następującym wzorem: \(\displaystyle{ \pi_{k}(n)\sim \left( \frac{n} {\log(n)}\right) \frac{\big(\log \log(n)\big)^{k-1}} {(k-1)!}}\) , gdzie znak \(\displaystyle{ \sim}\) oznacza, że przybliżenie staje się coraz lepsze wraz ze wzrostem argumentu. Zatem, by dostać wzór na ilość liczb \(\displaystyle{ p(k)}\) w przedziale \(\displaystyle{ [a,b]}\) , co jest równoważne Twojemu problemowi, musimy przekształcić wzór następująco: \(\displaystyle{ \pi_{k}(n)-\pi_{k-1}(n)}\) odejmujemy ilość liczb co najwyżej \(\displaystyle{ p(k-1)}\) , by dostać ilość tylko liczb \(\displaystyle{ p(k)}\) :\(\displaystyle{ \pi_{k}(n)-\pi_{k-1}(n)\sim \left( \frac{n} {\log(n)}\right) \frac{\big(\log \log(n)\big)^{k-1}} {(k-1)!}-\left( \frac{n} {\log(n)}\right) \frac{\big(\log \log(n)\big)^{k-2}} {(k-2)!}}\) musimy jeszcze odjąć wszystkie liczby kwadratowe, by uzyskać \(\displaystyle{ \mathfrak{B_{k}}}\) : \(\displaystyle{ \mathfrak{B_{k}}\sim \left( \frac{n} {\log(n)}\right) \frac{\big(\log \log(n)\big)^{k-1}} {(k-1)!}-\left( \frac{n} {\log(n)}\right) \frac{\big(\log \log(n)\big)^{k-2}} {(k-2)!}-s}\) , gdzie \(\displaystyle{ s=\left| A\right| -\lfloor\sqrt{b}\rfloor-\lfloor\sqrt{a}\rfloor}\) Mam nadzieję, że pomogłem, pozdrawiam.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Liczba liczb z przedziału o danej własności.

Post autor: a4karo »

Legisl pisze:Niech \(\displaystyle{ A}\) będzie tym ciągiem \(\displaystyle{ A=\left\{ a,a+1,...,b\right\}}\) , wtedy liczba liczb bezkwadratowych to dokładnie \(\displaystyle{ s=\left| A\right| -(\lfloor\sqrt{b}\rfloor+\lfloor\sqrt{a}\rfloor)}\)
W zbiorze \(\displaystyle{ \{5,6,7,8,9,10\}}\) są cztery liczby bezkwadratowe, a wzorek daje \(\displaystyle{ 1}\).
Awatar użytkownika
Legisl
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 6 cze 2019, o 15:41
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 15 razy
Pomógł: 1 raz

Re: Liczba liczb z przedziału o danej własności.

Post autor: Legisl »

Faktycznie. Dziękuję za czujność a4karo , zaraz postaram się go naprawić.-- 19 lip 2019, o 14:11 --Ok, jest gotowe. Zatem wzór powinien wyglądać następująco: \(\displaystyle{ s=(b-\lfloor\sqrt{b}\rfloor)-(a-\lfloor\sqrt{a}\rfloor)}\) i można sprawidzić: \(\displaystyle{ A=\lbrace5,6,7,8,9,10\rbrace \Rightarrow s=(10-3)-(5-2)=4}\)
Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 340
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 42 razy
Pomógł: 60 razy

Re: Liczba liczb z przedziału o danej własności.

Post autor: Gosda »

Ten wzorek zdaje się liczyć liczby, które nie są kwadratami, a nie bezkwadratowe. Dla \(\displaystyle{ a = 1}\), \(\displaystyle{ b = 100}\) daje błędną odpowiedź \(\displaystyle{ 90}\). Poprawna to \(\displaystyle{ 61}\).
Awatar użytkownika
Legisl
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 6 cze 2019, o 15:41
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 15 razy
Pomógł: 1 raz

Re: Liczba liczb z przedziału o danej własności.

Post autor: Legisl »

A, faktycznie. Tutaj mój błąd, myślałem, że liczby bezkwadratowe to, to samo co liczby nie będące kwadratami żadnej liczby całkowitej. Bardzo dziękuję za zwrócenie uwagi na ten istotny szczegół.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Liczba liczb z przedziału o danej własności.

Post autor: a4karo »

No to liczb, które nie są kwadratami w moim przykładzie jest pięć, więc też zły wzór
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Liczba liczb z przedziału o danej własności.

Post autor: Janusz Tracz »

Rozważmy funkcję \(\displaystyle{ W_1:\NN \rightarrow \ZZ \cup \left( \RR \setminus \QQ\right)}\) "warunku liczba nie jest kwadratem". Niech funkcja będzie postaci:
\(\displaystyle{ W_1(n)= \sqrt{n}}\)
Wtedy liczby które są kwadratami ze zbioru \(\displaystyle{ A=\left\{ a,a+1,...,b\right\}}\) można zliczyć wzorem:
\(\displaystyle{ \sum_{n=a}^{b}\left\lfloor\cos^2\left( W_1(n) \pi \right) \right\rfloor=\sum_{n=a}^{b}\left\lfloor\cos^2\left( \sqrt{n} \pi \right) \right\rfloor}\)
Wzór ten dla każdego elementu \(\displaystyle{ a_i\in A}\) rozstrzyga czy \(\displaystyle{ a_i}\) jest kwadratem liczby całkowitej czy nie. Gdy jest to kwadrat to po spierwiastkowaniu daje całkowity wynik a dalej przypisujemy mu \(\displaystyle{ 1}\) i na końcu je zliczamy sumą.

Podobnie można by się było zastanowić nad warunkiem z \(\displaystyle{ k}\) dzielnikami pierwszymi. Gdyby udało się znaleźć funkcję \(\displaystyle{ W_2(n)}\) o własnościach (dla ustalonego \(\displaystyle{ k\in\NN}\)):

\(\displaystyle{ \bullet}\) Gdy \(\displaystyle{ n=p_{i_1}^{\ \alpha _1}p_{i_2}^{\ \alpha _2} \cdot ... \cdot p_{i_{\red{k}}}^{\ \alpha _k}}\) to \(\displaystyle{ W_2(n)\in\ZZ}\)

\(\displaystyle{ \bullet}\) Gdy \(\displaystyle{ n=p_{i_1}^{\ \alpha _1}p_{i_2}^{\ \alpha _2} \cdot ... \cdot p_{i_{\red{m}}}^{\ \alpha _m}}\) oraz \(\displaystyle{ m \neq k}\) to \(\displaystyle{ W_2(n)\in\QQ \setminus \left\{ \frac{1}{W_{1}(n)},\frac{2}{W_{1}(n)},... \right\}}\).

Wtedy "wzór zliczający te liczby z tego przedziału co są bezkwadratowe i które mają dokładnie k dzielników pierwszych" wyraża się wzorem:
\(\displaystyle{ \sum_{n=a}^{b}\left\lfloor\cos^2\left( W_1(n)W_2(n) \pi \right) \right\rfloor=\sum_{n=a}^{b}\left\lfloor\cos^2\left( \sqrt{n}W_2(n) \pi \right)\right\rfloor}\)
Oczywiście problemem jest jawna postać \(\displaystyle{ W_2(n)_k}\). Ale zasada działania jest taka, że funkcja "warunku koniunkcji" czyli \(\displaystyle{ \sqrt{n}W_2(n)}\) przyjmuje wartość całkowitą tylko gdy \(\displaystyle{ n}\) jest kwadratem postaci \(\displaystyle{ n=p_{i_1}^{\ \alpha _1}p_{i_2}^{\ \alpha _2} \cdot ... \cdot p_{i_{\red{k}}}^{\ \alpha _k}}\). W przeciwnym razie gdy nie będzie spełniony warunek pierwszy lub drugi to

\(\displaystyle{ \sqrt{n}W_2(n)\not\in\ZZ \ \Rightarrow \ \left\lfloor\cos^2\left( \sqrt{n}W_2(n) \pi \right)\right\rfloor=0}\)

Wydaje mi się, że określenie jawne \(\displaystyle{ W_2(n)_k}\) może być trudne ale być może coś w stylu

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Legendre%27s_formula
(uogólnionego na dowolne \(\displaystyle{ n\in\NN}\)) się przyda.
ODPOWIEDZ