Построение посл.-тей с опр.-ным св.-вом

[kthxbye]

Пусть

$$\varphi=\frac{1+\sqrt{5}}{2}$$

Пусть также

$$a_1(n)=\left\lfloor n\varphi \right\rfloor, a_2(n)=n+a_1(n)$$

Пусть $b_1(n)$ и $b_2(n)$ - это пара бесконечных комплементарных последовательностей, таких, что

• $b_1(1) = 1$ и $b_1(n)-b_1(n-m)$ принадлежит множеству $\left\lbrace a_2(m), a_2(m)+1 \right\rbrace$ при любых $n>m>0$.
• $b_2(1) = 2$ и $b_2(n)-b_2(n-m)$ принадлежит множеству $\left\lbrace a_1(m), a_1(m)+1 \right\rbrace$ при любых $n>m>0$.

Эксперименты свидетельствуют, что существует как минимум три пары таких последовательностей:

• A007064, A007067
• A007066, A026355
• A003622, A022342

Каким образом можно строить такие последовательности? Конечно ли их количество и существует ли способ доказать или же опровергнуть это?

[KhAl]

А последовательностей типа $b_1$ вообще бесконечно много?

[kthxbye]

KhAl в сообщении #1608846 писал(а):

А последовательностей типа $b_1$ вообще бесконечно много?

Это меня как раз и интересует. Я задумался, почему вы это спросили. Быть может это наводящий вопрос? Последовательность $a_2(n)$ начинается так:

$$2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41$$

Какой вывод мы можем здесь сразу же сделать? Допустим $c_1(n)$ это характеристическая функция $b_1(n)$. Мы начинаем с $c_1(1)=1$. Т.к. $a_2(1)=2$, то либо $c_1(3)$ либо $c_1(4)$ равно единице, а также гарантированно $c_1(2)=0$.

Таким образом мы можем отсеять часть чисел $k$, при которых гарантированно имеем $c_1(k)=0$, а оставшиеся пары потенциальных единиц заполнять либо парой $\left\lbrace0, 1\right\rbrace$, либо парой $\left\lbrace1, 0\right\rbrace$.

Я написал простую программку для этого:

b1(n) = (n + sqrtint(5*n^2))\2
b2(n) = b1(n) + n
b3(n) = b2(n) + 1
b4(n) = my(A = (1 + sqrt(5))/2); floor(2*A) - floor(n*A) - floor((2 - n)*A)
b5(n, m) = my(v1); v1 = vector(b3(m) + 1, i, b4(i)); for(i=1, m, if(bittest(n, i - 1), v1[b3(i)] = 0, v1[b3(i) + 1] = 0)); my(v2, v3); v2 = select(x -> (x == 1), v1, 1); v3 = select(x -> (x == 0), v1, 1); my(A1 = 0, A2 = 0); for(i=1, #v2-1, for(j=i + 1, #v2, A1+=(v2[j] - v2[i]) == b2(j - i) || (v2[j] - v2[i]) == (b2(j - i) + 1))); for(i=1, #v3-1, for(j=i + 1, #v3, A2+=(v3[j] - v3[i]) == b1(j - i) || (v3[j] - v3[i])==(b1(j - i) + 1))); [A1==binomial(#v2, 2) && A2==binomial(#v3, 2)]
b6(n, m, k) = (n%2)*2^m + k
w1 = [0, 1];
for(i=1, 20, my(z = 1, w2 = []); for(j=0, 2*#w1 - 1, if(b5(b6(j, i, w1[j\2 + 1]), i + 1), w2 = concat(w2, b6(j, i, w1[j\2 + 1])))); w2 = vecsort(w2); for(j=1, i+1, print(binary(w2[j]))); w1 = w2);

Вот несколько первых значений которые она возвращает:

[]
[1]
[1, 1]

[]
[1, 0, 0]
[1, 0, 1]
[1, 1, 1]

[]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0, 1]
[1, 1, 1, 1]
[]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0, 1]
[1, 1, 1, 1]
[1, 1, 1, 1, 1]

[]
[1, 0, 0]
[1, 0, 0, 1, 0, 0]
[1, 0, 0, 1, 0, 1]
[1, 0, 1, 1, 0, 1]
[1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]

[]
[1, 0, 0]
[1, 0, 0, 1, 0, 0]
[1, 0, 0, 1, 0, 1]
[1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1]

[]
[1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1]

Здесь $k$-тый справа ноль говорит о том, что пара заполняется $\left\lbrace1, 0\right\rbrace$. Если же вместо нуля стоит единица, то, соответственно, заполняем как $\left\lbrace0, 1\right\rbrace$.

Для чисел принадлежащих последовательности A001906 (четные числа Фибоначчи) первый слева бит для всех чисел кроме нуля (который отображается как []) это единица. Что интересно, если мы будем считать количества сплошных нулей подряд сверху вниз, то вполне вероятно, что они совпадают с соответствующей четной строкой последовательности A257961 (что можно будет дополнительно проверить через подстановку ее значений в b5(n, m).

Вот еще для примера:

[]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1]
[1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Т.е. вероятно что таких последовательностей бесконечно много и потенциально существует как минимум один способ построения их подпоследовательностей.

Теперь меня интересует другой вопрос. Пусть

$$T(n,k)=b_2(T(n,k-1)), \\ T(n,1)=b_1(n)$$

Как генерировать пары последовательностей, для которых $T(n,k)=T(n,k-1)+T(n,k-2)$ при $k>2$? Т.е. мы работает с теми же последовательностями, но просто добавляется новое ограничение.

[KhAl]

kthxbye писал(а):

Быть может это наводящий вопрос?

неа, просто думаю