Хабрахабр

Фракталы в иррациональных числах

Статья является продолжением моей первой статьи «Фракталы в простых числах».

В этой статье покажу фрактальную природу числа $\sqrt$.
Без предисловия. В предыдущей статье мы научились рисовать самоподобные паттерны с помощью взаимно простых чисел. Под кат.

В математике, описанные ниже системы называют бильярдами. Определимся с терминологией и обозначениями. Размеры прямоугольного бильярда будем обозначать через $M$ (ширина) и $N$ (высота). Далее будем использовать этот термин.

Двоичный бильярд.

В предыдущей статье мы брали прямоугольный бильярд со сторонами $M$ и $N$, запускали в него шар и отмечали траекторию пунктирной линией через клетку:

Для взаимно простых $M$ и $N$ получаем паттерн:

В двоичной версии, траекторию отмечаем не пунктирной линией, а закрашивая поочередно клетки, черным и белым цветом (формируем двоичный массив, в соответствующую ячейку помещаем 0 для черного и 1 для белого):

Правила отражений на границах:

Для взаимно простых $M$ и $N$ траектория проходит через каждую клетку:

Для разных M и N

Если стороны имеют общий делитель — тогда шар попадает в угол до того, как пройдет через каждую клетку:

Этот случай удобно рассматривать, как бильярд в прямоугольнике со сторонами $\frac{M}{НОД}$ и $\frac{N}{НОД}$ (НОД — наибольший общий делитель):

Прежде чем двигаться дальше, заполним таблицу предложенную пользователем Captain1312 в его статье (стороны бильярда будем делить на НОД).

$(1, 0)$ бит

Для каждого бильярда $M$ и $N$ возьмем бит с координатами $(1, 0)$.

В этом случае берем инвертированный бит с координатами $(0, 1)$. Если $M$ является делителем $N$ — тогда бит с координатами $(1, 0)$ отсутствует ($\frac{M}{НОД}=1$).

Начало координат — левый верхний угол. Заполняем таблицу. Для каждого бильярда отмечаем бит $(1, 0)$, или инвертированный бит $(0, 1)$ (к этой теме вернемся ниже). По $x$ — ширина бильярда $M$, по $y$ — высота $N$.

Немного о числах Фибоначчи

Двоичная последовательность.

Для взаимно простых $M$ и $N$, траектория шара проходит через каждую клетку. Почему мы инвертировали бит в тех случаях, когда ширина бильярда $M=1$? Между верхней и левой стенкой бильярда, шар каждый раз проходит четное количество клеток.

Нулевой бит не берем — с него начинается траектория: Биты в левом столбце — инвертированные биты из верхней строки.

Кроме того, мы можем смело выкинуть каждый второй бит из этой последовательности (бит $2_{n-1}$ — инвертированный бит $2_{n}$):

Последовательность уникальная для каждого $M$ и $N$. Получили последовательность $1010010110$ для бильярда $(21,13)$.

От верхней стенки, движение всегда начинаем с «0» бита (черная клетка) и заканчиваем «1» битом (белая клетка): Какую бы высоту $N$ мы не взяли — шар всегда проходит траекторию $2N$ между двумя отражениями от верхней стенки.

На картинке траектория шара отмечена черным, если шар двигался вправо и белым — если двигался влево: Фактически, последовательность (которую мы выделили выше — $1010010110$) показывает, с какой стороны прилетел шар: 1 — если шар прилетел, отразившись от правой стенки и 0 — если шар прилетел, отразившись от левой стенки.

Это интересно

С помощью бильярда можно делить два числа в двоичной системе счисления. В момент касания верхней или нижней стенки фиксируем направление движения шара. Если шар двигался вправо — запишем 0. Если влево — запишем 1. Фиксировать будем каждое $2^n$ касание шара.
Первое касание нижней стенки. Шар двигался вправо. Зафиксировали 0
Второе касание — верхней стенки. Шар двигался влево. Зафиксировали 1
Четвертое касание — верхней стенки. Шар двигался вправо. Зафиксировали 0
Восьмое касание — верхней стенки. Шар двигался вправо. Зафиксировали 0
И т.д.
Получили: 0.1001111001111001111… — это двоичная запись дроби $\frac{13}{21}$.

С помощью нее мы можем восстановить исходный паттерн (и даже заглянуть за нижнюю границу паттерна). Эта последовательность ($1010010110$) содержит всю необходимую информацию о паттерне. Расставим биты нашей последовательности в тех местах, в которых шар ударился об верхнюю стенку (расстояние между соседними касаниями шара — 2 клетки). Возьмем квадрат со сторонами $M$.

