Пару слов о взаимно простых числах

xcont · Сообщение **xcont** » 20 авг 2013, 13:14

Паттерн

В 2002 году придумал интересную штуку. 14 лет тогда было. Размышлял о фракталах и теории хаоса, а учиться не хотел. Учиться не хотел, а в школу ходить заставляли. Придумал способ убить время на скучных уроках по истории, географии и прочей гуманитарии. Попробую объяснить подробно. Все, что нам нужно - листок в клетку и карандашик. Если листка в клетку нет в наличии и карандашик тоже отсутствует - онлайн версия на javascript [url=http://xcont.com/pattern.html]http://xcont.com/pattern.html[/url]

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

Выделяем прямоугольную область и пускаем из угла "квантовый луч" (так я его называл в 2002 году - сильно за терминологию не ругайте). Луч отражается от стенок и пропадает в другом углу.

Если соблюдаются определенные условия (об этом дальше) - получается фрактальный (об этом тоже дальше) узор-паттерн.
Если условия не соблюдаются (очевидный например - стороны прямоугольника равны) - узор не получается. Из менее очевидных напримеров - узор так-же не получается, если размеры сторон имеют общий делитель. Фактически, узоры получаются только если размеры обоих сторон - взаимно простые числа взаимно простые числа.

Наглядно (и кликабельно):

кстати, все сделано вручную, по пикселям в Paint

На картинке все числа от 1 до 30.

А теперь немного о Фибоначчи и фракталах.

Все узоры представляют из себя фракталы.

От чего зависит узор?

А потому, что нужно, чтобы разница тоже была простым числом (наиболее большим), его разница с числами тоже была простой и не маленькой, и т.д., тогда будет что-нибудь интересное.

Что наводит нас на мысль - а если попробовать числа Фибоначчи? Пацан сказал - пацан сделал.

Закрашивал в Paint самые большие замкнутые области.

233х144:

987х610 (скукожил в 5 раз):

233х144 и 987х610 - идентичны

Фракталы, как они есть.

Что еще можно из этого сделать

1. Попробовать не прямоугольную область, а скажем элипс.
2. Попробовать сделать в трех измерениях.
3. Обнаружить другие интересные зависимости между числами и рождаемым ими фракталом.

На хабре: [url=http://habrahabr.ru/sandbox/68846/]http://habrahabr.ru/sandbox/68846/[/url]

P.S.

И немножко шизофрении 11-ти летней давности:

Тогда размышлял, о соотношениях хаоса и порядка, откуда в хаосе берется порядок, и в порядке - хаос. Так вот была тогда мысль, что когда все взорвалось (большой взрыв, в который я свято верил), был луч электромагнитной энергии который в начале бегал в маленьком пространстве (которое далее расширялось). Поскольку электромагнитные волны можно представить в виде квантов - этот луч не непрерывный. Там где мы видим пересечения электромагнитных волн - там появляется "материя" ([url=http://ru.wikipedia.org/wiki/Рождение_пар]http://ru.wikipedia.org/wiki/Рождение_пар[/url]) в виде фрактальных узорчиков. Так из хаоса рождается порядок.

(2) у пространства нет кванта расстояния - поэтому нет общих делителей. Всегда получается узор (то, что мы называем материей).
(1) вселенная расширяется непрерывно и плавно. Узорчик непрерывно (и тоже плавно) переходит из одного в другой - то, что мы называем движением материи.

Ну и еще выводы:
1. Вселенная не двухмерная, а трехмерная (а с точки зрения Общей Теории Относительности - четырехмерная).
2. Опять-же, с точки зрения ОТО - вселенная - не прямоугольная. Топологически, вселенную можно представить в виде тора.
Поэтому узорчики на порядок сложнее.

Идентичный паттерну 4х3:

bot · Сообщение **bot** » 20 авг 2013, 16:14

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

С взаимной простотой тоже всё ясно - китайская теорема об остатках работает: для взаимно простых $$p$$

и

числа $xp+yq, x=0,1,\ldots, p-1, y=0,1,\ldots, q-1$
исчерпывают без повторений все числа от $$0$$

до

.

Что касается связи с хаосом, порядком, ОТО и может быть СТО - это уже плод разыгравшегося воображения, не более обоснованный чем вырезание ножницами бумажных снежинок.

xcont · Сообщение **xcont** » 20 авг 2013, 22:36

bot писал(а):Source of the post Что касается связи с хаосом, порядком, ОТО и может быть СТО - это уже плод разыгравшегося воображения, не более обоснованный чем вырезание ножницами бумажных снежинок.

Так ведь:

xcont писал(а):Source of the post шизофрении 11-ти летней давности

xcont · Сообщение **xcont** » 21 авг 2013, 01:46

bot · Сообщение **bot** » 21 авг 2013, 04:06

bot писал(а):Source of the post
С взаимной простотой тоже всё ясно - китайская теорема об остатках работает: для взаимно простых и числа $xp+yq, x=0,1,\ldots, p-1, y=0,1,\ldots, q-1$
исчерпывают без повторений все числа от до .

Слегка ( ) прокосячил.
1. Вместо $$xp+yq$$

надо взять $$xq+yp$$

.
2. Исчерпывают все по модулю $$pq$$

3. Всё это имеет слабое отношение к обходу таблицы.

Вот обход таблицы с перелётом и без пропусков $\left\{ \begin{matrix}x=n-p\left\lfloor\frac{n}{p}\right\rfloor\\ y=n-q\left\lfloor\frac{n}{q}\right\rfloor\end{matrix}\right.$

C отражением от стенок чуток сложнее $\left\{ \begin{matrix}x=\frac{p-1}{2}+(-1)^{\lfloor\frac{n}{p} \rfloor}\left(n-p\left\lfloor\frac{n}{p}\right\rfloor-\frac{p-1}{2}\right) \\ y=\frac{q-1}{2}+(-1)^{\lfloor\frac{n}{q} \rfloor}\left(n-q\left\lfloor\frac{n}{q}\right\rfloor-\frac{q-1}{2}\right)\end{matrix}\right.$

Чтобы перепрыгивать через клетку надо в этих формулах взять $$2n$$

вместо

.
Связь с КТО (китайской теоремой об остатках) здесь простая - декартово прозведение $\mathbb Z_p$ и $\mathbb Z_q$ при взаимно простых $$p$$

и

изоморфно $\mathbb Z_{pq}$ . В первой формуле с перелётом как раз легко увидеть элементы декартового произведения, ну а во второй эти элементы просто перечисляются в другом порядке.

Андрей А.

xcont писал(а):Source of the post
Топологически, вселенную можно представить в виде тора.

Мысль о взаимно простых границах мироздания озадачила. Хотя, с бубликом - это уже не такая тяжелая мысль.

Sonic86 · Сообщение **Sonic86** » 28 авг 2013, 16:52

Поскольку рисовать узор отображением $k\to (k\bmod p, k\bmod q)$ показалось естственнее (т.е. без отражения от стенок, противоположные стенки отождествлены, луч двигается в одну сторону), потому и попробовал. Ан нет. Получается некрасиво - рисуются куски прямых только под одним наклоном, плоскость не распадается в узор, максимум - режется на косые полоски.

Пусть $$p,q$$

- длина и ширина прямоугольника, $$p<q$$

.

- узор. Как доказать, что луч проходит через каждую точку при $\gcd(p,q)=1$ ?

bot писал(а):Source of the post Чтобы перепрыгивать через клетку надо в этих формулах взять вместо .
Связь с КТО (китайской теоремой об остатках) здесь простая - декартово прозведение $\mathbb Z_p$ и $\mathbb Z_q$ при взаимно простых и изоморфно $\mathbb Z_{pq}$ . В первой формуле с перелётом как раз легко увидеть элементы декартового произведения, ну а во второй эти элементы просто перечисляются в другом порядке.

Это следует отсюда?

Поигрался со скриптом. Сколько существует семейств узоров при $\gcd(p,q)=1$ ?

bot · Сообщение **bot** » 29 авг 2013, 04:58

Sonic86 писал(а):Source of the post
Это следует отсюда?

Да, пусть

и

- образующие циклических групп взаимно простых порядков $$p$$

и

соответственно. Тогда при $\gcd (p, q)=1$ элемент $$ab$$

будет образующим в декартовом произведении. По сути это КТО и есть.

xcont · Сообщение **xcont** » 17 сен 2013, 12:46

Пользуясь гугль-транслейтером налепил сайтик об этом фрактале: New kind of fractals - Fractals in relatively prime integers (coprime integers)
Перевод весьма корявый. Кто может откорректировать? Буду весьма признателен. :rolleyes:

xcont · Сообщение **xcont** » 22 сен 2013, 23:32

Отправил на Хабру: Фракталы в простых числах Habrahabr.ru

yourdomain.com