Как–то в детстве читал какую–то книгу из серии «занимательная математика», или программирование? Там был рассказ про одного математика, имя которого я уже и не вспомню, который сидел на какой–то конференции и сильно скучал. Да, не всегда на конференциях бывает интересно, а на математических и подавно. И вот, находясь в скучающем расположение духа этот математик, написал посреди листа в клеточку число 0, справа от него 1, выше единицы число 2, слева двойки — 3. И так по спирали продолжал записывать все числа по порядку, когда дошел до сотни ему это занятие наскучило. Тогда он стал в этой спирали зачеркивать простые числа (для гуманитариев напоминаю, что простое – это число, которое делится только на 1 и на само себя). Так вот, этот математик предавался сему нехитрому занятию и тут заметил, что простые числа, которые он зачеркивал ложатся по прямым линиям.
И в этой книге (скорее всего по программированию), предлагалось написать алгоритм, делающий то–же самое, то есть рисующий на месте простых чисел черные точки.

Тут следует заметить, что простые числа ничего общего с простотой не имеют. Нет вменяемых формул (кроме простых чисел в особой форме) по которым можно в общем случае проверить простоту числа и так далее…

И вот я, тоже от нечего делать, по прошествии 15 лет, после пары бутылок темного чешского козла, решил это дело реализовать. Итак встречайте: 168100 чисел, из них 15173 простых.

Если у вас глядя на это внезапно назреет вопрос о жизни, вселенной и остальном, то ответ могу дать сразу – 42.

наука на научном форуме  410x410, 41.58 kb

Tagged with →  