Если бит = 0 — двигаемся вправо. Если соответсвующий бит = 1 — начинаем двигаться влево, отмечая траекторию через клетку.

При этом не забываем про нулевой бит:

Gif:

Получили исходный паттерн (и немного заглянули за нижнюю границу):

Скрипт для визуализации двоичных последовательностей

Эту последовательность мы можем построить с помощью остатков от деления.

Одномерный бильярд.

На числовой оси $X$ возьмем две точки: $0$ и $M$.

Двигаясь от одной точки к другой, отмеряем расстояния $N$:

Продолжаем отмерять расстояние от этой точки, сохраняя направление. Отметили точку. Если достигли точки $0$ или $M$ — меняем направление:

Эта точка нас не интересует. Как видно на рисунках выше, первая точка показывает место, где шар касается нижней стенки бильярда. Мы будем фиксировать только точки $2kN$ для $k=0,1,2,…$.

Развернем наш бильярд на оси $X$. Как отметить эти точки? Теперь достигнув точки $M$ мы не меняем направление движения, а продолжаем двигаться к точке $2M$. Отметим точки $0, M, 2M, 3M,…$.

Условно отметим эти отрезки единицами и нулями (чередуются). Точки, кратные $M$, делят нашу ось на отрезки. На отрезках, отмеченных единицами — справа налево. На отрезках, отмеченных нулями, шар (в прямоугольном бильярде) двигается слева направо. Или проще: шар двигается слева направо, если $Q_k=0$, для

$Q_k=\lfloor \frac{2kN}{M} \rfloor \; (\textrm{mod} \; 2); \quad k=0,1,2,…$

(На эту формулу следует обратить особое внимание. Далее мы к ней вернемся)

При этом мы можем не фиксировать движение шара в обратную сторону. Легко заметить, что точка, в которой шар коснулся верхней стенки бильярда — это остаток от деления $2kN$ на $M$. Получившийся остаток разделим на 2 (расстояние между соседними точками касания — две клетки). Берем целую часть от деления $2kN$ на $M$, если она четная — считаем остаток от деления $2kN$ на $M$. Оставшиеся элементы заполняем единицами (шар двигался от правой стенки к левой). Получили индексы элементов массива, которые нам надо заполнить нулями.

Длина последовательность = $\frac{M}{2}$.

function sequence(m,n){ var md=m/2; var array=[]; for(var k=0;k<md;k++) array[k]=1; for(var k=0;k<md;k++) if(Math.floor(2*k*n/m)%2==0) array[((2*k*n)%m)/2]=0; return array;
}
console.log(sequence(55, 34).join('')); // -> 0101001011010010110101101001

Теперь мы можем построить двоичную последовательность для бильярда с любыми сторонами $M$ и $N$ (натуральными числами).
Несколько примеров:
144x89 (числа Фибоначчи):
010100101101001011010110100101101001010010110100101101011010010110100101

169x70 (числа Пелля):
0101011010100101011010100101011010110101001010110101001010110101001010010101101010010

233x55 (нечетные числа Фибоначчи $F_n$ и $F_{n-3}$):
0100100110110110010011011011001001001101100100100110110010010011011011001001101101100
10010011011001001001101100100100

Еще одна интересная таблица

Очень любопытные графики получаются, если взять бильярд с шириной $M$ и построить последовательности для каждого $N$ от $0$ до $M$. Далее эти последовательности сложить стопкой.

var array; for(var y=1;y<m;y++){ array=sequence(m,y); for(var x=0;x<array.length;x++){ if(array[x]==0) context.fillRect (x, y, 1, 1); } }

Несколько примеров.
M=610:

M=611:

M=612:

M=613:

M=614:

Для остальных M

Как еще можно визуализировать двоичные последовательности? Последовательности у нас есть. С помощью Черепашьей графики.

Turtle graphics.

Далее берем поочередно биты из нашей последовательности. Рисуем отрезок. Если бит = 0 — поворачиваем отрезок на $-60^{\circ}$. Если бит =1 — поворачиваем отрезок относительно предыдущего на $60^{\circ}$ (по часовой). Начало следующего отрезка — конец предыдущего.

