2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение09.12.2013, 09:57 
Заслуженный участник


09/02/06
4397
Москва
У вас не убывает, я просто лишнее удалил :

Цитата:
с максимальной значением абсолютной ошибки (при $x \gg p_2$) на основании (3): $\Delta_2<1/p_1[x/p_1]$.(8)

x должна быть в знаменателе, чтобы убывало.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение09.12.2013, 11:47 


23/02/12
3357
Руст в сообщении #798093 писал(а):
Цитата:
с максимальной значением абсолютной ошибки (при $x \gg p_2$) на основании (3): $\Delta_2<1/p_1[x/p_1]$.(8)

x должна быть в знаменателе, чтобы убывало.

Просто неудачная запись.
Запишу понятнее:
$\Delta_2<\frac {1} {p_2[\frac {x} {p_2}]} \approx 1/x$ при больших х.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение09.12.2013, 22:18 


23/02/12
3357
Руст в сообщении #797914 писал(а):
Плотность делящихся на n, не зависит от его разложения на простые и есть $\frac{1}{n}$. Оценки ошибки так же не зависят от его разложения.

Так действительно проще.

Натуральные числа, делящиеся без остатка на натуральное k, принадлежат последовательности $f(n)=kn$. Плотность последовательности $f(n)=kn$ на ограниченном интервале натурального ряда [1,x], где х - большое натуральное число $(x \gg k)$ достигает максимума при $x=kN$ (N- натуральное число): $P(f,1,kN)=\pi(f,1,kN)/kN=N/kN=1/k$ (1) и равна значению асимптотической плотности данной последовательности.
При значение $x=kN+(k-1)$ плотность последовательности $f(n)=kn$ на ограниченном интервале натурального ряда [1,x], где х - большое натуральное число $(x \gg k)$ достигает минимума: $P(f,1,kN+(k-1))=\pi(f,1,kN+(k-1))/kN+(k-1)=\frac {1} {\frac {k-1} {[\frac {x} {k}]}}$, (2) а в следующей точке $kN+k$ плотность последовательности достигает своего максимума - 1/k.
Таким образом, период функции плотности последовательности $f(n)=kn$ - $P(f,1,x)$ равен k (3) и колебания между максимумом и минимумом:
$\Delta=\frac {1} {k}-\frac {1} {k+\frac {k-1} {[x/k]}}<1/kN=\frac {1} {k[x/k]}$.(4)
При больших х $(x \gg k)$ значение $\Delta \approx 1/x$ (5) мало.
В случае $k=p_1 \cdot p_2$, где $p_1,p_2$ - различные простые числа, то плотность последовательности $f(n)=p_1p_2 n$ на интервале натурального ряда [1,x], где х - большое натуральное число $(x \gg p_1p_2)$ на основании (1):
$P(f,1,x)=1/k=1/p_1p_2=1/p_1 1/p_2=P(f_1,1,x) \cdot P(f_2,1,x)$, (6) где $P(f_1,1,x),P(f_2,1,x)$ - соответственно плотность последовательности $f_1(n)=p_1n, f_2(n)=p_2n$ с максимальной ошибкой на основании (5) равной $\Delta \approx 1/x$. (7)
Период функции плотности последовательности $f(n)=p_1p_2 n$ на интервале натурального ряда [1,x], где х - большое натуральное число $(x \gg p_1p_2)$ - $P(f,1,x)$ равен $k=p_1p_2$.(8)
При большом х значение максимальной ошибки $\Delta$ мало и с высокой степенью точности выполняется равенство:
$P(f,1,x)=P(f_1,1,x) \cdot P(f_2,1,x)$.(9)
Учитывая, что последовательности $f_1(n)=p_1n, f_2(n)=p_2n$ являются целочисленными строго возрастающими на интервале натурального ряда [1,x], где х - большое натуральное число $(x \gg p_1p_2)$, поэтому плотности последовательностей $P(f_1,1,x),P(f_2,1,x)$ на данном интервале являются значениями вероятностной меры (или просто вероятностью) соответственно событий, что натуральные числа на интервале [1,x] делятся на простые числа $p_1,p_2$ без остатка.
Следовательно, формула (9) означает независимость событий $A_1,A_2$, что натуральные числа на интервале натурального ряда [1,x], где х - большое натуральное число $(x \gg p_1p_2)$ соответственно делятся на $p_1,p_2$ без остатка:
$Pr(A_1 \cdot A_2)=Pr(A_1) \cdot Pr(A_2)$.(10)
На основании независимости событий (10) независимыми являются соответственно противоположные события $\bar{A_1}, \bar{A_2}$, что натуральные числа на интервале [1,x] не делятся на простые числа $p_1,p_2$ без остатка:
$Pr(\bar{A_1}\cdot \bar{A_2})=Pr(\bar{A_1}) \cdot Pr(\bar{A_2})$.(11)
Вероятности противоположных событий соответственно равны:
$Pr(\bar{A_1})=1-Pr(A_1),  Pr(\bar{A_2})=1-Pr(A_2)$, поэтому на основании (11):
$Pr(\bar{A})= (1-Pr(A_1))(1-Pr(A_2))=(1-1/p_1)(1-1/p_2)$.(12)
Формула (12) справедлива при больших х $(x \gg p_1p_2)$.
Максимальная ошибка в определении вероятности $Pr(\bar{A})$:
$\bar{\Delta}=\Delta_1(1-1/p_2)+\Delta_2(1-1/p_1)+\Delta_1\Delta_2$, (13)
где $\Delta_i<\frac {1} {p_i[x/p_i]}$.(14)
При больших х $(x \gg p_1p_2)$ справедлива оценка:
$\bar{\Delta}\approx \Delta_1(1-1/p_2)+\Delta_2(1-1/p_1)$, (15)
где $\Delta_i \approx  \frac {1} {x}$.(16)

