08.03.2019 00:01
xcont 12 11300 Источник
Статья является продолжением моей первой статьи «Фракталы в простых числах».



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

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

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


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



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



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



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



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



Для разных M и N
Больше всего в этих паттернах удивляет то, что для разных $M$ и $N$ получается свой уникальный паттерн:



В статье, в качестве $M$ и $N$, мы используем преимущественно числа Фибоначчи. Здесь можно нарисовать паттерны для других чисел (координат мышки).

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



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



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

$(1, 0)$ бит


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



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

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



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



Есть еще один оригинальный способ получить эти линии.

Для каждого $x$ и $y$, если $y$ является делителем $x$, построим последовательность чисел Фибоначчи:

$F_0=y; F_1=x; F_n=F_{n-1}+F_{n-2}$


И отметим на графике точки $(F_{n}, F_{n-1})$ и $(F_{n-1}, F_{n})$:


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


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





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



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



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

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



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



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

Получили: 0.1001111001111001111… — это двоичная запись дроби $\frac{13}{21}$.



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



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



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



Gif:



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



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

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

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


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



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



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



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

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



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

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


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

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

Длина последовательность = $\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


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



Возьмем два достаточно больших числа Фибоначчи: $F_{29}=514229$ и $F_{28}=317811$.

Построили последовательность:
00101101001011010010100101101001011010110100101101001010010110100101… (257114 символов плюс нулевой бит).

Визуализируем с помощью черепашьей графики. Размер начального отрезка — 10 пикселей (начальный отрезок в правом нижнем углу):



Размер начального отрезка — 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 пикселей:



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



У этой кривой есть название — «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}$. В знаменателе — $F_{n+1}$.

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

$\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,…$



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

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



Если не отнимать каждый раз $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 пикселей:



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



Построим последовательность для $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…

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



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



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



Интересно было бы подобрать $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}$



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



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

Кто-то может засомневаться в том, что четность целой части от $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$:



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


Комментарии (12)


  1. xcont Автор
    08.03.2019 05:35
    #19851504
    +5

    Минутка злости
    Ссылки в статье заработают, когда хостер праздновать закончит.


    1. AEP
      08.03.2019 16:13
      #19852938

      Можно было залить на jsfiddle.net или аналоги.


    1. babylon
      08.03.2019 19:47
      #19853498

      Это Ваша работа или хобби?


  1. Javian
    08.03.2019 07:08
    #19851546
    +1

    off Картинка первого графика (y*sqrt(x)) очень похожа на искажения на аналоговом видеосигнале при передаче изображения из прямых линий, выходящих из одной точки.


  1. rumkin
    08.03.2019 07:14
    #19851552
    -2

    От таких изображений эпилептический припадок может случиться. Лучше убавьте контраст.


    1. xcont Автор
      08.03.2019 10:09
      #19851800

      Спрятал «проблемные» картинки под спойлер.


      1. vvzvlad
        10.03.2019 11:11
        #19858434
        -1

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


  1. S-e-n
    08.03.2019 10:10
    #19851806
    +1

    Спасибо за статью.

    Я не специалист, но не поставить ли тут варнинг для эпилептиков? Я не эпилептик, но от продолжительного созерцания последней картинки слегка поплохело.


  1. amarao
    08.03.2019 13:49
    #19852528
    +2

    Последняя картинка поста обладает свойством оптической иллюзии — если её скроллить, разные части картинки будут двигаться с разной скоростью.


  1. zuborg
    08.03.2019 15:11
    #19852766
    +2

    Отправьте ссылку Стивену Вольфраму, он оценит! )


  1. fivehouse
    08.03.2019 21:38
    #19853676

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


  1. Smith2018
    08.03.2019 23:58
    #19854070
    -3

    Очень красиво! Только зачем это все нужно? Убили столько времени на то, чтоб сгенерировать всю эту хр*нотень…