Размер начального отрезка — 10 пикселей (начальный отрезок в правом нижнем углу): Возьмем два достаточно больших числа Фибоначчи: $F_{29}=514229$ и $F_{28}=317811$.
Построили последовательность:
00101101001011010010100101101001011010110100101101001010010110100101… (257114 символов плюс нулевой бит).
Визуализируем с помощью черепашьей графики.

Размер начального отрезка — 5 пикселей:

Размер начального отрезка — 1 пиксель:

Следующий пример — числа Пелля.

$P_n=\begin{cases}0, n=0;\\1, n=1 \\2P_{n-1}+P_{n-2}, n>1 \end{cases}$

Берем $P_{16}=470832$ и $P_{15}=195025$.
Последовательность:
00101001010110101001010110101001010010101101010010101101010010101101 (235415 символов плюс нулевой бит).
Размер начального отрезка — 1 пиксель:

Еще один пример — нечетные числа Фибоначчи $F_n$ и $F_{n-3}$.
Берем $F_{28}=317811$ и $F_{25}=75025$.
Последовательность:
00110110010010011011001001001101101100100110110110010011011011001001… (158905 плюс нулевой бит).
Вместо углов $60^{\circ}$ и $-60^{\circ}$ будем использовать углы $90^{\circ}$ и $-90^{\circ}$.
Размер начального отрезка — 5 пикселей:

4 пикселя: Размер начального отрезка — 0.

Размерность Хаусдорфа для этой кривой известна:
У этой кривой есть название — «Fibonacci word fractal».

$D=3{\frac {\log \Phi }{\log(1+{\sqrt {2}})}}=1,6379; \quad \Phi =\frac {1+{\sqrt {5}}}{2}$

Скрипт для визуализации двоичных последовательностей с помощью Turtle Graphics

Проблема.

Задача нетривиальная. Можно ли нарисовать паттерн для бильярда, стороны которого несоизмеримы (одна из сторон — иррациональное число)? Пытаясь решить эту задачу, мы столкнемся с рядом вопросов:
1. Если стороны несоизмеримы — мы не можем замостить бильярд клетками одинаковой величины.
2. Если стороны несоизмеримы — шар будет бесконечно отражаться и никогда не попадет в угол.
3. Последовательности в бильярдах заполняются не по порядку, а хаотично.

Но если бы существовал способ заполнить последовательность по порядку — тогда мы могли бы, двигаясь по последовательности слева направо, восстановить паттерн способом, которым мы пользовались выше. Первые два вопроса, очевидно, не имеют решения. И тем самым увидеть, как выглядит паттерн в левом верхнем углу бильярда, стороны которого несоизмеримы.

Черная магия.

Запустим в него шар и будем фиксировать номер касания шара у верхней стенки. Возьмем бильярд, стороны которого равны числам Фибоначчи (с другими числами такой фокус может не сработать). Номера закрасим белым цветом — если шар двигался справа налево и черным — если шар двигался слева направо:

Теперь расставим номера по порядку: Белому цвету соответствует единица в последовательности, черному — ноль.

Получили точно такую же последовательность единиц и нулей.

Для других чисел

Начало координат — левый верхний угол. По оси $x$ — ширина бильярда $M$. По оси $y$ — высота бильярда $N$. Белыми точками отмечены числа, для которых последовательности совпадают:

Числа, для которых последовательность инвертируется:

Закинул скрипт:

Первая строка — координаты мышки, которые используются в качестве ширины и высоты бильярда.
Вторая строка — первые 100 бит последовательности, полученной через остатки от деления.
Третья строка — первые 100 бит последовательности, полученной через четность целой части.

Черный цвет — Визуализация первой последовательности с помощью Turtle graphics.
Фиолетовый — визуализация второй последовательности.

Для чисел Фибоначчи достаточно проверить четность целой части от деления $2kN$ на $M$: Фактически, в некоторых случаях, нам не надо брать остаток от деления.

$Q_k=\lfloor \frac{2kN}{M} \rfloor \; (\textrm{mod} \; 2); \quad k=0,1,2,…$

В знаменателе — $F_{n+1}$. В числителе у нас $F_{n}$.

Как известно:

$\lim_{n\to\infty} \frac{F_n}{F_{n+1}}= \frac{1}{\Phi}$

Иррациональное число. $\Phi$ — Золотое сечение. Теперь нашу формулу можем записать как:

$Q_k=\lfloor \frac{2k}{\Phi} \rfloor \; (\textrm{mod} \; 2); \quad k=0,1,2,…$