Продолжение следует.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение10.12.2013, 22:17 


23/02/12
3357
Продолжение

Формулу (15) можно записать в виде:
$\bar{\Delta}=(1-1/p_1)(1-1/p_2)(\frac {\Delta_1} {1-1/p_1}+\frac {\Delta_2} {1-1/p_2})$ (17)
и при больших х $(x \gg p_1p_2)$ справедливо соотношение:
$\bar{\Delta}=\frac {1} {x}(1-1/p_1)(1-1/p_2)(\frac {1} {1-1/p_1}+\frac {1} {1-1/p_2})$ (18) значение $\bar{\Delta}$ мало.
$Pr(\bar{A})$ равна плотности последовательности натуральных чисел на интервале [1,x] не кратных простым числам $p_1, p_2$ - g(n) - $P(g,1,x)$.
Минимум функции плотности последовательности g(n) на интервале [1,x] при больших х $(x \gg p_1p_2)$ равен $(1-1/p_1)(1-1/p_2)$, а максимум равен $(1-1/p_1)(1-1/p_2)+\bar{\Delta}$, где $\bar{\Delta}$ определяется формулой (17).
Период колебаний функции последовательности g(n) на интервале [1,x] при больших х $(x \gg p_1p_2)$ равен $p_1 \cdot p_2$.
Формулу (11) можно обобщить на конечное число событий:
$$Pr(\bar{A})=Pr(\bar{A_1}\cdot \bar{A_2} \cdot ... \cdot  \bar{A_m})=Pr(\bar{A_1}) \cdot Pr(\bar{A_2}) \cdot ...\cdot Pr(\bar{A_m}) =(1-1/p_1)(1-1/p_2)...(1-1/p_m)=\prod_{i=1}^{m}(1-1/p_i)$$,(19) где $\bar{A}$ - событие, что натуральные числа из интервала [1,x] не кратно одновременно простым числам - $p_1,p_2,...,p_m$, а $\bar{A_i}$ - событие, что натуральные числа из интервала [1,x] не кратно простому числу $p_i$.
Формула (19) справедлива при больших х $(x \gg p_1p_2)$.
Максимальная ошибка в определении $Pr(\bar{A}) по формуле (19)$:
$\bar{\Delta}=\prod_{i=1}^{m}(1-1/p_i) \sum_{i=1}^{m}{\frac {\Delta_i} {1-1/p_i}}$,(20)
где $\Delta_i<\frac {1} {p_i[x/p_i]}$.
При больших х $(x \gg p_1p_2)$ справедлива оценка максимальной ошибки:
$\bar{\Delta}=1/x\prod_{i=1}^{m}(1-1/p_i) \sum_{i=1}^{m}{\frac {1} {1-1/p_i}}$.(21)
Относительная ошибка при больших х $(x \gg p_1p_2)$:
$\bar{\Delta_o}=1/x \sum_{i=1}^{m}{\frac {1} {1-1/p_i}}$ (22) мала.
Например, при $x=10^8,p_1=2,p_2=3,p_3=5,p_4=7,p_5=11$ по формуле (21) получим $\bar{\Delta}=2,571 \cdot 10^{-8}$.
Относительная ошибка, полученная по формуле (22) равна $\bar{\Delta_o}=7,0166 \cdot 10^{-8}$.
Рассмотрим плотность последовательности $g_r(n)$ на интервале [1,x], получаемой после r-ого шага решета Эратосфена при условии большого х $(x \gg 2 \cdot 3 \cdot...\cdot p_r)$:
$P(g_r,1,x)=\prod_{p \leq p_r}(1-1/p)$.(23)
Максимальная ошибка в определении плотности последовательности $g_r(n)$ на интервале [1,x], при больших х $(x \gg 2 \cdot 3 \cdot...\cdot p_r)$ на основании формулы (21) равна:
$\bar{\Delta_r}=1/x\prod_{p \leq p_r}(1-1/p) \sum_{p \leq p_r}{\frac {1} {1-1/p}}$.(24)
Относительная ошибка в определении плотности последовательности $g_r(n)$ на интервале [1,x], при больших х $(x \gg 2 \cdot 3 \cdot...\cdot p_r)$ на основании формулы (22) равна:
$\bar{\Delta_{or}}=1/x \sum_{p \leq p_r}{\frac {1} {1-1/p}}$.(25)
Оценим величину относительной ошибки, определяемой по формуле (25):
$$\bar{\Delta_{or}}=1/x \sum_{p \leq p_r}{\frac {1} {1-1/p}}=1/x(\sum_{p \leq p_r} {\frac {p} {p-1}})=1/x(\sum_{p \leq p_r}1+\sum_{p \leq p_r} {\frac {1} {p-1}})<1/x(m+2(\ln(\ln(p_r))+B+O(1/\ln(p_r)))$$, (26) где В=0,26419.
В формуле (25) использовано, что $\sum_{p \leq p_r}{\frac {1} {p-1}}<2\sum_{p \leq p_r}{\frac {1} {p}}=2(\ln(\ln(p_r))+B+O(1/\ln(p_r)))$.
Например, при $x=10^{-8}, r=100$ на основании (26) получим: $\bar{\Delta_{or}}<1,0653 \cdot 10^{-6}$.

Продолжение следует.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение11.12.2013, 09:37 


23/02/12
3357
Уточнение формулы:
$\bar{\Delta_{or}}=\frac {1} {x} \sum_{p \leq p_r}{\frac {1} {1-1/p}}=\frac {1} {x}(\sum_{p \leq p_r} {\frac {p} {p-1}})=\frac {1} {x}(\sum_{p \leq p_r}1+\sum_{p \leq p_r} {\frac {1} {p-1}})<\frac {1} {x}(r+2(\ln(\ln(p_r)+B+O(1/\ln(p_r))),(26)$
где В=0,26419.
В формуле (26) использовано, что $\sum_{p \leq p_r}{\frac {1} {p-1}}<2\sum_{p \leq p_r}{\frac {1} {p}}=2(\ln(\ln(p_r))+B+O(1/\ln(p_r)))$.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение12.12.2013, 22:40 


23/02/12
3357
Руст в сообщении #797037 писал(а):
множитель $e^{\gamma}$ для простых при выражении, через последовательное исключение делимостей появляется ввиду того, что $\prod_{p\le \sqrt x}(1-\frac 1p)$ имеет очень большой период и не может оцениваться как плотность не делящихся на эти простые в интервале от 1 до х.

Руст в сообщении #797184 писал(а):
Период последовательности после исключения есть $\prod_{p<\sqrt x} p\approx e^{\sqrt x (1+o(1))}$ гораздо больше х. Именно поэтому не совпадение как и в случае, когда в предыдущем примере оцениваем при х=0.5р на полупериоде.

Именно так.

На основании теоремы о решете Эратосфена для того, чтобы все натуральные числа на интервале [2,x] r-ом шаге решета были простыми должно выполняться условие: $p^2_r <x< p^2_{r+1}$. (27)
С другой стороны для независимости событий, чтобы все числа натурального ряда на интервале [2,x] не были кратны простым числам:$2,3,..p_r$ должны выполняться условия: $x \gg 2 \cdot 3 \cdot...\cdot p_r$. (28) На основании (27), (28) для независимости указанных событий должно выполняться условие $p^2_{r+1} \gg 2 \cdot 3 \cdot...\cdot p_r$ (29). Однако, условие (29) не выполняется уже при r>1.
Поэтому указанные события зависимы и плотность последовательности простых чисел g(n) на интервале [2,x] определяется по формуле: $P(g,2,x)=C(x)\prod_{p\leq \sqrt{x}}(1-1/p)$,(30) где С(х) - коэффициент зависимости.
Например, при r=3 плотность последовательности простых чисел g(n) на интервале от 2 до $p^2_r=25$, определяемая как $P(g,2,25)=\prod_{p\leq 5}(1-1/p)=4/15$. Фактическое значение плотности $P_{*}(g,2,25)=1/4$. Обратите внимание, что $P(g,2,25)>P_{*}(g,2,25)$, т.е. С(х)<1.
При r=5 плотность последовательности простых чисел g(n) на интервале от 2 до $p^2_r=121$, определяемая как $P(g,2,121)=\prod_{p\leq 11}(1-1/p)=48/231$. Фактическое значение плотности $P_{*}(g,2,121)=1/4$. В данном случае относительная ошибка достигает уже 20%. Обратите внимание, что $P(g,2,121)<P_{*}(g,2,121)$, т.е. С(х)>1.
Таким образом, при небольших х коэффициент зависимости C(x) с ростом r колеблется около 1 и возрастает по модулю.
Гренвилле в своей работе http://www.dartmouth.edu/~chance/chance ... cramer.pdf
утверждает, что ошибка в определении плотности простых чисел на интервале [2,x], определяемой по формуле: $\prod_{p\leq \sqrt{x}}(1-1/p)$, колеблется в интервале от $-2^{r-1}/p^2_r$ до $+2^{r-1}/p^2_r$, (31) где r-номер шага решета Эратосфена.
Теперь определим значение С(х) при больших х.
На основании асимптотического закона распределения простых чисел для плотности последовательности простых чисел g(n) на интервале [2,x] для больших х выполняется: $P(g,2,x)=1/\ln(x)+o_1(1/\ln(x))$.(32)
Используя теорему Мертенса можно записать:
$1/\ln(x)=0,5e^{\gamma}\prod_{p\leq \sqrt{x}}(1-1/p)+o_2(1/\ln(x))$, (33)
где $\gamma=0,577215...$ - постоянная Эйлера.
На основании формул (32) и (33) для больших х справедливо равенство :
$P(g,2,x)=0,5e^{\gamma}\prod_{p\leq \sqrt{x}}(1-1/p)+o(1/\ln(x))$,(34)
где $o(x)=o_1(x)+o_2(x)$.
Таким образом, плотность последовательности простых чисел g(n) на интервале натурального ряда [2,x], где х - большое натуральное число определяется как:
$P(g,2,x)=0,5e^{\gamma}\prod_{p\leq \sqrt{x}}(1-1/p)$ с точностью $o(1/\ln(x)$.
Следовательно, С(х) в формуле (30) для больших x равно:
$C(x)=0,5e^{\gamma}=0,890536...$.(35)
Равенство (34) также является вероятностью, что выбранное наугад натуральное число из интервала [2,x], где х - большое натуральное число, является простым.

Буду благодарен за замечания и предложения

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение13.12.2013, 10:17 


23/02/12
3357
Сделаю небольшое уточнение.

Следуя Гренвилле, при росте х на конечном интервале [2,x] (на каждом шаге решета Эратосфена) значение С(х) в формуле (30) колеблется около 1, даже при больших х.
Однако, формулу (34) можно записать в виде: $P(g,2,x) \sim 0,5e^{\gamma}\prod_{p\leq \sqrt{x}}(1-1/p)$, из которой вытекает, что $C=\lim \limits_{x \to \infty} {C(x)}=0,5e^{\gamma}$.(36)

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение15.12.2013, 22:13 


23/02/12
3357
Проведем небольшой анализ результатов.

Плотность последовательности $g_r(n)$ на интервале [1,x], получаемой после r-ого шага решета Эратосфена при условии большого х $(x \gg 2 \cdot 3 \cdot...\cdot p_r)$ определяется по формуле (23): $P(g_r,1,x)=\prod_{p \leq p_r}(1-1/p)$, с максимальной абсолютной ошибкой (24): $\bar{\Delta_r}=1/x\prod_{p \leq p_r}(1-1/p) \sum_{p \leq p_r}{\frac {1} {1-1/p}}$.
Поэтому учитывая, что $\lim \limits_{x \to \infty} {\Delta_r(x)}=0$, (37) получаем, что асимптотическая плотность последовательности, получаемой после r-ого шага решета Эратосфена равна: $P(g_r,1,x) \sim \prod_{p \leq p_r}(1-1/p)$. (38)
На основании формулы (34) можно утверждать, что асимптотическая плотность последовательности простых чисел g(n) равна:
$P(g,2,x) \sim 0,5 e^{\gamma}\prod_{p<\sqrt{x}}(1-1/p)$,(39) что соответствует формуле (7) темы "Противоречия гипотез о простых числах".
При этом надо обратить внимание, что формула (39) выведена без основного предположения гипотез о простых числах (вероятность большого натурального числа х быть простым равна $1/\ln(x)$). Сама формулировка данного предположения вызывает большие вопросы, так как является асимптотической плотностью простых чисел, которая не является вероятностной мерой.
Второе предположение гипотез Харди-Литлвуда и Бейтмана-Хорна о независимости остатков от деления натурального х на различные простые числа вообще не верно на основании этой же формулы (39).

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение22.12.2013, 22:00 


23/02/12
3357
Все формулы данной работы носили приближенный характер, поэтому очень важно проверить их с помощью точных формул.

Обозначим, через $F(x,y)$ число натуральных чисел, меньших или равных х, не делящихся на простые числа, меньшие или равные y.
На основании формула Мейсселя:
$F(x,p_r)=x-\sum_{p_i|M}{ [x/p_i] }+ \sum_{p_ip_j|M}{[x/(p_ip_j)]} +...+(-1)^r \sum_{p_1p_2...p_r|M}{[x/(p_1p_2...p_r)]}$,(40) где $p_i$ - i-ое простое число, а $M=p_1p_2...p_r$.
Обозначим количество натуральных чисел последовательности $f_r$, получаемой на r-ом шаге решета Эратосфена на интервале $[2,x]$ - $\pi(f_r,2,x)$.
Для того, чтобы получить значение $\pi(f_r,2,x)$ надо добавить к функции $F(x,p_r)$ значение r, так как она не включает первые r простых чисел, которые содержит последовательность $f_r$, и вычесть 1, так как она не содержится в интервале $[2,x]$.
Поэтому количество натуральных чисел последовательности $f_r$, получаемой на r-ом шаге решета Эратосфена на интервале $[2,x]$ равно:
$\pi(f_r,2,x)=r-1+x-\sum_{p_i|M}{ [x/p_i] }+ \sum_{p_ip_j|M}{[x/(p_ip_j)]} +...+(-1)^r\sum_{p_1p_2...p_r|M}{[x/(p_1p_2...p_r)]}$.(41)
На основании (41), при больших х ($x\gg 2 \cdot 3 \cdot...\cdot p_r$) плотность последовательности $f_r$, получаемой на r-ом шаге решета Эратосфена на интервале $[2,x]$ равна:
$$P(f_r,2,x)=(r-1)/x+1-1/x(\sum_{p_i|M}{ [x/p_i] }+ \sum_{p_ip_j|M}{[x/(p_ip_j)]} +...+(-1)^r \sum_{p_1p_2...p_r|M}{[x/(p_1p_2...p_r)]}).(42)$$
Например, при $x=10^8,r=3$ на основании (42) получим:
$P(f_r,2,x)=2 \cdot 10^{-8}+0,266666663$. (43)
Теперь определим плотность данной последовательности по формуле (23):
$P(f_r,2,x)=1/2 \cdot 2/3 \cdot 4/5=4/15=0,266666666$.(44)
Сравнивая (43) и (44), получаем, что абсолютная ошибка определения плотности для данного случая по формуле (23):
$\Delta=2 \cdot 10^{-8}+3 \cdot 10^{-9}=2,3 \cdot 10^{-8}$.(45)
На основании (45) относительная ошибка определения плотности для данного случая равна:
$\Delta_o=\frac {2,3 \cdot 10^{-8}} {4/15}=8,625 \cdot 10^{-8}$.(46)
Теперь определим относительную ошибку в определении плотности для данного случая по формуле (26):
$\bar{\Delta_o}<10^{-8}(3+2(0,26419+\ln(\ln(10^8)))=9,355 \cdot 10^{-8}$.(47)
Сравнивая со значением (46) мы видим, что условие (47) действительно выполняется.

Продолжение следует.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение23.12.2013, 20:40 


23/02/12
3357
Если определять плотность последовательности, полученной после r-ого шага решета Эратосфена по формуле (23), то максимальная абсолютная ошибка, определяемая по формуле (24): $\bar{\Delta}=O(1/x)$.
При $x \gg 2 \cdot 3 \cdot...\cdot p_r$ формулу (42) можно представить в виде:
$P(f_r,2,x) \approx (r-1)/x+\prod_{i=1}^{r}(1-1/p_i)$.(48)
За счет учета составляющей $(r-1)/x$ в формуле (48) абсолютная ошибка в определении плотности уменьшится до: $\Delta<1/x$.
Действительно, при r=2 и х=100 точное значение плотности, получаемое по (42):
$P(f_2,2,100)=1/100+1-[100/2]/100-[100/3]/100+[100/6]/100=0,01-0,5-0,33+0,16=0,01+0,33$.
Теперь определим значение плотности для данного случая по приближенной формуле (48):
$P(f_2,2,100) \approx 0,01+0,333$.
Таким образом, абсолютная ошибка в определении плотности для данного случая по формуле (48) составляет:
$\Delta  = 0,003<0,01=1/x$.
При r=2 и х=1000 точное значение плотности, получаемое по (42):
$P(f_2,2,1000)=0,001+0,333$.
Теперь определим значение плотности для данного случая по приближенной формуле (48):
$P(f_2,2,1000) \approx 0,001+0,3333$.
Таким образом, абсолютная ошибка в определении плотности для данного случая по формуле (48) составляет:
$\Delta  = 0,0003<0,001=1/x$.
При r=2 и х=10000 точное значение плотности, получаемое по (42):
$P(f_2,2,10000)=0,0001+0,3333$.
Теперь определим значение плотности для данного случая по приближенной формуле (48):
$P(f_2,2,1000) \approx 0,001+0,33333$.
Таким образом, абсолютная ошибка в определении плотности для данного случая по формуле (48) составляет:
$\Delta  = 0,00003<0,0001=1/x$.

При r=3 и х=1000 точное значение плотности, получаемое по (42):
$P(f_3,2,1000)=2/1000+1-[1000/2]/1000-[1000/3]/1000-[1000/5]/1000+[1000/6]/1000+[1000/15]/1000-[1000/30]/1000=0,002+1-0,5-0,333-0,2+0,167+0,1+0,0666-0,0333=0,002+0,2663$.
Теперь определим значение плотности для данного случая по приближенной формуле (48):
$P(f_2,2,1000) \approx 0,002+0,2666$.
Таким образом, абсолютная ошибка в определении плотности для данного случая по формуле (48) составляет:
$\Delta  = 0,0003<0,001=1/x$.
При r=3 и х=10000 точное значение плотности, получаемое по (42):
$P(f_3,2,10000)=0,0002+0,26663$.
Теперь определим значение плотности для данного случая по приближенной формуле (48):
$P(f_2,2,1000) \approx 0,0002+0,26666$.
Таким образом, абсолютная ошибка в определении плотности для данного случая по формуле (48) составляет:
$\Delta  = 0,00003<0,0001=1/x$.

Следовательно, если при $x \gg 2 \cdot 3 \cdot...\cdot p_r$ определять плотность последовательности на r-ом шаге решета Эратосфена по формуле (48), то абсолютная ошибка по сравнению с формулой (42) не превосходит $\Delta <1/x$.(49)

Продолжение следует.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение24.12.2013, 15:10 


23/02/12
3357
Из формулы (49) вытекает интересное следствие.
Количество натуральных чисел в последовательности, полученной после r-ого шага решета Эратосфена $f_r$ на интервале $[2,x]$ примерно равно: $\pi(f_r,2,x) \approx r-1+[x \cdot \prod_{i=1}^{r}(1-1/p_i)]$.(50)
Абсолютная ошибка в определении $\pi(f_r,2,x)$ не превосходит: $\Delta \leq 1$.(51)

Приведу примеры.
По формуле (40) получим:
$\pi(f_3,2,102)=2+102-[102/2]-[102/3]-[102/5]+[102/6]+[102/10]+[102/15]-[102/30]=29$.
По формуле (50): $\pi(f_3,2,102)=2+[102 \cdot 4/15]=29$. Значения совпадают.
По формуле (40) получим:
$\pi(f_3,2,103)=2+103-[103/2]-[103/3]-[103/5]+[103/6]+[103/10]+[103/15]-[103/30]=30$.
По формуле (50): $\pi(f_3,2,103)=2+[103 \cdot 4/15]=29$. Расхождение на 1.
По формуле (40) получим:
$\pi(f_3,2,104)=2+104-[104/2]-[104/3]-[104/5]+[104/6]+[104/10]+[104/15]-[104/30]=30$.
По формуле (50): $\pi(f_3,2,104)=2+[104 \cdot 4/15]=29$. Расхождение на 1.
По формуле (40) получим:
$\pi(f_3,2,105)=2+105-[105/2]-[105/3]-[105/5]+[105/6]+[105/10]+[105/15]-[105/30]=30$.
По формуле (50): $\pi(f_3,2,105)=2+[105 \cdot 4/15]=30$. Значения совпадают.
По формуле (40) получим:
$\pi(f_3,2,106)=2+106-[106/2]-[106/3]-[106/5]+[106/6]+[106/10]+[106/15]-[106/30]=30$.
По формуле (50): $\pi(f_3,2,106)=2+[106 \cdot 4/15]=30$. Значения совпадают.

Формула (50) удобна для определения количество натуральных чисел в последовательности, полученной после r-ого шага решета Эратосфена при $x \gg 2 \cdot 3 \cdot...p_r$, так ее абсолютная ошибка минимальна, а вычисление по формуле (41) трудоемко. Однако, формула (50) справедлива и при $x \geq 2 \cdot 3 \cdot...\cdot p_r$.
Приведу примеры.
По формуле (40) получим:
$\pi(f_3,2,30)=2+30-[30/2]-[30/3]-[30/5]+[30/6]+[30/10]+[30/15]-[30/30]=10$.
По формуле (50): $\pi(f_3,2,30)=2+[30 \cdot 4/15]=10$. Значения совпадают.
По формуле (40) получим:
$\pi(f_3,2,34)=2+34-[34/2]-[34/3]-[34/5]+[34/6]+[34/10]+[34/15]-[34/30]=11$.
По формуле (50): $\pi(f_3,2,34)=2+[34 \cdot 4/15]=11$. Значения совпадают.

Но уже при $x < 2 \cdot 3 \cdot...\cdot p_r$ формула (50) с оценкой (51) не выполняется.
Пример.
По формуле (40) получим:
$\pi(f_3,2,29)=2+29-[29/2]-[29/3]-[29/5]+[29/6]+[29/10]+[29/15]-[29/30]=10$.
По формуле (50): $\pi(f_3,2,29)=2+[29 \cdot 4/15]=8$. Расхождение на 2.
Это происходит потому, что на интервале $[2,29]$ при r=3 находятся только одни простые числа, для которых формула (40) и соответственно формула (50) не подходят.

Случай с $x < 2 \cdot 3 \cdot...\cdot p_r$, когда на интервале $[2,x]$ находятся только простые числа, рассмотрим отдельно в следующих сообщениях.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение25.12.2013, 15:36 


23/02/12
3357
Хочу уточнить, что в общем случае в последовательности, полученной после r-ого шага решета Эратосфена $f_r$ на интервале $[2, 2 \cdot 3 \cdot...\cdot p_r]$ при $r>3$ находятся не только простые числа. Как известно, только простые числа в последовательности $f_r$ находятся на интервале $[2, (p_r)^2]$, поэтому количество натуральных чисел в последовательности, полученной после r-ого шага решета Эратосфена $f_r$ на интервале $[(p_r)^2, 2 \cdot 3 \cdot...\cdot p_r]$ при r>3 определяются также по формуле (50) с абсолютной ошибкой (51).
Пример. По формуле (40) получим:
$\pi(f_4,2,50)=3+50-[50/2]-[50/3]-[50/5]-[50/7]+[50/6]+[50/10]+[50/14]+[50/15]+[50/21]+[50/35]-[50/30]-[50/42]-[50/105]+[50/210]=15$.
По формуле (50): $\pi(f_4,2,50) \approx 3+[50 \cdot 24/105]=14$. Расхождение равно 1, что соответствует (51).
Случай последовательности, получаемой после r-ого шага решета Эратосфена $f_r$, когда х принадлежит интервалу $[2, (p_r)^2]$ и $f_r$ состоит только из простых чисел, рассмотрим в следующих сообщениях.

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение29.12.2013, 11:52 


23/02/12
3357
На основании решета Эратосфена, для того, чтобы все числа на интервале $[2,x]$ были простыми необходимо, чтобы на r-ом шаге решета выполнялось условие $p_r \leq \sqrt{x}$ (52). Поэтому шаг решета Эратосфена r в формуле (41) выбирается из условия (52).
Таким образом, количество натуральных чисел в последовательности простых чисел $f$ определяется по формуле:
$\pi(f,2,x)=\pi(\sqrt{x})-1+x-\sum_{p_i|M}{ [x/p_i] }+ \sum_{p_ip_j|M}{[x/(p_ip_j)]} +...+(-1)^r\sum_{p_1p_2...p_r|M}{[x/(p_1p_2...p_r)]}$,(52) где $p_r \leq \sqrt{x}$.
На основании (52), плотность последовательности простых чисел $f$ на интервале $[2,x]$ равна:
$$P(f,2,x)=(\pi(\sqrt{x})-1)/x+1-1/x(\sum_{p_i|M}{ [x/p_i] }+ \sum_{p_ip_j|M}{[x/(p_ip_j)]} +...+(-1)^r \sum_{p_1p_2...p_r|M}{[x/(p_1p_2...p_r)]}).(53)$$, где где $p_r \leq \sqrt{x}$.
Здесь также возможны 3 случая:
$x \gg 2 \cdot 3 \cdot ...\cdot p_r$.(54)
$x \geq 2 \cdot 3 \cdot ...\cdot p_r$.(55)
$(p_r)^2 \leq x <2 \cdot 3 \cdot ...\cdot p_r$.(56)
Поэтому, как было показано выше, для плотности последовательности простых чисел на интервале $[2,x]$ выполняется формула:
$P(f,2,x) \approx (\pi(\sqrt{x})-1)/x+\prod_{i=1}^{r}(1-1/p_i)$,(57) где r выбирается из условия $p_r \leq \sqrt{x}$, и абсолютная ошибка в определении плотности последовательности простых чисел $f$ на интервале $[2,x]$ не превосходит: $\Delta(f)<1/x$. (58)
Отсюда следует, что количество натуральных чисел в последовательности простых чисел $f$ на интервале $[2,x]$ примерно равно:
$\pi(f,2,x) \approx \pi(\sqrt{x})-1+[x \cdot \prod_{i=1}^{r}(1-1/p_i)]$,(59)
где r выбирается из условия $p_r \leq \sqrt{x}$, и абсолютная ошибка в определении $\pi(f,2,x)$ не превосходит: $\Delta \leq 1$.(60)


Далее будут приведены примеры для случаев (54)-(56).

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение04.01.2014, 22:49 


23/02/12
3357
На r-ом шаге решета Эратосфена все натуральные числа на интервале [$2,p^2_r$) - простые. Поэтому при r=0 все натуральные числа на интервале [$2, 4$) - простые.
При r=1 все натуральные числа на интервале [$4,9$) становятся также простыми и выполняется неравенство $p_1<p^2_1\leq x < p^2_2$, что соответствует (54).
При r=2 все натуральные числа на интервале [$9,25$) становятся простыми и выполняется неравенство $p_1 \cdot p_2 < p^2_2 \leq x<p^2_3$, что соответствует (54).
При r=3 все натуральные числа на интервале [$25,49$) становятся простыми и выполняется либо неравенство $p^2_3  \leq x<p_1 \cdot p_2 \cdot p_3$, что соответствует (56), либо выполняется неравенство $p_1 \cdot p_2 \cdot p_3  \leq x<p^2_4$, что соответствует (55).
При $r>3$ все натуральные числа на интервале [$p^2_r,p^2_{r+1}$) становятся простыми и выполняется неравенство $p^2_r  \leq x <p^2_{r+1}<p _1 \cdot p_2 \cdot ...\cdot p_r$, что соответствует (56).
Например, найдем по формуле (52) значение - $\pi(f,2,5) =\pi(\sqrt{5}) - 1+5-[5/2]=3$. В данном случае r=1, поэтому он соответствует неравенству (54).
Теперь найдем тоже значение по приближенной формуле (59) - $\pi(f,2,5)  \approx \pi(\sqrt{5})-1+[5 \cdot 1/2)] =2$. Абсолютная ошибка определения по формуле (59) в данном случае равна 1.
Найдем по формуле (52) значение - $\pi(f,2,24) =\pi(\sqrt{24}) - 1+24 -[24/2] - [24/3] +[24/6]=9$. В данном случае r=2, поэтому он соответствует неравенству (54).
Теперь найдем тоже значение по приближенной формуле (59) - $\pi(f,2,24)  \approx \pi(\sqrt{24})-1+[24 \cdot 1/3)] =9$. Абсолютная ошибка определения по формуле (59) в данном случае равна 0.
Найдем по формуле (52) значение:
$$\pi(f,2,30) =\pi(\sqrt{30}) - 1+30 -[30/2] - [30/3] - [30/5] +[30/6] +[30/10]+[30/15]- [30/30]=10.$$
В данном случае r=3, и случай соответствует неравенству (55). Теперь найдем тоже значение по приближенной формуле (59) - $\pi(f,2,30)  \approx \pi(\sqrt{30})-1+[30 \cdot 4/15)] =10$. Абсолютная ошибка определения по формуле (59) в данном случае равна 0.
Известно, что на интервале [$2, 1000$) находятся 168 простых чисел. Теперь найдем тоже значение по приближенной формуле (59) - $\pi(f,2,1000)  \approx \pi(\sqrt{1000})-1+[1000 \cdot 0,157947)] =11-1+157= 167$. Абсолютная ошибка определения по формуле (59) в данном примере равна 1. В данном случае $r>3$, поэтому он соответствует неравенству (56).

 Профиль  
                  
 
 Re: Некоторые св-ва последо-стей на огран.интерв.натурально ряда
Сообщение06.01.2014, 23:17 


23/02/12
3357
vicvolf в сообщении #809589 писал(а):
Известно, что на интервале [$2, 1000$) находятся 168 простых чисел. Теперь найдем тоже значение по приближенной формуле (59) - $\pi(f,2,1000)  \approx \pi(\sqrt{1000})-1+[1000 \cdot 0,157947)] =11-1+157= 167$. Абсолютная ошибка определения по формуле (59) в данном примере равна 1. В данном случае $r>3$, поэтому он соответствует неравенству (56).

