Отбор f(n,m)-решаемых посл.-тей

[kthxbye]

Пусть

$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$

а также

$$b(n)=3\cdot2^{\ell(n)}-n-1$$

Тогда будем иметь

$$f(n,m)=2(b(2n+1)+2^{\ell(n)+2}(2^m-1))$$

Пусть $a_k(n)$ принадлежит семейству последовательностей рекуррентного типа, которые задаются следующим образом:

$$a_k(2n+1)=a_k(n), a_k(2n)=a_k(n)+\sum\limits_{j=1}^{i}a_k(g_j(n)), a_k(0)=1$$

Здесь $g_j(n)$ это некоторые функции, такие, что $0\leqslant g_j(n)<2n$.

Теперь, собственно, к сути. Назовем последовательность $a_k(n)$ $f(n,m)$-решаемой, если для $n>0$ она имеет легко задаваемую замкнутую форму типа

$$a_k(f(n,m))=\sum\limits_{j=1}^{h(n)}s(n,m,j)T_k(c(n),j)$$

Здесь $h(n)$ это функция для верхней границы суммы, $s(n,m,j)$ отвечает за особенности суммирования, $c(n)$ это A059893 (в двоичной записи $n$ реверсируем порядок всех битов кроме крайнего слева), и, наконец, $T_k(n,j)$ это легко задаваемые целые коэффициенты с нехитрым рекуррентным соотношением.

Например, возьмем A002487, последовательность Штерна-Броко, и на единицу сместим точку отсчета последовательности. Тогда рекуррентное соотношение примет вид

$$a_1(2n+1)=a_1(n), a_1(2n)=a_1(n)+a_1(n-1), a_1(0)=1$$

Здесь важно отметить, что сама последовательность осталась той же, просто мы поменяли немного точку отсчета, т.е. сместили нулевый член.

Тогда будем иметь

$$a_1(f(n,m))=\sum\limits_{j=1}^{2}(m+1)^{j-1}T_1(c(n),j)$$

Здесь $T_1(n,1)=a_1(n)$ и $T_1(n,2)=a_1(2n)$.

Другой пример - моя любимая последовательность A329369. Она тоже оказалась $f(n,m)$-решаемой.

Пусть $\operatorname{tr}(n)$ это A007814, число конечных нулей в двоичной записи $n$.

Пусть

$$a_2(2n+1)=a_2(n), a_2(2n)=a_2(n)+a_2(n-2^{\operatorname{tr}(n)})+a_2(2n-2^{\operatorname{tr}(n)}), a_2(0)=1$$

Тогда будем иметь

$$a_2(f(n,m))=\sum\limits_{j=1}^{\operatorname{wt}(n)+2}j!\cdot j^{m+1}T_2(c(n),j)(-1)^{\operatorname{wt}(n)-j+2}$$

Здесь $\operatorname{wt}(n)$ это A000120 (число единиц в двоичной записи $n$) а также

$$T_2(0,1)=T_2(0,2)=1$$

$$T_2(n,1)=1, n>0$$

$$T_2(0,k)=0, k>2$$

$$T_2(2n+1,k)=kT_2(n,k)+T_2(n,k-1)$$

$$T_2(2n,k)=kT_2(n,k)+T_2(n,k-1)-\frac{1}{k-1}(T_2(2n,k-1)+T_2(n,k-1))$$

Существует еще две последовательности, являющиеся интерполяцией A329369, которые тоже являются $f(n,m)$-решаемыми - это A341392 и A347205. Рекуррентные соотношения для их $T_k(n,j)$ требуют обращения к дополнительным последовательностям. Чтобы не нагромождать уже и без того большую тему, здесь я их не привожу.

Теперь, собственно, к вопросу: имеем множество последовательностей хотя бы следующего типа

$$a_k(2n+1)=a_k(n), a_k(2n)=a_k(n)+a_k(g_1(n)), a_k(0)=1$$

Как мы помним, $0\leqslant g_1(n)<2n$.

Вопрос: как из множества всех этих последовательностей отобрать $f(n,m)$-решаемые? Может есть какой-то критерий, по которому с определенной вероятностью последовательность будет являться $f(n,m)$-решаемой, что уже, собственно, будет несложно проверить? Если да, то что это за критерий (или критерии)? Можно ли получать эти критерии в процессе грубого перебора всех последовательностей? Конечно ли множество $f(n,m)$-решаемых последовательностей или же с помощью умного перебора можно наткнуться на потенциальное бесконечное семейство?

[kthxbye]

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

$$f(n,m)=2(b(\textcolor{red}{n+2^{\ell(n)+1}})+2^{\ell(n)+2}(2^m-1))$$

Еще я заметил, что если вместо $a_k(n)$ мы будем брать $a_k(n,x)$, такие, что

$$a_k(2n+1,x)=a_k(n,x), a_k(2n,x)=xa_k(n,x)+\sum\limits_{j=1}^{i}a_k(g_j(n),x), a_k(0,x)=1$$

то если хотя бы для одного $x\in\mathbb{N}$ последовательность $a_k(n,x)$ является $f(n,m)$-решаемой, то для любого $x\in\mathbb{N}$ остальные последовательности $a_k(n,x)$ аналогично являются $f(n,m)$-решаемыми. Вероятно это тривиальный результат, который может быть как-то обобщен (но как конкретно пока сказать не могу).