Репрезентация через комплементарность (в поисках паттерна)

[kthxbye]

Некоторые участники форума (когда я прибегаю сюда с очередным вопросом) иногда жалуются на то, что им ничего не понятно. Постараюсь в этот раз разъяснить все максимально подробно, поскольку вопрос кажется мне достаточно интересным.

Пусть $T(n,k)$ это A035506, т.е. массив (а точнее бесконечная таблица) Stolarsky читаемый по антидиагоналям. Здесь Stolarsky это фамилия некоего Kenneth B. Stolarsky.

Последовательность начинается так:

$$1, 2, 4, 3, 6, 7, 5, 10, 11, 9, 8, 16, 18, 15, 12, 13, 26, 29, 24$$

А вот так она выглядит в виде бесконечной таблицы (ниже приведен левый верхний угол):

$$\begin{bmatrix} 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 \\ 4 & 6 & 10 & 16 & 26 & 42 & 68 & 110 & 178 & 288 \\ 7 & 11 & 18 & 29 & 47 & 76 & 123 & 199 & 322 & 521 \\ 9 & 15 & 24 & 39 & 63 & 102 & 165 & 267 & 432 & 699 \\ 12 & 19 & 31 & 50 & 81 & 131 & 212 & 343 & 555 & 898 \\ 14 & 23 & 37 & 60 & 97 & 157 & 254 & 411 & 665 & 1076 \\ 17 & 28 & 45 & 73 & 118 & 191 & 309 & 500 & 809 & 1309 \\ 20 & 32 & 52 & 84 & 136 & 220 & 356 & 576 & 932 & 1508 \\ 22 & 36 & 58 & 94 & 152 & 246 & 398 & 644 & 1042 & 1686 \\ 25 & 40 & 65 & 105 & 170 & 275 & 445 & 720 & 1165 & 1885 \end{bmatrix}$$

Для разнообразия дальше можно заглянуть сюда (одностраничный pdf на английском), но вообще это необязательно.

Итак, какова же закономерность и как, собственно, задается $T(n,k)$? Offset (стартовый член последовательности) у A035506 это $0$, но для удобства мы условимся нумеровать $T(n,k)$ по натуральным значениям $n,k$. Т.е. $T(1,1)=1$, $T(2,1)=4$ и т.д.

Итак, пока все очень просто. Пусть $\varphi=\frac{1+\sqrt{5}}{2}$, тогда $T(n,1)=\left\lfloor n(\varphi+1)-\frac{\varphi}{2}\right\rfloor$ и $T(n,2)=\left\lfloor T(n,1)\varphi+\frac{1}{2}\right\rfloor$. Ну а далее $T(n,k)=T(n,k-1)+T(n,k-2)$.

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

Дальше нам потреюбуется PARI. Копируем прогу из соответствующей секции в A035506 и добавляем еще кое-что:

{Stolarsky(r, c)= tau=(1+sqrt(5))/2; a=floor(r*(1+tau)-tau/2); b=round(a*tau); if(c==1, a, if(c==2, b, for(i=1, c-2, d=a+b; a=b; b=d; ); d))}
[x,y]=[1,1]; for(k=1,299, while(!(Stolarsky(x,y)==k), y++; if(Stolarsky(x,y)>k, x++; y=1)); print([x,y]); [x,y]=[1,1];);

Т.е. здесь мы ищем по каким координатам (номер строки и стоблца) у нас прячется каждое натурально число по-порядку. Выходят вот такие последовательности:

1, 2, 3, 1, 4, 2, 1, 5, 1, 3, 2, 1, 6, 1, 2, 4, 1, 3, 2, 1
1, 1, 1, 2, 1, 2, 3, 1, 4, 2, 3, 5, 1, 6, 4, 2, 7, 3, 5, 8

Что здесь можно заметить? Во второй последовательности каждые $F(k)$ (числа Фибоначчи) членов содержат числа от $1$ до $F(k)$. Как их генерить трудно сказать. С первой последовательностью вообще ничего не понятно.

Вот мы и ознакомились с $T(n,k)$. В моем случае я о ней когда-то узнал, а потом забыл. Едем дальше.

Пусть $a(n)$ это A200714, т.е. репрезентация Stolarsky читаемая в двоичной системе счисления, а затем переведенная в десятичную.

Последовательность начинается так:

$$0, 1, 3, 2, 7, 5, 6, 15, 4, 11, 13, 14, 31, 10, 9, 23, 12, 27, 29, 30$$

Нумерация начинается с единицы, т.е. $a(1)=0$, $a(2)=1$ и т.д.

Что же это за репрезентация такая? Пусть у нас есть две последовательности - $b_1(n)=T(n,1)$ и $b_2(n)=\left\lfloor n\varphi+\frac{1}{2}\right\rfloor$. Эти последовательности комплементарны, т.е. в совокупности они образуют последовательность натуральных чисел, но при этом каждое число принадлежит только какой-то одной из последовательностей (а следовательно встречается в совокупности ровно один раз).

Дальше мы задаем $a(1)=0$. Т.е. у нас там как бы ноль, но на самом деле он символизирует пустоту. И вот к этой пустоте мы начинаем применять следующее правило:

• если $n=b_1(k)$, припишите к репрезентации $k$ в конце один $0$
• если $n=b_2(k)$, припишите к репрезентации $k$ в конце одну $1$

Для наглядности можно заглянуть в текстовый файл из раздела ссылок в A200714 (вот он).

Теперь самое интересное. Пусть $c(n)$ это обратная перестановка $\left\lbrace a(n)+1\right\rbrace$, т.е. $a(c(n))=n-1$.

Последовательность начинается так:

$$1, 2, 4, 3, 9, 6, 7, 5, 22, 15, 14, 10, 17, 11, 12, 8, 56, 36, 38, 24$$

А теперь мы призываем $T(n,k)$ в качестве флешбека и шутки ради делаем следующее:

{Stolarsky(r, c)= tau=(1+sqrt(5))/2; a=floor(r*(1+tau)-tau/2); b=round(a*tau); if(c==1, a, if(c==2, b, for(i=1, c-2, d=a+b; a=b; b=d; ); d))}
a(n) = {if (n == 1, return (0)); tau = (1 + sqrt(5))/2; mn = 0; while ((m = round(mn*tau)) < n, mn++; ); if (m == n, return (2*a(mn)+1)); mn = 0; while ((m = floor(mn*(1+tau)-tau/2)) < n, mn++; ); if (m == n, return (2*a(mn))); error("neither A nor B !!"); }
c(n) = my(A=1); while(!(a(A)==n-1), A++); A
[x,y]=[1,1]; for(k=1,299, my(A=c(k)); while(!(Stolarsky(x,y)==A), y++; if(Stolarsky(x,y)>A, x++; y=1)); print([x,y]); [x,y]=[1,1];);

Т.е. мы ищем координаты натуральных чисел не в их обычном порядке, а в том, в каком они расположены в $c(n)$. Результат ошемляющий:

1, 1, 2, 1, 4, 2, 3, 1, 9, 4, 6, 2, 7, 3, 5, 1, 22, 9, 15, 4
1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3

Иными словами, если мы вводим $q(n)$ (A007814, т.е. число конечных нулей в двоичной записи $n$), то координаты имеют вид

$$\left\lbrace c\left(\left\lfloor\frac{n}{2^{q(n)+1}}\right\rfloor+1\right), q(n)+1\right\rbrace$$

Вопросы:

• Если мы берем любые комплементарные последовательности, образующие в совокупности последовательность натуральных чисел и начинаем приписывать нули и единицы к пустой репрезентации, всегда ли мы будем иметь (после чтения в двоичной системе счисления и перевода в десятичную) перестановку натуральных чисел?
• Если да, то верно ли также, что аналогичная (практически) обратная перестановка проливает свет на закономерности для координат?
• Что если взять таблицу $R(n,k)$, такую что $R(1,n)$ это простые, уменьшенные на единицу, а $R(n,k)$ при $n>1$ это простые, умноженные на $k$ и результат уменьшен на единицу? Существует ли для нее репрезентация на основе комплементарности, которая дает закономерность для координат?
• Уникальна ли $c(n)$ в том плане, что координаты имеют именно такой вид?

Везде подразумевается что $q(n)$ это не единственная последовательность, на которой базируется закономерность - ею может быть любая другая последовательность, в которой каждое натуральное число встречается бесконечное количество раз.

Благодарю вас за интерес, если вы прочитали весь пост до конца. Буду признателен за столь аналогичные (по подробности) ответы.