Длина последовательности = $\infty$, но мы можем восстанавливать часть паттерна, двигаясь слева направо по последовательности и заглянуть в верхний левый угол бильярда. Получили формулу, с помощью которой можем по порядку заполнять последовательность для бильярда, ширина которого равна $\Phi$, а высота — $1$. Осталось разобраться, как посчитать $\Phi$

Единицу деленную на золотое сечение можно переписать как:

$\frac{1}{\Phi}=\frac {-1+{\sqrt {5}}}{2}$

Мы можем избавиться от двойки:

$\frac{2k}{\Phi}=\frac {2k(-1+{\sqrt {5}})}{2}=k\sqrt{5}-k$

Наша формула принимает вид:

$Q_k=\lfloor k\sqrt{5}-k \rfloor \; (\textrm{mod} \; 2); \quad k=0,1,2,…$

В третьей колонке отбрасываем дробную часть и оставляем целую. Для наглядности нарисовал таблицу. В четвертой колонке проверяем четность целой части:

В четвертой колонке получили нашу последовательность: 01010010110100…

Восстанавливаем часть паттерна для бильярда со сторонами $1$ и $\Phi$: Продолжаем вычислять биты для остальных $k$.

Получим общую формулу: Если не отнимать каждый раз $k$ — тогда каждый второй бит в последовательности инвертируются.

$Q_k=\lfloor k\sqrt{x} \rfloor \; (\textrm{mod} \; 2); \quad k=0,1,2,…$

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

Построим последовательность для $k\sqrt{3}+k$


var x=3;
var q=[];
for(var k=0;k<256000;k++) q[k]=Math.floor(k*Math.sqrt(x)+k)%2;

Первые несколько бит последовательности:
00100101101001001011010010110110100101101001001011010010010110100101…

Углы 90 и -90 градусов. Визуализировать будем с помощью черепашьей графики. Размер начального отрезка 5 пикселей:

5 пикселя: Размер начального отрезка — 0.

Построим последовательность для $k\sqrt{2}$


var x=2;
var q=[];
for(var k=0;k<256000;k++) q[k]=Math.floor(k*Math.sqrt(x))%2;

Первые несколько бит последовательности (A083035):
01001101100100110010011011001101100100110110011011001001100100110110…

Размер начального отрезка 5 пикселей: Углы 90 и -90 градусов.

5 пикселя: Размер начального отрезка — 0.

Это интересно

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

Интересно было бы подобрать $M$ и $N$ для этого паттерна.

И это

Количество отрезков в повторяющейся части кривой = $P_n$ (числа Пелля: 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, … ).

$\sqrt{2} = \lim_{n\to\infty} \tfrac{P_{n-1}+P_n}{P_n}$

Размер начального отрезка 5 пикселей: Углы 60 и -60 градусов.

Скрипт для визуализации

Визуализируем часть этой последовательности вторым способом: Кто-то может засомневаться в том, что четность целой части от $k\sqrt{2}$ дает фрактальную последовательность.

Для наглядности, закрасил самую длинную кривую в получившемся паттерне:

У этой кривой есть название — «Fibonacci word fractal».

Берем бильярд, ширина которого = 1, а высота = $\sqrt{2}$. Как с помощью бильярда получить эту последовательность? Если шар двигался слева направо — записываем 0, если справа налево — записываем 1. У верхней и нижней границы фиксируем направление движения шара.

Два графика:

$z=\lfloor y\sqrt{x} \rfloor \; (\textrm{mod} \; 2)$

$z=\lfloor yx\sqrt{2} \rfloor \; (\textrm{mod} \; 2)$

Но статья и без того получилась слишком громоздкой. Продолжать в том же духе можно очень долго — у паттернов есть много интересных свойств. Об одном из интересных свойств расскажу напоследок.

В двоичном бильярде мы запускали шар из левого верхнего угла и заполняли матрицу битами.

Для бильярда 610х377:

Увеличенная часть паттерна:

Если запустить второй шар из другого угла (из левого нижнего для бильярда 610х377) и отметить биты, которые совпадают для обеих траекторий — получим очень любопытный паттерн:

Увеличенная часть паттерна: Совпадающие биты отмечены черными пикселями.

Об одном из них упомянул в статье Perfect shuffle. Существует еще два способа нарисовать этот паттерн. Второй:

Нарисуем график функции:

$z=\sin(x\pi(\sqrt{5}+1))+\sin(y\pi(\sqrt{5}+1))$

И отметим черными точками $z<0$:

Увеличенная часть паттерна:

Теги
Показать больше

Похожие статьи

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть