Автор Тема: Уточнённая аппроксимирующая функция числа простых чисел в натуральном ряде  (Прочитано 1751 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Лошкарёв

  • Местный мудрец
  • *****
  • Сообщений: 9702
  • Страна: ua
  • Рейтинг: +858/-1090
    Частота следования  простых чисел среди чисел натурального ряда  апроксимируется  простой функцией одного параметра, основания натураоьных логарифмов:
              π(x)  ~  x 1/ln x                                                         (1)
с оговоркой, что эта формула веоьма неточна при малых  x.
 Лагранж предложил её уточнение:
      π(x) =  x /[(ln x) – 1,08366]                                               (2)
в строгом соответствии с логарифмическим законом:

                           π(x) = 1/ln (x/e^k)
При этом не сохранено условие чтобы вычисленное значение при всех числах натурального ряда не превосходило фактического числа простых чисел.
 Так как функция (1) предельно проста  π(x)  определяется только основанием логарифма, то найти подходящую  простую, и достаточно точную,  функцию его от  x, имея фактические числа простых чисел,  нетрудно.
 Итак, основание логарифма:
                    a  =  f(x)                                                           (3)
 Привожу здесь табличку оснований логарифма, соответствующих количеству простых чисел в натуральном ряде  от 1 до  x:
  100    1000   10000   100000  1000000  10000000
 2,305  2,358   2,368    2,450      2,515       2,554
 
100000000  1000000000  10000000000
    2,566           2,583             2, 597
  Этот ряд уменьшающихся  величин оснований логарифма в (3)  достаточно хорошо апроксимируется  функцией:
         a = e -  1/lg x                                                            (4)
а число простых чисел расчитывается    как и  в (1), но по основанию логарифма  a:
   π(x) =  x / log (e- 1/lg x); x                                              (5)
 Сравнивая числа фактические и вычисленные по  (5) можно увидеть, насколько они близки. Например, до  x = 5000 разница не превышает 20-ти, в то время как  при использовании  (1)  она достигает 100. Существенно, что относительная ошибка аппроксимации формулой (5) во всей области аппроксимации много меньше,  вычисляемой по  (1)  при введении одного лишь дополнительного параметра – функции  (3) простого вида. В функции (4) можно, конечно, тоже изменять основание логарифма, представляя его подходящей функцией х, но компактная функция Лагранжа точнее простой (5), хотя даёт числа простых, превосходящие имеющиеся в натуральном ряде.
Это недопустимо, так как конкретная цель апроксимации в качественном прогнозе.

  

« Последнее редактирование: 25 Январь 2012, 00:38:05 от Лошкарёв »


Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
    Частота следования  простых чисел среди чисел натурального ряда  апроксимируется  простой функцией одного параметра, основания натураоьных логарифмов:
              π(x)  ~  x 1/ln x                                                         (1)
с оговоркой, что эта формула веоьма неточна при малых  x.
 Лагранж предложил её уточнение:
      π(x) =  x /[(ln x) – 1,08366]                                               (2)
не вполне согласующееся с логарифмической зависимостью числа простых чисел в потоке чисел натурального ряда. Поэтому я нашёл уместным  уточнить функцию (1) не нарушая логарифмического закона плотности потока простых чисел и сделать её равно пригодной  при числах, начиная со 100. При этом сохранено условие чтобы вычисленное значение при всех числах натурального ряда не превосходило фактического числа простых чисел.
 Так как функция (1) предельно проста  π(x)  определяется только основанием логарифма, то найти подходящую  простую, и достаточно точную,  функцию его от  x, имея фактические числа простых чисел,  нетрудно.
 Итак, основание логарифма:
                    a  =  f(x)                                                           (3)
 Привожу здесь табличку оснований логарифма, соответствующих количеству простых чисел в натуральном ряде  от 1 до  x:
  100    1000   10000   100000  1000000  10000000
 2,305  2,358   2,368    2,450      2,515       2,554
 
100000000  1000000000  10000000000
    2,566           2,583             2, 597
  Этот ряд уменьшающихся  величин оснований логарифма в (3)  достаточно хорошо апроксимируется  функцией:
         a = e -  1/lg x                                                            (4)
а число простых чисел расчитывается    как и  в (1), но по основанию логарифма  a:
   π(x) =  x / log (e- 1/lg x); x                                              (5)
 Сравнивая числа фактические и вычисленные по  (5) можно увидеть, насколько они близки. Например, до  x = 5000 разница не превышает 20-ти, в то время как  при использовании  (1)  она достигает 100. Существенно, что относительная ошибка аппроксимации формулой (5) во всей области аппроксимации много меньше,  вычисляемой по  (1)  при введении одного лишь дополнительного параметра – функции  (3)  простого вида. К тому же, при этом не нарушается принципиально признанная логарифмическая зависимость числа простых чисел как в (2).
Интересное наблюдение. Теперь я могу сказать - удачи  O0.
Да здравствует чистая математика!  И не будет она осквернена приложениями!

Оффлайн Лошкарёв

  • Местный мудрец
  • *****
  • Сообщений: 9702
  • Страна: ua
  • Рейтинг: +858/-1090
Интересное наблюдение. Теперь я могу сказать - удачи  O0.
1. Спасибо за "надежду"!
Я исправил некоторые "неаккуратные" высказывания в изложении темы и добавил сравнение с функцией Лагранжа. Всё таки у него сохраняется логарифмический закон числа простых чисел, хотя "нормировка" аргумента в знаменателе множителем 1/e^k "произвольна".
Я не выписал его функцию в "первозданном" виде и коэффициент
1,08366 заставил оговориться о "некотором нарушении логарифмического закона". Функция Лагранжа:

                              π(x) = x/ln (x/e^k)

 компактна и точна в сравнении с (1) и с (5) при к = 1,088366, но с числа 100 000 даёт оценки, прогрессивно превышающие фактические числа простых чисел. Кажется, это недопустимо, поскольку речь, в принципе, идёт о величинах достоверных.
 Конечно, усложняя   предложенную мной функцию основания логарифма  a = f(x),  можно бы "искать"...
 Но Лагранж поступил почти великолепно!
 3. Разве, что сама идея функциональной зависимости основания логарифма от  аргумента может и пригодиться.
« Последнее редактирование: 21 Январь 2012, 02:26:33 от Лошкарёв »

Оффлайн Лошкарёв

  • Местный мудрец
  • *****
  • Сообщений: 9702
  • Страна: ua
  • Рейтинг: +858/-1090
1. Спасибо за "надежду"!
Я исправил некоторые "неаккуратные" высказывания в изложении темы и добавил сравнение с функцией Лагранжа. Всё таки у него сохраняется логарифмический закон числа простых чисел, хотя "нормировка" аргумента в знаменателе множителем 1/e^k "произвольна".
Я не выписал его функцию в "первозданном" виде и коэффициент
1,08366 заставил оговориться о "некотором нарушении логарифмического закона". Функция Лагранжа:

                              π(x) = x/ln (x/e^k)

 компактна и точна в сравнении с (1) и с (5) при к = 1,088366, но с числа 100 000 даёт оценки, прогрессивно превышающие фактические числа простых чисел. Кажется, это недопустимо, поскольку речь, в принципе, идёт о величинах достоверных.
 Конечно, усложняя   предложенную мной функцию основания логарифма  a = f(x),  можно бы "искать"...
 Но Лагранж поступил почти великолепно!
 3. Разве, что сама идея функциональной зависимости основания логарифма от  аргумента может и пригодиться.
И она пригодилась.
   Способ, применённый Лагранжем строго рассуждая, нехорош тем, что введенный коэффициент 1,08633  не обусловлен логарифмическим законом роста числа простых чисел. Это эмпирическое число, обеспечивающее очень хорошее приближение расчётного
числа простых чисел среди чисел натурального ряда для ограниченного натурального числа. Однако, именно точность этого приближения на большом интервале натуральных чисел свидетельствует о том, что это следствие существования некой логарифмической функции.
 Разумеется, что применение определённой функции натурального числа, обеспечивающей такую же точность без введения дополнительных параметров, предпочтительнее найденного Лагранжем коэффициента, не зависящего от аргумента  x.
 Оказалось, что функция основания логарифмирования, определяющая плотность потока простых чисел в натуральном ряде, довольно проста:

 a = e^{1 +[x (ln 2)(ln x)]^-1 – (ln x)^-1 – (ln x)^-2 – (ln x)^-3 - …}^-1                       

 При этом число простых чисел определяется простой формулой:

 Π(x)  = x /{1 +[x (ln 2)(ln x)]^-1 – (ln x)^-1 – (ln x)^-2 – (ln x)^-3 - …}ln x                      

    Формулы  тем точнее при больших  x, чем больше слагаемых в знаменателе. Я привожу сравнительную таблицу значений   π(x) для интервала чисел натурального ряда  от 10^2  до 10^10.
      x:     100   500  10^3  10^4   10^5  10^6    
      n(ф):  26    96    169   1260   9572  78498  
      n(L):  28     97    172   1231   9588  78543  
      n(Л):  26    96    174   1234    9591  78474  
      n(Л):  26    96    174   1236    9598  78506  
 
        x:     10^7          10^8             10^9                10^10
     n(ф):   664579    5761455      50847534          455052512  
     n(L):   665140    5768036      50917518          455743190
     n(Л):   664185    5758250. .   50825892          454908920
     n(Л):   664354    5759230      50831907          454947950
  В этой таблице приведены фактические числа, вычисленные по Лагранжу и два варианта  вычисленных значений при двух основаниях логарифмирования:
  a = e^(1 +[x(ln2)(lnx)]^-1 – (ln x)^-1)   и    a =  e^(1+[x(ln2)(lnx)]^-1 – (ln x)^-1 – 1/(ln x)^2).
Формула (6) даёт хорошие оценки и при малых значениях  х:
     x:                10    20   30   40   50    60    70    80    90    100
    n(ф):             4      8    11   13   16    18    20    23    25     26
    n(L):              7    10    12   15   17    19    22    25    26     28
    n(Л):             6     9     12   14   16    18    23    25    26     26
 Таким образом, чисел простых чисел в натуральном ряду, получаемые по формуле, не содержащей эмпирических параметров и в соответствии с логарифмическим законом,  не хуже рассчитываемых с применением поправки Лагранжа.
« Последнее редактирование: 25 Январь 2012, 01:19:51 от Лошкарёв »

Оффлайн BJIaquMup

  • Местный мудрец
  • *****
  • Сообщений: 49165
  • Страна: ru
  • Рейтинг: +659/-1746
  • Пол: Мужской
  • Oшызденeвший НумерОЛУX
Лошкарёву

А вы случайно не перепутали Лагранжа с Лежандром?  :)
Константа 1.08366... это вроде бы константа Лежандра считается.
Вот ссылка: http://evrika.tsi.lv/index.php?name=texts&file=show&f=21
"Собрание звероящеров постановило не признавать эволюцию".

В.А.Шендерович

Оффлайн Гришин Станислав Григорьевич

  • Местный мудрец
  • *****
  • Сообщений: 11387
  • Страна: ru
  • Рейтинг: +617/-2308
Лошкарёву А вы случайно не перепутали Лагранжа с Лежандром?
Константа 1.08366... это вроде бы константа Лежандра считается.
Вот ссылка: http://evrika.tsi.lv/index.php?name=texts&file=show&f=21
Да он так велик, и речь его столь замысловата,
что не мудрено всех перепутать -
Гольдбаха с Гольдбергом, Лагранжа с Лежандром, ...
Пишет то 1.08366, то 1.08836, то 1.08633...
« Последнее редактирование: 28 Январь 2012, 20:04:36 от Анаксагор »
"Оставим книги, обратимся к разуму" Рэнэ Дэкарт (1596-1650).

Оффлайн Гришин Станислав Григорьевич

  • Местный мудрец
  • *****
  • Сообщений: 11387
  • Страна: ru
  • Рейтинг: +617/-2308
А ты чего тут флудишь хер мамин? Ты сучара убогий три по существу, а не киздоболь в серьёзной теме!Ты часом не из еврейских выродков -жидофф будешь?
Чья бы корова мычала. Боцман - еврейская фамилия.
http://malech.ucoz.com/publ/osnovnye/kak_po_familii_otlichit_evreja_ot_slavjano_rusa/1-1-0-9
Это раз. И эта фамилия, как видно из всех твоих постов,
тебе в точности соответствует. "Боц" на иврите означает "грязь".
Не плохо, да? Это два.
А в-третьих, зачем с не чистым рылом в калашный ряд ?
Шнуркам эта тема не по плечу...
"Оставим книги, обратимся к разуму" Рэнэ Дэкарт (1596-1650).

Оффлайн Лошкарёв

  • Местный мудрец
  • *****
  • Сообщений: 9702
  • Страна: ua
  • Рейтинг: +858/-1090
Лошкарёву

А вы случайно не перепутали Лагранжа с Лежандром?  :)
Константа 1.08366... это вроде бы константа Лежандра считается.
Вот ссылка: http://evrika.tsi.lv/index.php?name=texts&file=show&f=21
Спасибо за замечаеие!
Именно случайно и перепутал...
Конспектировал я как раз лекцию Дона Цагира...
 В конспекте у меня написано "Лежандр".
Не везёт мне с именами... просто беда!
 Спешка, "туды её в качель!". Мне уж "половина восьмого", поспешать вынужден...
Спасибо ещё раз и примите мои извинения!
« Последнее редактирование: 09 Февраль 2012, 12:49:14 от Лошкарёв »

Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
Спасибо за замечаеие!
Именно случайно и перепутал...
Конспектировал я как раз лекцию Дона Цагира...
 В конспекте у меня написано "Лежандр".
Не везёт мне с именами... просто беда!
 Спешка, "туды её в качель!". Мне уж "половина восьмого", поспешать вынужден...
Спасибо ещё раз и примите мои извинения!
Вы бы лучше бы прокомментировали текст Боцмана. Хороших Вы защитников находите. И спешка нужна в других делах, не в математике.
Да здравствует чистая математика!  И не будет она осквернена приложениями!

