Бесконечный узор на основе простых чисел

    image

    Привет, Хабр! Однажды утром мне пришла в голову идея находить "исключающее ИЛИ" между координатами точки пространства и проверять полученное число на простоту. Результат такого простого алгоритма вы можете видеть на картинке. Подробнее под катом.

    Алгоритм генерации узора


    Алгоритм на языке C++

    long long temp = x ^ y; // x и y координаты точки
    // Далее идет проверка temp на простоту одним из алгоритмов.
    // Например алгоритм Бэйли-Померанс-Селфридж-Вагстафф (BPSW) проверки n на простоту
    if(isprime(temp) == true) { 
    // рисуем закрашенную точку
    } else {
    // оставляем точку пустой
    }
    

    Такой алгоритм дает следующие бесконечные узоры:

    Картинки с узорами
    image
    image
    image
    image
    image
    image

    Можно также посмотреть видео с узорами:



    Другие варианты узоров


    Если заменить операцию XOR (исключающее ИЛИ) на операцию ИЛИ или И, можно получить фрактальные треугольники:

    image

    image

    Также можно вместо проверки на простое число использовать любые другие проверки, например деление без остатка на какое-либо число. Но такие варианты дают менее разнообразные узоры.

    Программа и исходники


    Для тестирования генератора узора я написал простую программу, которую можно скачать вместе с исходниками здесь. Для работы с изображениями используется библиотека OpenCV.
    Поделиться публикацией
    Комментарии 35
      +1
      Не перестану удивляться бесконечности людской фантазии :) Только после прочтение остается странное чувство, что-то вроде вопроса "… и?". Хоть и интерессный факт описанный в статье.
        +4
        Я думаю использовать в 2д игре для генерации строений «инопланетян». Может быть есть другое интересное применение.
      +3
      На предпоследней картинке получился треугольник Серпинского, кажется.
        0
        Кажется, да. А какого, собственно, хрена он там получился?
          0
          Он генерируется из координат. А дальше просто убираются «непростые» точки. Поэтому издалека выглядит как полноценный треугольник Серпинского. Вблизи же будут видны дырки в линиях.
            0
            Кажется, он там только кажется.
            Мотив есть, но самого его там нет.
            Так что, кажется, ни хрена он там не получился на самом-то деле.
              0
              Именно. В 1998 будучи сопливым студентом неожиданно получил точно такую картину от программки на асме весом 58 байт. (Исходники до сих пор лежат где-то под кроватью) Долго удивлялся как же так, фрактальные генераторы со сложной математикой, а тут нате вам. Уже после понял что не фрактал там, всего лишь его призрак.
            0
            "… фрактальные треугольники..." Автор это и подразумевал.
            –4
            А смысл данной работы? Математическое обоснование, практическое применение…
              +2
              habr.com/post/117160 тут, например, побольше и того и другого
                0
                Это классика!
                0
                Вы про то, почему так получается и как можно использовать, или «это всё баловство, идите чем-нибудь полезным займитесь»?)
                Если первое, то практическое применение ограничивается только фантазией (хотя первое что приходит в голову — да, дизайн и красивые картиночки). Хотя про причины и правда хотелось бы почитать побольше, ни здесь, ни в посте, приведённом в соседнем комментарии, эта тема почти не раскрыта.
                А если второе, то зря Вы так.
                  0
                  Наверно не совсем я ясно выразился.
                  Имелось в виду:
                  1) Чем обусловлен узор? Почему узор именно такой, а не иначе? Его можно как-то описать математически? Без поиска простых чисел.
                  2) Данный узор можно использовать для предсказания простых чисел? Или для ускорения генерации пар ключей?
                +1

                Ищите оси симметрии. К примеру главная диагональ является осью симметрии из-за коммутативности побитовых операций.
                Исключите симметричные области и узоры станут не такими уж и красивыми.

                  0

                  Главная-то понятно, а вот верно ли, что OR(x, y) = OR(x+na, y), где a-константа, или что OR(x, y+n) = OR(y, x+n) для определённого множества n? Что это за множество? Такое ощущение, что в первом случае n<y/a, но не уверен.


                  Для prime(OR) это очевидно верно, а вот для самих значений не знаю.

                    0

                    Для начала я бы прорядил плоскость.
                    Для любых n и m и любых нечётных x и y


                    isPrime(2n | 2m) == false
                    isPrime(n & 2m) == false
                    isPrime(x ^ y) == false
                  0
                  Архитекторам или дизайнерам можно предложить в реализацию — очень они любят стены новых домов и внутри парадных украшать на рендере разные красивые арты.
                  Так же как рисунки для обоев (бумажные которые на стены) красиво, но нужно играться с цветами и фоном.
                    0

                    Стоит сделать версию с некоммутативной операцией (например, импликация) и посмотреть, как будут выделяться диагонали в ней.

                      +1
                      Скатерть Улама 2.0
                        +1
                        if(isprime(temp) == true)

                        if(isprime(temp))
                        не работает?
                          +1
                          Пошел себе заказывать свитер с таким узором.
                            +3
                            Меня фракталы всегда завораживали:
                            image
                              0
                              Передача про фракталы 20-летней давности при участии фантаста Артура Кларка
                              –2

                              X^Y по определению не простое число (если только одно из них не единица). Поправьте меня если я не прав Ж-)

                                +4
                                Оператор ^ в javascript означает побитовое исключающее ИЛИ, а не возведение в степень. Если бы вы читали пост с самого начала, вы могли бы до этого догадаться сами.
                                  0
                                  и не только в javascript
                                –1
                                а какой математический смысл XOR координат? По сути это просто исключение диагоналей
                                  –1
                                  Прежде всего, извиниться за машинный перевод. Я не говорю по-русски, я могу читать, но не говорить.

                                  Интересная, но в то же время сложная математическая область. Все, что включает простые числа. Очень интересные закономерности, но в моем случае уже известные. Фрактальность исходит от бинарных операторов. С приращением натуральных чисел и бинарных операторов„And“ операотр, например, у нас есть обычный треугольник серпинского. Эта тема, как уже было сказано, нуждается в анализе со многими другими дисциплинами. Вольфрамов „new kind of science book“ хорошая область для сравнения. Фрактальная геометрия. Но из моих частных исследований о простых числах все, что имеет потенциал для решения простых чисел, — это спираль квадратного корня и на самом деле очень особая ее часть. Это взаимное суммы квадратных корней из неперекрывающийся точки 17,54,110,186,281… Эта обратная сумма стремится к одной новой константе порядка 0,112722393… Я назвал его" tsi " (Теодор спиральных пересечений), но это не важно и правильно из-за „неперекрывающийся точки“. Самое интересное заключается в сочетании с постоянными, так называемый Prime-постоянной от mathworld mathworld.wolfram.com/PrimeConstant.html с p = 0,41468250985111166… и самая популярная постоянная Эйлера e=2,7182… Мое подозрение:

                                  Я утверждаю, что он строит следующее отношение (e*P)/tsi = 10. Да 10 круглое. Это открыто для многих интерпретаций. После долгих исследований я думаю, что из-за 10 = 2*5 У нас есть две спирали в разных направлениях. Но я дал многим информацию, я не в состоянии математически утверждать, что это отношение правильное. Я протестировал его на компьютере. А исследования простых чисел идут в области исследования гиперкубов и гиперсфер.
                                    –1
                                    Простите, я — начинающий питонист, решил реализовать эту вещь на python. Но есть проблема — приходиться долго ждать, целых 10 секунд!!11! И я не знаю как сделать перемещение по осям. Вот ссылка: pastebin.com/d4zKX3uw
                                      0

                                      Это история о том как потерять кучу процессорного времени на пустом месте...


                                      def is_prime(num):
                                          for i in range(2, num):
                                              if num % i == 0:
                                                  return False
                                          return True

                                      Во-первых, перебирать делители нужно до квадратного корня из num, а не до num — это уже ускорит программу до секунды. Во-вторых, поскольку вы в цикле вызываете is_prime кучу раз — нужно не проверять их по одному, а воспользоваться Решетом Эратосфена.

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

                                    Самое читаемое