Поиск простых чисел. Решето Эратосфена.
Данный калькулятор находит простые числа методом, известным с античных времен, как решето Эратосфена. Напомним, простые числа, не имеют других делителей, кроме себя и единицы.
В результате работы калькулятора отобразится матрица содержащая составные числа (серые) и простые числа (черные).
Решето Эратосфена
Конечное число
Рассчитать
Ссылка Сохранить Виджет
Это был демонстрационный калькулятор с самым примитивным алгоритмом. Диапазон чисел в нем ограничен до 1000 ввиду избыточного вывода и ресурсоемкой реализации. Калькулятор и его исходный код будет полезен, тем кто хочет понять логику древнегреческого ученого, придумавшего метод в 3 веке до нашей эры.
Следующий калькулятор является развитием идеи Эратосфена, без избыточных операций и с оптимизацией по объему используемой памяти. Тут уже (если позволит ваш компьютер) можно попробовать посчитать простые числа до нескольких миллиардов. Однако будьте осторожны — с большой конечной границей память и процессор вашего устройства будут нещадно использоваться.
2, 3, 5, 7, 11, . 282 589 933 − 1
В декабре прошлого года было обнаружено новое самое большое известное простое число, которое оказалось равным 2 82 589 933 − 1. Десятичная запись этого числа более чем вдвое превышает длину романа Марселя Пруста «В поисках утраченного времени» (самого длинного романа по версии книги рекордов Гинесса) и примерно на семь процентов длиннее предыдущего рекорда. О том, как это произошло, по каким формулам ищут и не находят простые числа, а также зачем они нужны, по просьбе N + 1 рассказывает математик Иван Тельпуховский.
Что такое простые числа
Простые числа, которые вы можете увидеть на форзаце почти любого школьного учебника математики, — это натуральные числа, бóльшие единицы, которые делятся только на себя и на 1. Например, число 3 — простое, а число 6 (= 2 × 3) уже нет.
Простые числа являются «элементарными кирпичиками» в мире всех натуральных чисел, поскольку любое натуральное число можно единственным образом представить в виде произведения простых чисел (с точностью до порядка сомножителей). Скажем, число 90 представляется в виде произведения 2 × 3 × 3 × 5. Это утверждает основная теорема арифметики, известная по крайней мере еще Евклиду, который, однако, не смог дать ей полного доказательства. Доказательство было дано молодым Гауссом лишь спустя более двух тысяч лет.
Разумно задаться вопросом: конечно ли множество простых чисел в числовом ряду? Сможем ли мы представить любое число как произведение, скажем, только чисел 2, 3 и 5? Отрицательный ответ на этот вопрос дал Евклид в девятой книге своих «Начал». Его аргумент оказался столь простым и фундаментальным, что до сих пор является одним из первых строгих математических доказательств, изучаемых в школе.
Действительно, докажем от противного и допустим, что все простые числа могут быть записаны в виде конечного списка p1, . pn. Перемножим все числа из списка и прибавим единицу: p1 × . × pn + 1. Поскольку получившееся число не содержится в нашем списке и, следовательно, не может быть простым, оно должно делиться на простое число. Однако при делении на любое из чисел p1, . pn получается остаток 1. Налицо противоречие.
Для знакомых с азами элементарной топологии рекомендуем разобрать занятное доказательство бесконечности простых чисел, предложенное Фурстенбергом.
Мы знаем, что простых чисел бесконечно много, но как часто они встречаются в натуральном ряду? Иными словами, как быстро растут простые числа и можем ли мы найти для них хотя бы приблизительную формулу?
Ответ на этот вопрос был дан в конце XIX века и называется теоремой о распределении простых чисел. Чтобы ее сформулировать, обозначим за π(N) количество простых чисел, не превосходящих число N. Теорема утверждает, что функция π(N) ведет себя как функция N / lnN для больших N, где lnN — натуральный логарифм N. Более строго, в пределе, отношение этих функций равно единице:
Теорему можно интерпретировать следующим образом: у наугад выбранного числа от 1 до N шанс оказаться простым асимптотически равен 1 / lnN. Как следствие, мы получаем, что простые числа попадаются чем дальше, тем реже (попробуйте убедиться в этом сами).
Скорость роста простых чисел
Доказать эту теорему позволило развитие комплексного анализа, чьи методы активно используются в теории чисел по сей день. Простого доказательства у теоремы нет, но его идея, принадлежащая Риману, основывается на том, что распределение простых чисел тесно связано с нулями дзета-функции, задаваемой по следующей формуле для s > 1:
= 1 мы получаем
, который расходится, поэтому функция не определена в данной точке). Например, для
= 2 мы получаем
Риман показал, что дзета функцию можно доопределить на множество всех комплексных чисел (кроме s = 1), где у нее раскрываются удивительные свойства (взгляните на эти графики: первый, второй, третий и четвертый).
Возвращаясь к неформальной идее доказательства: можно определить функцию-«звуковую волну», которая звучит как логарифмы всех простых чисел (и степеней простых чисел) меньше заданного числа N. Если «прослушать» эту функцию (а именно, применив к ней преобразование, близкое к преобразованию Фурье) и записать услышанные ноты, то ими окажутся нули дзета-функции!
Завершающим моментом доказательства является отсутствие нулей дзета-функции на вертикальной прямой x = 1 на комплексной плоскости. Отметим удивительную связь со знаменитой гипотезой Римана: она утверждает, что нули дзета-функции в полосе 0 ≤ x ≤ 1 расположены только на «критической» прямой x = 1/2. Пользуясь аллегорией, гипотезу Римана можно сформулировать так: «Музыка простых чисел формирует аккорд».
Из теоремы о распределении простых чисел несложно вывести следующую примерную формулу для N-го простого числа: pN ~ N lnN. На самом деле, ее можно даже немного улучшить: pN ~ N(lnN + lnlnN − 1). Например, для тысячного простого числа эта формула ошибается уже меньше чем в 1 процент (поэкспериментируйте сами!).
Несмотря на низкий процент ошибки, ее величина растет с N, и даже если допустить, что гипотеза Римана верна, то величина ошибки будет, грубо говоря, порядка корня из N, поэтому подлинное N-ое простое число отыскать становится все сложнее. Более того, точная формула для N-ного простого числа, которая бы позволила его найти за короткое время (например, полиномиальное по числу разрядов), на сегодняшний день неизвестна.
Почему многочлены не помогут
За последние столетия было предпринято великое множество попыток описать точную формулу простых чисел. Одним из примеров такой формулы может послужить многочлен с целыми коэффициентами.
Давайте рассмотрим «игрушечный» пример — линейный многочлен f(n) = an + b. Значения такого многочлена называются арифметической прогрессией. Во-первых, очевидно, что если у чисел a и b есть общий делитель (больший единицы), то больше одного простого элемента в прогрессии не появится (к примеру, 3n + 3 всегда будет делиться на 3). Кроме того, ясно, что только простые значения у многочлена f(n) тоже не могут быть, потому что числа f(kb) = a × kb + b = (ak + 1) × b делятся на b для всех k. Как бы то ни было, математиком Дирихле (известным своим принципом) было доказано, что если числа a и b взимно просты, то в соответствующей арифметической прогрессии встретится бесконечно много простых чисел.
В качестве следующего примера можно рассмотреть квадратичные многочлены, то есть вида an 2 + bn + c. Например, в XVIII веке Леонард Эйлер заметил, что значения квадратичного многочлена n 2 + n + 41 являются простыми для 39 последовательных значений n. Эти явления иллюстрирует скатерть Улама: в ней по спирали из центра записываются последовательные числа (не показаны), и черным среди них помечаются простые:
Обратите внимание, что некоторые диагонали на скатерти отчетливо выделяются среди других: на них много простых чисел. Оказывается, что диагонали на скатерти Улама и представляют собой значения квадратичных многочленов (попробуйте доказать!). Несмотря на эти обнаружения, до сих пор неизвестно о существовании многочлена второй степени (или выше) от одной переменной, который принимал бы бесконечно много простых значений (что никакой такой многочлен не может принимать только простые значения, нетрудно доказать).
Если перейти к случаю нескольких переменных, то оказывается, что существует многочлен, чьи положительные целые значения совпадают со множеством простых чисел. Этот многочлен является «побочным» результатом многолетней деятельности специалистов в теории алгоритмов, направленной на решение десятой проблемы Гильберта, в которой поставил точку ленинградский (тогда) аспирант Юрий Матиясевич в 1970 году. Отметим, что этот многочлен совершенно бесполезен для вычислений.
Недавно в прессе освещалось достижение математика Симона Плуфа, который утверждает, что нашел конкретную формулу, выдающую рекордные 50 (судя по его сайту, уже и все 100) простых чисел подряд. Внимательный взгляд на эту эмпирическую формулу лишний раз показывает, как далеки мы от осмысленного результата по направлению к формуле простых чисел. И несмотря на то, что мы не знаем, что искомой формулы не может быть в природе, мы попытаемся порассуждать о том, почему ее, скорее всего, нет.
Действительно, эта формула должна бы быть очень умной! Ведь промежуток между соседними простыми числами (и, соответственно, соседними значениями формулы) может быть сколь угодно большим (подсказка: рассмотрите числа n! + 2, . n! + n), а может быть (бесконечно часто!) ограниченной длины по теореме, доказанной в 2013 году Итаном Чжаном (в идеале длины 2, как утверждает гипотеза о числах-близнецах).
Простые числа как случайные процессы
Другим указанием на отсутствие формулы простых чисел может служить современная точка зрения на множество простых чисел как на модель случайного множества. Грубо говоря, простые числа слишком беспорядочно разбросаны среди натурального ряда и про них можно думать как о псевдослучайном множестве. Разумеется, между простыми числами наблюдается структура, например они все (кроме одного) являются нечетными числами, а значит, не могут идти друг за другом. Простые числа являются детерминированным множеством, принадлежность к которому проверяется за полиномиальное время по числу разрядов.
Тем не менее, если не принимать во внимание мультипликативные свойства простых чисел (которые мы перечисляли), то за ними проглядываются свойства случайного множества. Например, верно, что возможные остатки при делении на 10 для простых чисел (это 1, 3, 7 или 9) асимптотически равновероятны. Примечательно то, что в рамках различных моделей, имитирующих простые числа, легко доказываются многие неразрешенные гипотезы, например, все проблемы Ландау.
Примером модели простых чисел является вероятностная модель Крамера, основанная на теореме о распределении простых чисел: множество выбираются случайно таким образом, что его плотность на отрезке от 1 до N равнаяется уже встречавшемуся выражению 1 / lnN. Модель Крамера можно улучшить, если принять во внимание элементарные свойства «настоящих» простых чисел.
Несмотря на то, что все эти модели не доказывают уже известных гипотез, они, вместе с численными экспериментами, позволяют измерить силу предположения или привести к новым плодотворным догадкам. В частности, используя свою модель, Крамер сформулировал знаменитую гипотезу о величине больших промежутков между простыми числами, над которой бьются математики, но к которой пока не подошли вплотную.
Примеры частных формул
Несмотря на то, что математики не могут найти формулу, выражающую все простые числа, хорошо известны простые формулы, значения которых позволяют явно находить очень большие простые числа. Последние двадцать с лишним лет главной такой формулой является 2 p -1, чьи значения называются числами Мерсенна. Поиском простых чисел Мерсенна занимается проект добровольных распределенных вычислений GIMPS, о котором мы уже неоднократно писали (например, здесь, здесь и здесь).
Среди других подобных формул можно отметить обобщенные простые числа Ферма, поиском которых занимается похожий проект PrimeGrid.
Эта деятельность имеет мало общего с «атакой» на недоказанные гипотезы о простых числах, которая использует все передовые достижения математики, и больше похожа на своеобразную форму нумизматики (в чем частично признаются создатели). Тем не менее, как и в случае с доказательством гипотезы Римана, новое СБИПЧ (самое большое известное простое число) может принести «охотнику» денежный гонорар (пусть и скорее всего гораздо меньший). Впрочем, в науке это не главное.
Сколько простых чисел от 1 до n
Простые числа разбросаны в натуральном ряду очень прихотливым образом, и не удивительно, что издревле математики стремились найти «формулу для простых чисел». Такими формулами можно называть формулы, обладающие разными свойствами, и здесь очень важно понять, что нам требуется на самом деле.
Самая простая формула для простых чисел выглядит, так:
где p n обозначает n -е простое число. Чем же эта формула не устраивает нас? Дело в том, что правая часть этого равенства вычисляется слишком сложным образом попробуйте, например, самостоятельно найти p 1975 ! Мы же хотим получить аналогичную формулу с возможно более простым способом вычисления правой части (однако, как мы увидим, простота вычислений понятие совсем не очевидное). Это, так сказать, программа-максимум .
Ради простоты формулы можно отказаться от требования явной зависимости от и искать формулы, дающие простые числа, быть может, не по порядку. Далее, можно отказаться от желания задать одной формулой сразу все простые числа и требовать только того, чтобы формула давала бесконечно много простых чисел. Можно, наконец, допустить, чтобы эта формула давала наряду с бесконечно многими простыми числами и некоторые составные числа. Это программа-минимум .
Формулы, кажущиеся очень простыми, на деле могут оказаться не лучше Именно к таким примерам мы сейчас и переходим.
Теорема Е. М. Райта
В 1947 году В. X. Миллс опубликовал следующий результат:
Существует вещественное число λ такое, что при любом число
Впоследствии появился ещё ряд формул такого же типа. Однако все это были результаты, формулировка которых выглядит заманчивой и многообещающей, но доказательство разочаровывает. Тому, кто хочет понять, почему это так, мы предлагаем разобраться в доказательстве следующей теоремы Е. М. Райта:
Существует вещественное число μ такое, что всякое число вида
Ключевым пунктом в доказательстве теоремы Райта является так называемый постулат Бертрана . Согласно этому постулату при между x и всегда есть простое число. Эту гипотезу впервые высказал французский математик Бертран: доказать её он не смог, а потому использовал в своих рассуждениях в качестве недоказуемого постулата. Доказательство гипотезы Бертрана было найдено впоследствии выдающимся русским математиком П. Л. Чебышёвым 2 .
Чтобы найти нужное число μ выберем сначала последовательность простых чисел q 1 , такую, что при любом
| q n | q n +1 | |
| 2 | < q n +1 < 2 | 1. |
(В качестве q 1 можно взять любое простое число, возможность же неограниченного продолжения последовательности с соблюдением гарантирует постулат Бертрана.)
Обозначим для краткости число
где берётся n возведений в степень, через a обратную функцию,
log 2 log 2 . log 2 β
Попробуем выбрать число μ так, чтобы при
| [exp 2 n μ] = q n . | (5) |
Согласно определению целой части числа эквивалентно неравенству
Прологарифмировав его n раз по получим ещё одно двойное неравенство,
| log 2 n q n ≤ μ < log 2 n ( q n + 1). | (6) |
Проверьте сами, что из (4) следует
Таким образом, последовательность
строго возрастает и ограничена сверху; следовательно, она имеет предел. мы и возьмём в качестве докажите, что так выбранное μ удовлетворяет даже более сильному, неравенству
| log 2 n q n < μ < log 2 n ( q n + 1), | (7) |
и, следовательно, равенство (5) справедливо. Теорема Райта доказана.
Основным недостатком формул (2) и (3) является то, что они (точнее, их доказательства) не дают никакого способа находить новые простые числа, ибо чтобы вычислить простое число по нужно числа знать с достаточной точностью. Таким образом, в некотором смысле являются всего лишь замаскированными (и ухудшенными) вариантами Кроме того, вид на самом деле почти ничего не говорит именно о множестве простых чисел. Из доказательства теоремы Райта видно, что формулы, аналогичные можно указать для любого «достаточно густого» множества.
Недостатки формул (2) и (3) порождены тем, что в них входят вещественные числа задаваемые неким косвенным образом. В дальнейшем мы будем рассматривать лишь формулы, в которые входят только целочисленные коэффициенты. Такие формулы обладают важным преимуществом: они могут быть (в принципе) выписаны явно.
Простые числа Мерсенна и Ферма
Формулы Миллса, Райта и другие подобные формулы остались изолированными фактами, не приведшими к новым результатам. Однако в других случаях возможность представить некоторые простые числа в том или ином специальном виде имеет неожиданные и глубокие следствия.
Рассмотрим сейчас две формулы, имеющие совсем простой вид:
| p = 2 n 1, | (8) |
| p = 2 n + 1. | (9) |
Очевидно, что формула (8) не всегда даёт простые числа; например, если n составное число, то p делится на и на Но и при получающееся по число может оказаться составным:
2 11 1 = 2047 = 23 · 89.
Простые числа, получающиеся по формуле (8), называются числами Мерсенна в честь Марена Мерсенна, который ещё в 1664 году указал все простые не превосходящие 257, для которых, по его мнению, даёт простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным.
Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое имеет вид, указанный в то число является совершенным. Например,
простые числа, и соответственно
| 6 = | (3 · 4)/2 = 1 + 2 + 3, |
| 28 = | (7 · 8)/2 = 1 + 2 + 4 + 7 + 14 |
совершенные числа. Спустя несколько столетий Леонард Эйлер доказал (попробуйте и здесь свои силы), что все чётные совершенные числа имеют вид, указанный Евклидом. Таким образом, вопрос, конечно или бесконечно множество чётных совершенных чисел, свёлся к вопросу, конечно или бесконечно множество простых чисел Мерсенна, то есть к вопросу, реализует ли нашу программу-минимум. Ответ на этот вопрос не известен до сих пор 3 .
Формула (9) также не всегда даёт простые числа, например, если n имеет простой нечётный то p делится на а если n само нечётно, то p делится Таким образом, вместо n в имеет смысл подставлять и степени При n =0 , 2 0 , 2 1 , 2 2 , 2 3 и 2 4 действительно даёт простые числа, и Пьер Ферма, живший в XVII веке, высказал предположение, что и при даёт простое число; в его честь простые числа вида получили название чисел Ферма . Гипотезу Ферма опроверг Эйлер, указавший, что число делится на 641. В настоящее время известно несколько при которых по получаются составные числа, но не найдено ни одного нового простого числа Ферма, отличного от указанных выше.
Простые числа Ферма обнаруживают неожиданную связь с геометрией. Выдающийся немецкий математик Карл Фридрих Гаусс доказал, что правильный можно построить циркулем и линейкой при в том и только том случае, когда p число Ферма 4 . Более общий результат таков: правильный допускает построение циркулем и линейкой тогда и только тогда, когда где p 1 , попарно различные простые числа Ферма.
Скатерть Улама
Формулы (8) и (9) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.
Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.
Возьмём вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что тривиальный задаёт бесконечно много простых чисел, более того, все простые числа, но это неинтересный случай. А что можно сказать о многочлене (где a , b и x натуральные числа)? Ясно, что если a и b имеют общий делитель, отличный то значение многочлена число составное, кратное этому делителю. Случай же, взаимно просты, гораздо менее очевиден.
Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что взаимно просты, то в арифметической прогрессии с первым и встречается бесконечно много простых чисел. Эта гипотеза была доказана лишь в немецким математиком Леженом Дирихле.
Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен его изучал ещё Леонард Эйлер. Этот многочлен принимает простые значения при При его значение составное.
Доказано, что никакой многочлен (отличный, разумеется, от константы) не может иметь в качестве значений только простые числа, но до сих пор не известно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.
Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама 5 . Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль диагонали в пределах, ограниченных на рис. 1 красными линиями это значения некоторого квадратного многочлена с целыми коэффициентами).
| 197 | 196 | 195 | 194 | 193 | 192 | 191 | 190 | 189 | 188 | 187 | 186 | 185 | 184 | 183 |
| 198 | 145 | 144 | 143 | 142 | 141 | 140 | 139 | 138 | 137 | 136 | 135 | 134 | 133 | 182 |
| 199 | 146 | 101 | 100 | 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 132 | 181 |
| 200 | 147 | 102 | 65 | 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 | 90 | 131 | 180 |
| 201 | 148 | 103 | 66 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 56 | 89 | 130 | 179 |
| 202 | 149 | 104 | 67 | 38 | 17 | 16 | 15 | 14 | 13 | 30 | 55 | 88 | 129 | 178 |
| 203 | 150 | 105 | 68 | 39 | 18 | 5 | 4 | 3 | 12 | 29 | 54 | 87 | 128 | 177 |
| 204 | 151 | 106 | 69 | 40 | 19 | 6 | 1 | 2 | 11 | 28 | 53 | 86 | 127 | 176 |
| 205 | 152 | 107 | 70 | 41 | 20 | 7 | 8 | 9 | 10 | 27 | 52 | 85 | 126 | 175 |
| 206 | 153 | 108 | 71 | 42 | 21 | 22 | 23 | 24 | 25 | 26 | 51 | 84 | 125 | 174 |
| 207 | 154 | 109 | 72 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 83 | 124 | 173 |
| 208 | 155 | 110 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 123 | 172 |
| 209 | 156 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 171 |
| 210 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 |
| 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название « скатерть Улама ».
Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена выстраиваются по диагоналям у спирали, начинающейся с (рис. 3).
| 57 | 56 | 55 | 54 | 53 |
| 58 | 45 | 44 | 43 | 52 |
| 59 | 46 | 41 | 42 | 51 |
| 60 | 47 | 48 | 49 | 50 |
| 61 | 62 | 63 | 64 | 65 |
Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.
Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил математического объяснения.
О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.
Экспоненциальный многочлен
Экспоненциальные многочлены отличаются от обычных тем, что в них показателями степени могут быть не только конкретные натуральные числа, но и линейные многочлены от переменных с натуральными коэффициентами, то есть многочлены вида
где a 1 , a 2 , . a k , b целые неотрицательные числа.
Простейшими примерами экспоненциальных многочленов от являются правые части
В дальнейшем мы всегда будем предполагать, что все встречающиеся у нас переменные принимают целые положительные значения.
В 1952 году американский математик Джулия Робинсон 6 опубликовала следующий замечательный результат:
- любое его положительное значение при целых положительных значениях переменных является простым числом;
- любое простое число можно представить в таком виде.
В результате получается такая «формула для простых чисел»:
| p = R ( x 0 , . x k ). | (10) |
Эта формула замечательна вот чем. в неё входят только целые числа, и потому, в отличие от формул Миллса, Райта и им подобных, формула Джулии Робинсон может быть выписана явно. она задаёт все простые числа, а не только избранные из них, в отличие от всех рассмотренных выше формул. хотя задаёт и не только простые числа, у нас есть очень простой способ отсеивания «лишних» чисел: каждое не простое при целых положительных значениях неизвестных не превосходит нуля. Этим формула Джулии Робинсон выгодно отличается от а также и от только что рассмотренных полиномиальных формул 7 .
Доказательство Джулии Робинсон совершенно элементарно. Ниже излагаются его основные идеи; доведение же доказательства до формальной строгости мы оставляем читателям: все промежуточные результаты сформулированы в виде пяти лемм, и нужно доказать. Как мы увидим, из этих лемм следует не только существование экспоненциального но и его явный вид.
Что мы должны сделать?
Чтобы доказать теорему Джулии Робинсон, мы, очевидно, должны указать экспоненциальный такой, что разрешимо в натуральных числах относительно переменных тогда и только тогда, когда выполнено следующее условие:
| p простое число . | (11) |
Это пример условия на переменную p .
Приведём ещё несколько примеров условий на набор переменных
| λ 1 , . λ n , x 0 , . x k . | (11′) |
Если мы потребуем, чтобы набор чисел (11) удовлетворял системе уравнений вида
| F i (λ 1 , . λ n , x 0 , . x k ) = 0 ( i = 1, . s ), | (11″) |
или допустим словесное описание типа: простые числа », или простое число , чётные числа » то тем самым мы из множества всех выделим некоторые , подчиняющиеся наложенному на них условию .
Мы не станем точно определять, условия какого вида являются для нас допустимыми. Приведённое описание примеров условий достаточно для оправдания того способа действий, которым мы в дальнейшем будем пользоваться.
В последующем изложении мы будем различать переменные, называя некоторые из них параметрами , так что деление переменных на параметры и неизвестные у нас является чисто условным.
Если все левые части системы уравнений (11″) являются экспоненциальными многочленами от и решения этой системы ищутся в целых положительных числах, то такая система называется экспоненциально диофантовой ; если обыкновенные многочлены, то система уравнений (11″) называется просто диофантовой .
Уравнение (10) является примером экспоненциально диофантова уравнения относительно переменных p ,
Мы будем говорить, что две системы условий, имеющие одни и те же параметры, эквивалентны друг другу относительно этих параметров, если множество тех значений параметров, при которых имеет решение одна из этих систем, совпадает со множеством тех значений параметров, при котором имеет решение и другая система . (Обратите внимание, что в этом определении ничего не говорится о связи значений неизвестных для наших целей это неважно, эквивалентные в нашем понимании системы могут вообще не иметь общих неизвестных.)
Примером эквивалентных условий относительно могут служить неравенство
λ = (2 x 0 + 1)· x 1 .
Ясно, что каждое из этих условий имеет решение тогда и только тогда, когда принадлежит множеству чисел, не являющихся целыми степенями числа 2.
В этой терминологии наша цель формулируется так: найти экспоненциальный многочлен такой, что условие (10) эквивалентно условию (11) относительно параметра p.
Однако требование, чтобы параметр p стоял только в левой части является, как мы сейчас увидим, излишне жёстким.
Пусть удалось найти экспоненциальный многочлен такой, что экспоненциально диофантово уравнение (условие на p ,
| Q ( p , x 1 , . x k ) = 0 | (12) |
эквивалентно условию (11).
| R ( x 0 , . x k ) = x 0 ·(1 Q 2 ( x 0 , . x k )). | (13) |
Лемма 1 . Если экспоненциальные многочлены R связаны то эквивалентны относительно
Нам достаточно даже найти не уравнение, а хотя бы систему экспоненциально диофантовых уравнений
| Q 1 ( p , x 1 , . , x k ) = 0, |
| · · · · · · · · · · |
| Q l ( p , x 1 , . , x k ) = 0, |
эквивалентную условию (11)
| l | ||
| Q ( p , x 1 , . , x k ) = | ∑ | Q i 2 ( p , x 1 , . , x k ), |
| i =1 |
то система (14) эквивалентна уравнению (12).
Именно поиском системы экспоненциально диофантовых уравнений, эквивалентной мы и будем заниматься.
Что такое простое число?
«Странный вопрос, удивится читатель. Каждый знает, что простое число это число, большее единицы, которое делится только на единицу и на себя». Конечно, это так, но с таким определением работать нелегко ведь оно предполагает, что проверка простоты числа состоит в переборе бесконечного числа потенциальных делителей всех натуральных чисел, и самого числа. Лучше сказать так: является простым, если не делится ни на какое число, и отличное Для наших же целей больше подходит следующее определение: является простым, если и для любого 8
В этом определении нет ограничения и, что более важно, оно позволяет переменное число условий свести в одно условие:
Сделанное замечание позволяет нам написать первую систему условий, эквивалентную относительно
| p = r + 1, s = r !, Н.О.Д.( s , p ) = 1. |
Первое из этих условий имеет искомый вид экспоненциально диофантова (более того, диофантова) уравнения, а третье легко приводится к такому же виду за счёт введения двух новых неизвестных:
Лемма 3 . Условие (17) эквивалентно относительно параметров p , s условию 9
| x 1 · s x 2 · p = 1. | (18) |
Так как уравнение (18) экспоненциально диофантово, то нам осталось лишь найти систему экспоненциально диофантовых уравнений, эквивалентную относительно параметров r и s условию (16).
Как вычислить факториал?
В условие (16) входит r !; этот-то факториал и «мешает» нам. Вспомним, что факториал фигурирует в выражении для биномиальных коэффициентов 10 :
| r ! = | t ( t 1) . ( t r + 1) |
Многочлен, стоящий в числителе, имеет довольно сложную структуру. Попытаемся заменить его более простым а именно, При имеем:
( t r )
t ( t 1) . ( t r + 1)
t 1
t 2
t r + 1
Легко видеть, что
| r ! = | lim t →∞ | t r |
однако эта запись факториала нам ничего не даст, поскольку t , будучи параметром в искомой системе уравнений, сможет принимать любые, сколь угодно большие, но конечные значения. Но мы и не будем переходить к пределу, а воспользуемся целочисленностью r ! из (19) и (20) следует, что при достаточно
Лемма 4 . Формула (21) верна как только
Лемма 4 позволяет преобразовать условие (16) в эквивалентную ему относительно параметров r и s систему (проверьте эквивалентность!)
| ì |
| ï |
| í |
| ï |
| î |
| t = 2 r r +2 , |
| c = ( t r ) , |
| t r = s · c + ( x 3 1), |
| ( x 3 1) + x 4 = c . |
| (22) |
| (23) |
| (24) |
| (25) |
Здесь условия (22), (24) и (25) имеют требуемый вид, и нам остаётся лишь найти систему экспоненциально диофантовых уравнений, эквивалентных условию (23) относительно параметров r , t
Итак, нам осталось «избавиться» от биномиального коэффициента.
Биномиальные коэффициенты
Только что мы использовали выражение биномиальных коэффициентов через факториал; но биномиальные коэффициенты имеют много и других определений. Воспользуемся теперь тем, что
| t | |||
| ( u + 1) t = | ∑ | ( t i ) | u i . |
| i =0 |
Эта формула является определением биномиальных коэффициентов, если рассматривать её как тождество относительно u . Но нам нужно, чтобы u было неизвестной , принимающей в каждом конкретном решении искомой системы лишь одно значение.
| t | ||||
| ( t i ) | ≤ | ∑ | ( t i ) | = (1 + 1) t = 2 t , |
| i =0 |
и, таким образом, если
| u > 2 t , | (28) |
то ( t 0 ) , ( t 1 ) , . ( t t ) это цифры в записи числа в позиционной системе счисления с основанием u . Следовательно, биномиальные коэффициенты однозначно определяются тем условием, что равенство (26) и неравенства (27) и (28) одновременно выполнены хотя бы при одном
Лемма 5 . Условие (23) эквивалентно относительно параметров r , t , c системе условий
| ì |
| ï |
| í |
| ï |
| î |
| u = 2 t + 1, |
| x 5 = u + 1, |
| x 5 t = x 6 u r +1 + cu r + x 7 , |
| x 7 + x 8 = u r , |
| c + x 9 = u . |
(30)
(31)
(32)
(33)
Здесь все условия уже имеют необходимый нам вид.
Итак, мы показали, что условие (11) эквивалентно относительно системе, состоящей из экспоненциально диофантовых (18), (22), (24), (25), Чтобы получить требуемый экспоненциальный многочлен, осталось переименовать s , t , c и u в x 10 , x 11 , x 12 , x 13 , x 14 , объединить по все уравнения в одно и преобразовать по это уравнение к искомому
Дальнейшие шаги
Формула (10) не содержит явно номера задаваемого ею простого числа. Описанный выше способ построения экспоненциального не даёт прямого пути для включения номера простого числа в Используя существенно более сложную технику, Мартин Дейвис, Хилэри Патнам и Джулия Робинсон в 1961 году доказали одну очень сильную теорему, которая имеет такое следствие.
Существует экспоненциальный многочлен такой, что при каждом фиксированном значении и произвольных значениях остальных переменных, принимает ровно одно положительное значение, и этим значением является простое число.
В 1970 году автору этой статьи удалось, используя другие результаты Джулии Робинсон, построить такое диофантово уравнение:
| M ( a , b , c , z 1 , . z m ) = 0, | (34) |
которое разрешимо тогда и только тогда, когда параметры связаны соотношением Этот результат позволяет опустить в формулировке предыдущей теоремы слово «экспоненциальный», то есть позволяет построить многочлен, задающий простые числа. Об этом, однако, мы поговорим в другой раз. Те же читатели, кого заинтересовала подобная тематика и кого не страшат трудности, могут попробовать самостоятельно разобраться в статье автора «Диофантовы множества», опубликованной в журнале «Успехи математических наук», т. XXVII, № 5, 1972 год.
Темы для размышлений
Докажите, что в арифметических прогрессиях и бесконечно много простых чисел.
Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль
начата с некоторого числа u ?
начата с некоторого числа u , и по спирали стоят члены арифметической прогрессии u , u + v ,
Теорема Вильсона утверждает, что если p простое число, то делится Как можно использовать этот результат, чтобы уменьшить число неизвестных в экспоненциальном задающем простые числа?
Постройте экспоненциальный многочлен который задаёт множество полусумм простых , т.е. такой многочлен, что если то оба числа и являются простыми, и наоборот, если и простые числа, то при некоторых
Постройте экспоненциальный многочлен такой, что
если q простое число, то существуют числа такие, что
если q простое число и то простое число, следующее
если q не является простым числом, то всегда
Этот экспоненциальный многочлен даёт « формулу для следующего простого числа ».
Примечания
Здесь и далее [α] обозначает целую часть то есть наибольшее целое число, не назад к тексту
Прочитать об этом доказательстве можно в статье М. И. Башмакова, «Квант», 1971, № 5 , или в заметке С. Б. Стечкина «Простое доказательство теоремы Чебышёва о простых числах» (УМН, 1968, № 5, DjVu, 17 Кб). . назад к тексту
Об истории и современном состоянии исследований по совершенным числам и простым числам Мерсенна вы можете прочитать в статье И. Я. Депмана, «Квант», 1971, № 8 , или в обзорной статье Вальтера Боро «Дружественные числа» из книги «Живые числа» (М., «Мир», 1985, DjVu, 1875 Кб). в книге Р. Грэхема, Д. Кнута и О. Паташника «Конкретная математика» (М., «Мир», 1998) и цитируемую там литературу. . назад к тексту
Подробнее об этом открытии тогда ещё совсем молодого Гаусса рассказано в статье С. Г. Гиндикина, «Квант», 1972, № 1 , или в книге «Рассказы о физиках и математиках» (М., МЦНМО, 2001, PDF, 7275 Кб) того же автора, в главе, посвящённой Гауссу. . назад к тексту
Как было сделано это наблюдение, красочно рассказывает М. Гарднер в «Математических досугах» (М., «Мир», 1972). Вот этот кусочек
В зависимости от расположения целых чисел простые числа могут образовывать тот или иной узор. Однажды математику Станиславу М. Уламу пришлось присутствовать на одном очень длинном и очень скучном, по его словам, докладе. Чтобы развлечься, он начертил на листке бумаги вертикальные и горизонтальные линии и хотел было заняться составлением шахматных этюдов, но потом передумал и начал нумеровать пересечения, поставив в центре 1 и двигаясь по спирали против часовой стрелки. Без всякой задней мысли он обводил все простые числа кружками. Вскоре, к его удивлению, кружки с поразительным упорством стали выстраиваться вдоль прямых. На рис. 203 показано, как выглядела спираль со ста первыми числами [ Это усечённая на два оборота версия вышеприведённого поэтому я его не привожу. Для удобства числа вписаны в клетки, а не стоят на пересечении линий.
Вблизи центра выстраивания простых чисел вдоль прямых ещё можно было ожидать, поскольку плотность простых чисел вначале велика и все они, кроме нечётны. Если клетки шахматной доски перенумеровать по спирали, то все нечётные числа попадут на клетки одного и того же цвета. Взяв (соответствующих 17 простым числам, не превосходящим и расставив их наугад на клетки одного цвета, вы обнаружите, что пешки выстроились вдоль диагональных прямых. Однако не было оснований ожидать, что и в области больших чисел, где плотность простых чисел значительно меньше, те также будут выстраиваться вдоль прямых. Улама заинтересовало, как же будет выглядеть его спираль, если её продолжить до нескольких тысяч простых чисел.
В вычислительном отделе Лос-Аламосской лаборатории, где работал Улам, имелась магнитная лента, на которой было записано простых чисел. Улам вместе с Майроном Л. Стейном и Марком Б. Уэллсом составили программу для вычислительной машины MANIAC, позволившую нанести на спираль последовательные целые числа Получившийся при этом узор (иногда его называют «скатертью Улама») изображён на рис. 204. [ А это уже расширенная версия вышеприведённого поэтому я его привожу. Обратите внимание на то, что даже у края картины простые числа продолжают послушно укладываться на прямые.
| Рис. 204 . Фотографии нарисованного компьютером узора видно, что выстраиваются |
Прежде всего бросаются в глаза скопления простых чисел на диагоналях, но вполне ощутима и другая тенденция простых чисел выстраиваться вдоль вертикальных и горизонтальных линий, на которых все клетки, свободные от простых чисел, заняты нечётными числами. Простые числа, попадающие на прямые, продолженные за отрезок, который содержит последовательные числа, лежащие на витке спирали, можно считать значениями некоторых квадратичных выражений, начинающихся с Например, последовательность простых чисел 5, 19, 41, 71, стоящих на одной из диагоналей на рис. 204, это значения, принимаемые квадратичным трёхчленом равном 0, 1, 2 Из рис. 204 видно, что квадратичные выражения, принимающие простые значения, бывают «бедными» (дающими мало простых чисел) и «богатыми» и что на «богатых» прямых наблюдаются целые «россыпи» простых чисел.
Начав спираль не с 1, а с какого-нибудь другого числа, мы получим другие квадратичные выражения для простых чисел, выстраивающихся вдоль прямых. Рассмотрим спираль, начинающуюся с (рис. 205, слева). Числа вдоль главной диагонали, идущей с на порождаются квадратичным трёхчленом Подставляя положительные значения x , мы получаем нижнюю половину диагонали, подставляя отрицательные значения верхнюю. Если рассмотреть всю диагональ и переставить простые числа в порядке возрастания, то окажется (и это приятный сюрприз), что все числа описываются более простой формулой Это одна из многих «производящих» формул для простых чисел, открытых ещё в XVIII веке великим математиком Леонардом Эйлером. При x , принимающем значения она даёт только простые числа. Следовательно, продолжив диагональ до тех пор, пока она не заполнит мы увидим, что вся диагональ заполнена простыми числами.
Самый знаменитый квадратичный трёхчлен Эйлера, производящий простые числа, получится, если начать спираль с (рис. 205, справа). Этот трёхчлен позволяет получить 40 последовательных простых чисел, заполняющих всю диагональ Давно известно, что из 2398 первых значений, принимаемых этим трёхчленом, ровно половина простые. Перебрав все значения знаменитого трёхчлена, не превышающие 10 000 000, Улам, Стейн и Уэллс обнаружили, что доля простых чисел среди них составляет 0,475. . Математикам очень бы хотелось открыть формулу, позволяющую получать при каждом различные простые числа, но пока такой формулы обнаружить не удалось. Может быть, её и не существует.
| 33 | 32 | 31 | 30 | 29 |
| 34 | 21 | 20 | 19 | 28 |
| 35 | 22 | 17 | 18 | 27 |
| 36 | 23 | 24 | 25 | 26 |
| 37 | 38 | 39 | 40 | 41 |
| 57 | 56 | 55 | 54 | 53 |
| 58 | 45 | 44 | 43 | 52 |
| 59 | 46 | 41 | 42 | 51 |
| 60 | 47 | 48 | 49 | 50 |
| 61 | 62 | 63 | 64 | 65 |
Спираль Улама подняла много новых вопросов, относящихся к закономерностям и случайностям в распределении простых чисел. Существуют ли прямые, на которых лежит бесконечно много простых чисел? Какова максимальная плотность распределения простых чисел вдоль прямых? Существенно ли различаются плотности распределения простых чисел в квадрантах «скатерти» Улама, если считать, что она продолжается неограниченно? Спираль Улама забава, но её следует принимать всерьёз.
Точнее, Робинсон получила чуть более слабый результат, а эту изящную форму придал результату Робинсон впоследствии X. Патнам. назад к тексту
Полиномиальная формула это формула, задаваемая многочленом. назад к тексту
Н.О.Д.( a , b ) это наибольший общий делитель чисел a назад к тексту
Сравните эту лемму с леммой 2 из «Кванта» № 6 за 1972 год, с. 33. назад к тексту
О свойствах биномиальных коэффициентов «Квант» рассказывал неоднократно; см., например, № 6 за 1970 год, или № 2 за 1973 год, книгу Р. Грэхема, Д. Кнута и О. Паташника «Конкретная математика» (М., «Мир», 1998). назад к тексту
алгебра — Определить кол-во простых чисел от 1 до n с математической точки зрения
Здравствуйте. Как определить кол-во простых чисел от 1 до n с математической точки зрения, например от 1 до 10^9.
задан 18 Янв ’14 0:26
Nok
110 ● 5 ● 20
100% принятых
Чтобы найти точно это количество, нужно всё «честно» подсчитать — «обходных» способов тут нет. Но для приблизительной оценки существует асимптотический закон распределения простых чисел. В отрезке от $%1$% до $%n$% таких чисел имеется порядка $%\frac<\ln n>$%. При $%x\to\infty$% отношение числа $%\pi(x)$% (так стандартно обозначается количество простых чисел, не превосходящих $%x$%) к величине $%x/\ln x$% стремится к единице.
(18 Янв ’14 0:33) falcao
Я не до конца понимаю постановку задачи. В частности, мне не ясна роль параметра $%k$%. Что он означает? Хотелось бы «чистого» описания на математическом языке, без «занимательного» сюжета и персонажей (мне трудно отсеивать ненужную информацию). Скорее всего, тут должно работать решето Эратосфена. Более сложных средств в такого рода задачах, как правило, не используется.
(18 Янв ’14 1:19) falcao
Число является простым если оно не делится от 2 до k+1,решето Эратосфена здесь не подходит
(18 Янв ’14 4:10) Nok
Falcao,отвечаю про k. В условии задачи сказано, что год не должен быть простым, а он должен казаться главному герою простым, то есть не иметь простых делителей меньших k+2.Решето Эратосфена в этой задаче здесь не подходит,а вот как в этой задаче можно использовать метод включений-исключений на отрезке с учетом k
(18 Янв ’14 21:15) Nok
@ivan145: роль числа $%k$% я теперь понял. Решето Эратосфена, если я правильно понимаю, не подходит по той причине, что в худшем случае оно требует прохождения массива длиной $%10^9$%, а это считается много. Если это в самом деле так, то напрашивается идея использования формулы включений и исключений. Реализовать её, судя по всему, можно. Я попробую тогда изложить свои соображения.
(18 Янв ’14 21:58) falcao
Отвечаю здесь, так как снизу всё исчерпано. Конечно, никаких произведений порядка $%10^$% здесь в принципе возникнуть не может. Ведь рассматриваются только числа до $%10^9$%, и у них не бывает столь огромных делителей. Я уже говорил, что задача подсчёта для $%[A;B]$% сводится к нахождению разности $%f(B)-f(A-1)$%, то есть параметр в задаче фактически один: число $%n$% от $%1$% до $%10^9$%, для которого мы ищем $%f(n)$%.
(20 Янв ’14 13:55) falcao
Falcao,я все реализовал,не считал те произведения которые больше 2*10^9,на тестах где k маленькое все проходит довольно неплохо,но в худшем случае при k=300,считает 3 секунды.Не может ли у этой задачи быть другого решения?
(25 Янв ’14 10:41) Nok
показано 5 из 7 показать еще 2
2 ответа
Попробую изложить реализацию одного из алгоритмов. Задачу я понимаю так. Нам даны три числа: $%A$%, $%B$% и $%k$%. Требуется найти количество чисел отрезка $%[A;B]$%, которые не делятся ни на одно простое число из отрезка $%[2;k+1]$%. Поскольку $%k$% сравнительно небольшое, мы можем быстро выписать все такие числа, пользуясь решетом Эратосфена. В худшем случае возникает список 2, 3, 5, . 293, в который входят 62 простых числа. Теперь надо реализовать функцию $%f(n)$%, которая подсчитывает количество чисел отрезка $%[1;n]$%, не делящихся ни на одно из указанных. Это будет некая процедура-функция, и далее она дважды вызывается, и вычисляется разность $%f(B)-f(A-1)$%. Число $%n$% может иметь порядок $%10^9$%.
Проблема в том, что пересечений, вообще говоря, имеется очень много, и в общем случае это будет величина порядка $%2^$% (каждое простое число можно брать или не брать, составляя произведение различных простых). Однако у нас тут имеется ограничение чисел по величине, поэтому брать те произведения простых, которые превышают $%10^9$%, нам уже не надо. Соответственно, задача сводится к нахождению эффективного принципа перебора всех произведений различных простых из списка $%p_1,\ldots p_m$%, с условием, что произведение не превышает $%10^9$%.
Сделаем ещё вот какое замечание. Если нам надо подсчитать число $%[n/(st)]$%, то можно это сделать по формуле $%[[n/s]/t]$%, то есть округлять можно после каждого деления. Тогда составляем список чисел $%[n/p_1],[n/p_2],\ldots,[n/p_m]$%. Все эти числа складываем. Про каждое число мы запоминаем, на какое $%p_i$% мы его последний раз делили. Далее $%[n/p_1]$% делим с округлением на числа $%p_2,\ldots,p_m$%; число $%[n/p_2]$% делим с округлением на более «поздние» числа $%p_3,\ldots,p_m$% и так далее; $%[n/p_]$% делим с округлением на $%p_m$%. Все полученные числа вычитаются. И далее повторяем эту процедуру, на каждом шаге меняя вычитание на сложение и наоборот, пока не произойдёт обнуление. Надо заметить, что количество действий тут не должно быть слишком большим: произведение первых 10 простых чисел уже превышает $%10^9$%, то есть делить слишком много раз будет не нужно. У самых больших простых чисел списка вообще берутся только три сомножителя. Судя по всему, этот план должен быть реализуем за предлагаемое время.
отвечен 18 Янв ’14 22:47
falcao
300k ● 9 ● 38 ● 55
@falcao Думаю, что предложенное Вами решение действительно может уложится в ограничение времени. Но «Это будет некая процедура-функция, и далее она дважды вызывается, и вычисляется разность f(B)−f(A−1). Число n может иметь порядок $$10^9$$.» В случае если А и В будут достаточно большими числами, а их разность небольшой, например, А=999999995 и В=999999999, то вместо проверки 4 чисел будут необоснованно дважды вычисляться значения функции для достаточно больших чисел. Уверен, что несколько тестов будут именно такого плана.
(19 Янв ’14 0:18) aid78
Falcao,понял все до замечания.Является ли замечание еще одним способом решения задачи?или это продолжение того,что вы написали ранее?можно поконкретней о чем говорится в замечании.
(19 Янв ’14 8:17) Nok
@aid78: с Вашим замечанием я согласен. Но дело в том, что такого рода соображений может быть много, и они играют роль уже на стадии реализации программы. Она может себя вести как-то по-особому при «малых» значениях $%B$%, или $%B-A$%. У меня в первую очередь речь шла о преодолении чисто математических трудностей для «худшего» случая.
(19 Янв ’14 9:34) falcao
@ivan145: замечание касалось способа вычисления целой части. Вместо $%[n/6]$% можно брать подсчитанное ранее значение $%[n/2]$%, которое далее делим на 3 с округлением вниз и получаем то же самое. Так удобнее реализовать алгоритм. Дальше у меня шло описание основной части, с формулой включений и исключений. Его было бы уместно начать с новой строки, так как это отдельная мысль, хотя и связанная с предыдущей. Фактически, это основной момент в вычислениях. Представьте себе формулу типа $%[n/p_1]+\ldots+[n/p_m]-([n/(p_1p_2]+[n/(p_1p_3)]+\ldots)+([n/(p_1p_2p_3)+\ldots)-$% и далее по тексту.
(19 Янв ’14 9:40) falcao
Ага,это и есть формула включений и исключений,и вы говорите,что здесь можно сделать отсечение,что если произведение превысит 10^9,то уже это необязательно рассматривать.А почему это необязательно рассматривать?и не нарушит ли это итоговый ответ?
(19 Янв ’14 10:00) Nok
@ivan145: представьте себе формулу включений и исключений для этого случая в её полном виде. Если мы поделили $%n$% на очень большое число, то целая часть такого частного равна нулю. Поэтому слагаемые этого вида можно не рассматривать. Мы ведь по формуле $%[n/s]$% подсчитываем количество чисел от 1 до $%n$%, кратных $%s$%, но в случае $%s > 10^9$% таких чисел просто нет.
(19 Янв ’14 10:13) falcao
Да с таким отсечением согласен,но есть проблема.Допустим нам достался худший случай и чисел простых будет 62.И когда (n/(p1p2p3p4p5p6p7p8p9p10)+n/(p1p2p3p4p5p6p7p8p9p11))и т.д. в фор-ле включений и исключений то этот перебор комбинаций займет слишком много времени,если составлять комбинации по 2,3,4,5 то это еще проходит,возможно пройдет и по 6,но когда составляем комбинации из 62 чисел по семь,то тут уже начинаются проблемы.Возможно ли это как-то избежать?
(20 Янв ’14 12:53) Nok
@ivan145: здесь не надо составлять все комбинации (сочетания) из 62 по 7. Учитывать и рассматривать надо только те произведения простых, которые не превосходят $%10^9$%. Их относительно немного, и «отсев» происходит на достаточно ранней стадии. Я показал, как можно осуществить перебор при помощи составления списков. Об этом в последнем абзаце говорится. Суть в том, что «длинных» произведений в списке будет очень мало.