Привет, Хабр! Однажды утром мне пришла в голову идея находить "исключающее ИЛИ" между координатами точки пространства и проверять полученное число на простоту. Результат такого простого алгоритма вы можете видеть на картинке. Подробнее под катом.
Алгоритм генерации узора
Алгоритм на языке C++
long long temp = x ^ y; // x и y координаты точки
// Далее идет проверка temp на простоту одним из алгоритмов.
// Например алгоритм Бэйли-Померанс-Селфридж-Вагстафф (BPSW) проверки n на простоту
if(isprime(temp) == true) {
// рисуем закрашенную точку
} else {
// оставляем точку пустой
}
Такой алгоритм дает следующие бесконечные узоры:
Можно также посмотреть видео с узорами:
Другие варианты узоров
Если заменить операцию XOR (исключающее ИЛИ) на операцию ИЛИ или И, можно получить фрактальные треугольники:
Также можно вместо проверки на простое число использовать любые другие проверки, например деление без остатка на какое-либо число. Но такие варианты дают менее разнообразные узоры.
Программа и исходники
Для тестирования генератора узора я написал простую программу, которую можно скачать вместе с исходниками здесь. Для работы с изображениями используется библиотека OpenCV.
Комментарии (33)
Revetements_Etales
22.07.2018 20:42+1На предпоследней картинке получился треугольник Серпинского, кажется.
synedra
23.07.2018 10:26Кажется, да. А какого, собственно, хрена он там получился?
DjSapsan
23.07.2018 10:52Он генерируется из координат. А дальше просто убираются «непростые» точки. Поэтому издалека выглядит как полноценный треугольник Серпинского. Вблизи же будут видны дырки в линиях.
olgerdovich
23.07.2018 11:47Кажется, он там только кажется.
Мотив есть, но самого его там нет.
Так что, кажется, ни хрена он там не получился на самом-то деле.Sunflower
24.07.2018 01:59Именно. В 1998 будучи сопливым студентом неожиданно получил точно такую картину от программки на асме весом 58 байт. (Исходники до сих пор лежат где-то под кроватью) Долго удивлялся как же так, фрактальные генераторы со сложной математикой, а тут нате вам. Уже после понял что не фрактал там, всего лишь его призрак.
DanilinS
22.07.2018 22:30-1А смысл данной работы? Математическое обоснование, практическое применение…
Manlok
24.07.2018 01:59Вы про то, почему так получается и как можно использовать, или «это всё баловство, идите чем-нибудь полезным займитесь»?)
Если первое, то практическое применение ограничивается только фантазией (хотя первое что приходит в голову — да, дизайн и красивые картиночки). Хотя про причины и правда хотелось бы почитать побольше, ни здесь, ни в посте, приведённом в соседнем комментарии, эта тема почти не раскрыта.
А если второе, то зря Вы так.DanilinS
24.07.2018 08:49Наверно не совсем я ясно выразился.
Имелось в виду:
1) Чем обусловлен узор? Почему узор именно такой, а не иначе? Его можно как-то описать математически? Без поиска простых чисел.
2) Данный узор можно использовать для предсказания простых чисел? Или для ускорения генерации пар ключей?
fshp
23.07.2018 06:15Ищите оси симметрии. К примеру главная диагональ является осью симметрии из-за коммутативности побитовых операций.
Исключите симметричные области и узоры станут не такими уж и красивыми.synedra
23.07.2018 10:49Главная-то понятно, а вот верно ли, что OR(x, y) = OR(x+na, y), где a-константа, или что OR(x, y+n) = OR(y, x+n) для определённого множества n? Что это за множество? Такое ощущение, что в первом случае n<y/a, но не уверен.
Для prime(OR) это очевидно верно, а вот для самих значений не знаю.
fshp
24.07.2018 07:20Для начала я бы прорядил плоскость.
Для любых n и m и любых нечётных x и y
isPrime(2n | 2m) == false isPrime(n & 2m) == false isPrime(x ^ y) == false
denis-19
23.07.2018 07:35Архитекторам или дизайнерам можно предложить в реализацию — очень они любят стены новых домов и внутри парадных украшать на рендере разные красивые арты.
Так же как рисунки для обоев (бумажные которые на стены) красиво, но нужно играться с цветами и фоном.
Deosis
23.07.2018 08:28Стоит сделать версию с некоммутативной операцией (например, импликация) и посмотреть, как будут выделяться диагонали в ней.
dext63r
23.07.2018 13:21Меня фракталы всегда завораживали:
Kaputmaher
25.07.2018 01:56Передача про фракталы 20-летней давности при участии фантаста Артура Кларка
Gonzales451F
23.07.2018 16:45-1X^Y по определению не простое число (если только одно из них не единица). Поправьте меня если я не прав Ж-)
arTk_ev
24.07.2018 00:45а какой математический смысл XOR координат? По сути это просто исключение диагоналей
fpr
25.07.2018 07:41-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 У нас есть две спирали в разных направлениях. Но я дал многим информацию, я не в состоянии математически утверждать, что это отношение правильное. Я протестировал его на компьютере. А исследования простых чисел идут в области исследования гиперкубов и гиперсфер.
Igor_ku
Не перестану удивляться бесконечности людской фантазии :) Только после прочтение остается странное чувство, что-то вроде вопроса "… и?". Хоть и интерессный факт описанный в статье.
ELEKTRO_YAR Автор
Я думаю использовать в 2д игре для генерации строений «инопланетян». Может быть есть другое интересное применение.
deniskreshikhin
Cтранно что это надо кому-то объяснять.
Вы большой молодец. Тема очень полезная, даже вот Кубрик что-то такое использовал в Space Odyssey для визуалиации beyond the infinite. https://www.youtube.com/watch?v=ebmwYqoUp44
sidorares
Это «rule 30» — blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covered-in-rule-30s
deniskreshikhin
Хех, точно)