Оффлайн Лошкарёв

  • Местный мудрец
  • *****
  • Сообщений: 9702
  • Страна: ua
  • Рейтинг: +858/-1090
Вы бы лучше бы прокомментировали текст Боцмана. Хороших Вы защитников находите. И спешка нужна в других делах, не в математике.
Будьте точны!
Находит ищущий... Кто "защитил", тому спасибо!
 Не всякий "выдержит" спокойно  мою с Вами дискуссию... Одни только увёртки по поводу многочлена степени 1, представляющего число функцией числовых аргументов: z = x + y + s + r, нужного для пояснения заведомой справедливости ВТФ, "дорогого стоят". Вот равенство  x = 3, справа в нём число, а что же слева?
 И чем я погрешил "в математике"?
Думаю, что Лежандр обратил бы, в первую очередь, внимание на суть дела... А описки досадны, конечно. Но, с другой стороны, "позволяют" ( "вдохновляют" даже на стихи) не обсуждать суть дела.
 
 

Оффлайн Мастеров АВ

  • Путлеровец
  • Хулиган
  • Местный мудрец
  • *****
  • Сообщений: 51974
  • Страна: ru
  • Рейтинг: +1324/-2384
  • Пол: Мужской
  • Смерть картавым фашистам!
    • Личный сайт Мастерова Александра
Статистка частоты появления простых чисел среди натуральных мало что даёт (для практического применения).
Куда интереснее было бы получить простую формулу для генератора простых чисел.
Задаёшь диапазон значений, а он (генератор) тебе вываливает все простые числа из этого диапазона.
Мы были нищими в СССР и останемся нищими в России,
нищими в самой богатой стране до тех пор, пока терпим
жидовскую оккупацию.
                                        Я сказал

Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
Будьте точны!
Находит ищущий... Кто "защитил", тому спасибо!
 Не всякий "выдержит" спокойно  мою с Вами дискуссию... Одни только увёртки по поводу многочлена степени 1, представляющего число функцией числовых аргументов: z = x + y + s + r, нужного для пояснения заведомой справедливости ВТФ, "дорогого стоят". Вот равенство  x = 3, справа в нём число, а что же слева?
 И чем я погрешил "в математике"?
Думаю, что Лежандр обратил бы, в первую очередь, внимание на суть дела... А описки досадны, конечно. Но, с другой стороны, "позволяют" ( "вдохновляют" даже на стихи) не обсуждать суть дела.
1. Значит Вы считаете методы защиты, которые использует Боцман в математической дискуссии, допустимыми?

2. Многочлен - либо алгебраическое выражение либо функция. Если Вам не нравятся такие определения, то доказательно опровергните их. Что означают слова "многочлен, представляющий число функцией". Я интерпретирую их следующим образом - число есть значение многочлена. Либо на выбор - число есть значение алгебраического выражения. Опровергните меня.

3. Я не знаю, на что бы обратил внимание Лежандр. Я обратил внимание на то, что доказательства ВТФ у Вас нет. Сформулируйте свои рассуждения в "школьном" стиле:
Определение.

Теорема.

Доказательство.
« Последнее редактирование: 10 Февраль 2012, 18:24:40 от МаленькийГном »
Да здравствует чистая математика!  И не будет она осквернена приложениями!

Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
Статистка частоты появления простых чисел среди натуральных мало что даёт (для практического применения).
Куда интереснее было бы получить простую формулу для генератора простых чисел.
Задаёшь диапазон значений, а он (генератор) тебе вываливает все простые числа из этого диапазона.
Необходима  не только простая формула, а быстро работающая. А это не одно и тоже
Да здравствует чистая математика!  И не будет она осквернена приложениями!

Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
Вот равенство  x = 3, справа в нём число, а что же слева?
Либо идентификатор переменной, либо алгебраическое выражение, либо функция. Всё зависит от контекста.
Да здравствует чистая математика!  И не будет она осквернена приложениями!