28 Responses to Простые числа. (UPD спирали Сакса)

  1. AgiMega:

    Возможно, в возникновении таких диагоналей каким-либо образом участвуют числа-близнецы.

  2. ZvnRain:

    Вставлю свои пять копеек.
    1) Математика звали Станислав Улам.
    2) Его идея с наглядным изображением простых чисел получила интересное продолжение — так называемую спираль Сакса, Ей посвящен сайт, на котором можно прочитать о разных особенностях этого способа изображения простых чисел, также на этом сайте есть небольшая программа под windows, чтобы самостоятельно попробовать разные закономерности, связанные с этой спиралью.
    3) На этой странице есть код на языке программирования питон, который позволяет строить спирали Сакса внушительных размеров, её автор сделал для интересующихся спирали из ста тысяч и из миллиона натуральных чисел. Будучи распечатанными на листе большого формата, они выглядят превосходно.
    4) Насчет формул. Действительно, нет алгоритмов, проверяющих, что число простое, но есть те, которые позволяют точно удостовериться, что оно не составное. Наиболее употребимый на сегодняшний день алгоритм, выполняемый за полиномиальное время это тест Агравала-Каяла-Саксены. Он сделан для общего случая, для особых простых чисел вроде Мерсенновских есть специальные тесты, которые работают куда быстрее. Ну и, конечно, если не требуется детерминистический алгоритм, то тоже можно посчитать быстрее.
    5) Первые пятнадцать миллионов простых чисел посчитаны. Ну, чтобы не тратить время на составление списка В этой области вообще силён дух соревнования: кто найдёт самое большое на сегодняшний день простое число. Пальму первенства удерживают числа Мерсенна, из-за того, что их очень удобно проверять. Люди годами держат компьютеры включенными, чтобы объегорить других таких же энтузиастов. Есть даже приличные денежные призы, с ума сойти!
    6) Существуют формулы, которые позволяют получить все простые числа, один из вариантов содержит систему из 14 диафантовыцх уравнений с 26 переменными. Так что простые числа, как верно подметил автор поста, на поверку совсем не просты.

  3. Akhef:

    А если поиграть с образующим паттерном?
    Например, попытаться уложить их в шестигранники?

  4. Odaam:

    : А пофиг. Каждая прямая соответствует какой-то последовательности типа n2-n+1 ; такие могут проявляться и в шестиугольнике. А в кубе может проявиться что-то другое.

  5. Snuno:

    Представляю, что бы было, если бы люди, что изначально придумали писать в прописи, использовали бы разлинованную бумагу с соотношением сторон 1:1,618 (случайно, к примеру), и это дошло бы до наших дней.

  6. KyySwet:

    О! Раз тут разговор зашел про гуманитариев, объясните пожалуйста смысл сакральный смысл в эпизоде про простые числа в Криптоминиконе Нила Стивенсона. Там где Уотерхауз заставил переименовать подразделение 2701 в 2702

  7. Daasuper:

    : нету в числах сакрального смысла, пока ты сам не начнешь приписывать числу магические свойства.

  8. AgiMega:

    :
    — Потому что, — отвечает Уотерхауз, — 2701 это произведение двух простых чисел, 37 и 73, которые, будучи записаны в десятичной системе, представляют собой, как вы легко можете видеть, взаимную перестановку цифр.
    Все лица обращаются к ученому, который явно пристыжен.
    — Это лучше исправить, потому что именно такие вещи может заметить Рудольф фон Хакльгебер. — Он встает, вынимает из кармана авторучку с золотым пером и переправляют 2701 на 2702. Уотерхауз оглядывает собравшихся и приходит к выводу, что все довольны. Очевидно, именно таких салонных фокусов от него и ждут.

  9. KyySwet:

    : Это я прочел уже 3 раза — не считая твоего комментария. Вопрос в другом — что именно поймет фон Хакльгебер, заметив «произведение простых чисел»?

  10. ThgSpb:

    Я четко вижу в центре свастику.

  11. Peeen:

    : Позволь поправить.

    Действительно, нет алгоритмов, проверяющих, что число простое …

    Нет. Таких алгоритмов полно. Самый простой «перебрать все делители», только он уж больно неэффективен.
    Упомянутый тобой тест АКС — полиномиальный алгоритм проверки простоты.

    Наиболее употребимый на сегодняшний день алгоритм

    Нет. АКС медленный, и поэтому имеет чисто теоретическую ценность. На практике, для проверки простоты всегда используются быстрые приблизительные методы.

  12. Yeken:

    : «перебрать все делители» — это один из первых известных алгоритмов («решето Эратосфена»), но его сложность O(n log log n), что не есть айс.

  13. Peeen:

    : Решето Эратосфена — это уже слегка другой алгоритм. Как и в случае простого перебора делителей, сложность его экспоненциальна (т.к. в данном случае принято за n брать размер числа в битах).

  14. ZvnRain:

    : Я, конечно, неверно сказал, имея в виду, что до сих пор нет удобоваримых алгоритмов для проверки собственно простоты числа. Тест Миллера-Рабина, на который ты намекаешь, хоть и быстрый, но может показать, что число составное, но не что оно простое. Кроме того, он не подходит для того случая, когда нужен точный результат.

  15. Peeen:

    : нет удобоваримых алгоритмов для проверки собственно простоты числа

    «Удобоваримый» в плане «понятный и простой»? Таких нет, да, но это не сильно мешает.

    не подходит для того случая, когда нужен точный результат.

    Это только с точки зрения теоретиков так. На практике всегда нужен точный результат (классический пример — шифрование с открытым ключом), и тем не менее всегда используется Миллер-Рабин (или один из схожих тестов).

  16. RetSnow:

    Всё замечательно, но откуда может браться явно неслучайная структура на рисунке?

  17. ZvnRain:

    : если попросту, то вы видите наглядное изображение разных числовых последовательностей, в некоторых из которых простых чисел много, а в некоторых нет вовсе.

  18. EhzTunes:

    : Просто обратит ненужное внимание.

  19. AgiMega:

    : разложение числа на простые множители и перестановки — операции, которые часто используется в криптографии, соответственно, числа 37 и 73, которые являются перестановкой друг друга, а в произведении дают номер подразделения, могли бы привлечь внимание пытливого ума немецкого математика.

  20. Phpnode:

    : Перебор делителей — это банальный алгоритм, когда ты все числа до корня заданного перебираешь и проверяешь делимость. Он за O(sqrt(n)) работает.

  21. YksLt:

    обьясните для не далеких приниц заполнения клеточек, хотя-бы до 20. я дальше 4ки не понял принципа

  22. Tcunode:

    : 2 — делиться на себя и на еденицу. Больше собственно не на что делить.
    3 — на 2 не делиться, значит простое
    4 — делиться на 2, значит не простое
    5 — на 2, 3 и 4 не делиться — простое
    6 — делиться на 2 и на 3, не простое
    7 — не делиться на 2, 3, 4, 5, 6 — простое
    8 — делиться на 2, 4 — не простое
    9 — делиться на 3 — не простое
    10 — делиться на 2 и 5 — не простое
    11 — на 2, 3, 4, 5, 6, 7, 8, 9, 10 не делиться — простое
    12 — делиться на 2, 3, 6 — не простое
    13 — на 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 не делиться — простое
    14 — делиться на 2, 7 — не простое
    15 — делиться на 3, 5 — не простое
    16 — делиться на 2, 4, 8 — не простое
    17 — на 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 не делиться — простое
    18 — делиться на 2,3,6, 9 — не простое
    19 — на 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 не делиться — простое
    20 — делиться на 2, 4, 5, 10 — не простое.

  23. RetSnow:

    : Ну да, я спустя сутки понял о чем вы. Но почему в некоторых последовательностях, которые образуются по диагонали, повышенный шанс нахождения простого числа? Почему вниз и вправо от единицы идут явные белые полосы без простых чисел. Хотя это вроде понятно, там небось всегда четные числа получаются. Но первый вопрос остается открытым. Не вижу ни одной причины чтобы было именно так.

  24. YksLt:

    : ага. тупанул я. спасибо

  25. ZvnRain:

    : хм, попробую объяснить. Для начала вот небольшой кусок этой спирали вокруг единицы, чтобы понять, как её строить:

    image

    Если вы посмотрите на картинке в посте на линию, уходящую направо от единицы (на самом деле она идёт со сдвигом небольшим), то увидите, что все числа на ней образуются определенными видами многочленов, а именно: 4t2+2t+n и 4t2+4t-n, где t — это номер витка спирали, а n — натуральные числа. Когда выполняются оба условия, простых чисел на этой линии не может получиться. Вниз от единицы, тоже со сдвигом, идёт линия чисел, которая задаётся формулами 4t2+2t-n и 4t2+n, на ней тоже нет простых.

    А есть многочлены, которые будут давать относительно много простых чисел, например знаменитый многочлен Эйлера P(n)=n2-2+41. Вот он на нашей картинке, образует одну из диагонально пролегающих линий:

    image

  26. ZvnRain:

    : неверно написал, P(n)=n2–n+41 правильно.

Добавить комментарий

Ваш e-mail не будет опубликован.