Об одной аддитивной задаче, связанной с разложениями по линейной рекуррентой последовательности
А. В. Шутов Хабаровское отделение Института прикладной математики ДВО РАН (г. Владимир)
Аннотация:
Пусть
$a_1,\ldots,a_d$ – натуральные числа, удовлетворяющие условию
$a_1\geq a_2\geq\ldots\geq a_{d-1}\geq a_d=1.$ Определим последовательность
$\{T_n\}$ при помощи линейного рекуррентного соотношения
$T_n=a_1T_{n-1}+a_2T_{n-2}+\ldots+a_dT_{n-d}$ и начальных условий
$T_0=1,$ $T_n=1+a_1T_{n-1}+a_2T_{n-2}+\ldots+a_nT_0$ для
$n<d$. Пусть
$\mathbb{N}(w)$ – множество натуральных чисел, для которых жадное разложение по линейной рекуррентной последовательности
$\{T_n\}$ заканчивается на некоторое слово
$w$. При этом
$w$ выбирается так, чтобы множество
$\mathbb{N}(w)$ было непустым. Рассматривается задача о числе
$r_k(N)$ представлений натурального числа
$N$ в виде суммы
$k$ слагаемых из
$\mathbb{N}(w)$.
С использованием полученного ранее описания множеств
$\mathbb{N}(w)$ в терминах сдвигов торов размерности
$d-1$ получена асимтотическая формула для числа представлений
$r_k(N)$, а также найдены верхние оценки для числа представлений.
Найдены условия на
$k$, при выполнении которых искомое представление существует для всех достаточно больших натуральных
$N$. В частности, такое представление существует, если
$k\geq 1+(a_1+1)^{m-d+1}\frac{(a_1+1)^d-1}{a_1}$, где
$m$ – длина фиксированного окончания
$w$ жадного разложения. Кроме того, получена асимтотическая формула для среднего числа представлений.
В заключении сформулировано несколько нерешенных задач.
Ключевые слова:
линейные рекуррентные последовательности, жадные разложения, фиксированные последние цифры, линейная аддитивная задача.
УДК:
511 Поступила в редакцию: 25.04.2023
Принята в печать: 12.09.2023
DOI:
10.22405/2226-8383-2023-24-3-228-241