Оффлайн Мастеров АВ

  • Путлеровец
  • Хулиган
  • Местный мудрец
  • *****
  • Сообщений: 51974
  • Страна: ru
  • Рейтинг: +1324/-2384
  • Пол: Мужской
  • Смерть картавым фашистам!
    • Личный сайт Мастерова Александра
Необходима  не только простая формула, а быстро работающая. А это не одно и тоже
Знание частоты простых чисел от их значения сможет ускорить процесс вычисления?
Вряд ли.

С другой стороны, с помощью подобной формулы (интегрированием) можно оценить объём данных, которые придётся сохранить на диске, чтобы записать все 64-рёх разрядные (к примеру) простые числа.

Несколько лет назад я писал алгоритм генератора простых чисел и делал подобные оценки (результат не помню).
Помню только то, что смог просчитать все 32-ух разрядные простые числа.
Далее (до 64 разрядов) я не пошел: объёма моего диска явно не хватало.
Мы были нищими в СССР и останемся нищими в России,
нищими в самой богатой стране до тех пор, пока терпим
жидовскую оккупацию.
                                        Я сказал

Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
Знание частоты простых чисел от их значения сможет ускорить процесс вычисления?
Вряд ли.

С другой стороны, с помощью подобной формулы (интегрированием) можно оценить объём данных, которые придётся сохранить на диске, чтобы записать все 64-рёх разрядные (к примеру) простые числа.

Несколько лет назад я писал алгоритм генератора простых чисел и делал подобные оценки (результат не помню).
Помню только то, что смог просчитать все 32-ух разрядные простые числа.
Далее (до 64 разрядов) я не пошел: объёма моего диска явно не хватало.
64-х разрядов давно мало для практического применения. Интересны 100-200-300 значные простые числа. а то и более
Да здравствует чистая математика!  И не будет она осквернена приложениями!

Оффлайн Мастеров АВ

  • Путлеровец
  • Хулиган
  • Местный мудрец
  • *****
  • Сообщений: 51974
  • Страна: ru
  • Рейтинг: +1324/-2384
  • Пол: Мужской
  • Смерть картавым фашистам!
    • Личный сайт Мастерова Александра
64-х разрядов давно мало для практического применения. Интересны 100-200-300 значные простые числа. а то и более
Кто-то умеет генерить такие числа?
Мы были нищими в СССР и останемся нищими в России,
нищими в самой богатой стране до тех пор, пока терпим
жидовскую оккупацию.
                                        Я сказал

Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
Кто-то умеет генерить такие числа?
К сожалению, свежей литературы у меня нет. Есть старый обзор ВИНИТИ (1985 года - точно не помню). В нём говорится об алгоритмах разложения чисел на простые множители и даётся оценка времени, необходимого для разложения произвольного числа на простые множители

PS. нашёл в dxdy
Цитировать
Прочитал в википедии о разложении 768-битного числа на множители
825192924987886235746450044811291811079246802279580115555330033094015550963829198881579227
40059068212510724569662733379922396193059806426064384437106407861187073051778547531551592
0696498915623049209123508994332541576952978321403939
и ещё http://homes.cerias.purdue.edu/~ssw/cun/
« Последнее редактирование: 14 Февраль 2012, 12:16:17 от МаленькийГном »
Да здравствует чистая математика!  И не будет она осквернена приложениями!

Оффлайн Мастеров АВ

  • Путлеровец
  • Хулиган
  • Местный мудрец
  • *****
  • Сообщений: 51974
  • Страна: ru
  • Рейтинг: +1324/-2384
  • Пол: Мужской
  • Смерть картавым фашистам!
    • Личный сайт Мастерова Александра
Перемножте числа столбиком (програмно), так. чтобы 1000 бит получилось, и вы разложите на множители число разрядностью 1000.

А вот если прибавить (или вычесть) из этого числа единицу (к примеру), во тогда - попробуй разложить
Мы были нищими в СССР и останемся нищими в России,
нищими в самой богатой стране до тех пор, пока терпим
жидовскую оккупацию.
                                        Я сказал

Оффлайн МаленькийГном

  • Местный мудрец
  • *****
  • Сообщений: 752
  • Страна: ru
  • Рейтинг: +55/-57
  • Любопытный прохожий
Перемножте числа столбиком (програмно), так. чтобы 1000 бит получилось, и вы разложите на множители число разрядностью 1000.

А вот если прибавить (или вычесть) из этого числа единицу (к примеру), во тогда - попробуй разложить
Так в этом и состоит сложность задачи разложения - надо быстро разложить случайное число
Да здравствует чистая математика!  И не будет она осквернена приложениями!