Здесь допущена неточность.
По приближенной формуле (59) - $\pi(f,2,1000)  \approx \pi(\sqrt{1000})-1+[1000 \cdot 0,15285)] =11-1+152=162$. Абсолютная ошибка определения по формуле (59) в данном примере равна 6 (16). В скобках указана абсолютная ошибка в определении количества простых чисел по формуле $\pi(f,2,x) \approx [x \cdot \prod_{p \leq \sqrt{x}}(1-1/p)]$.(61)
Величина абсолютной ошибки в формулах (50) и (59) не превосходят 1 только для небольшого числа шагов решета Эратосфена - r. Расчеты показывают, что величина абсолютной ошибки в указанных формулах при $r>5$ больше 1.
По приближенной формуле (59) - $\pi(f,2,200)  \approx \pi(\sqrt{200})-1+[200 \cdot 0,19181)] =6-1+38=43$. Известно, что на интервале [$2, 200$) находятся 46 простых чисел. Поэтому абсолютная ошибка определения по формуле (59) в данном примере равна 3 (8).
По приближенной формуле (59) - $\pi(f,2,300)  \approx \pi(\sqrt{300})-1+[300 \cdot 0,18052)] =7-1+54=60$. Известно, что на интервале [$2, 300$) находятся 62 простых чисел. Поэтому абсолютная ошибка определения по формуле (59) в данном примере равна 2 (8).
По приближенной формуле (59) - $\pi(f,2,400)  \approx \pi(\sqrt{400})-1+[400 \cdot 0,17102)] =8-1+68=75$. Известно, что на интервале [$2, 400$) находятся 78 простых чисел. Поэтому абсолютная ошибка определения по формуле (59) в данном примере равна 3 (10).
По приближенной формуле (59) - $\pi(f,2,700)  \approx \pi(\sqrt{700})-1+[700 \cdot 0,16359)] =9-1+114=122$. Известно, что на интервале [$2, 700$) находятся 125 простых чисел. Поэтому абсолютная ошибка определения по формуле (59) в данном примере равна 3 (11).
По приближенной формуле (59) - $\pi(f,2,900)  \approx \pi(\sqrt{900})-1+[900 \cdot 0,15795)] =10-1+142=151$. Известно, что на интервале [$2, 900$) находятся 154 простых чисел. Поэтому абсолютная ошибка определения по формуле (59) в данном примере равна 3 (12).
Из сравнения величин в скобках и без становится ясно, что формула (59) значительно точнее (61).
При определении количества натуральных чисел для последовательности простых чисел $f(n)$ на интервале [$2, x$) при больших х возрастает абсолютная ошибка в члене $ [x \cdot \prod_{p \leq \sqrt{x}}(1-1/p)]$ в формуле (59), как указывал Гренвилле в своей работе http://www.dartmouth.edu/~chance/chance ... cramer.pdf . Поэтому справедлива формула для плотности простых чисел на интервале [$2, x$) при больших х (34).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 57 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group