Две одинаковых последовательности

[daniel starodubtsev]

Решил ради интереса поискать числа, не представимые в виде суммы двух чисел с равными суммами цифр. Последовательность выходит такая: $1, 3, 5, 7, 9, 29, 49, 69, 89, 199, 399, 599, 799, 999, 2999, 4999, 6999...$.
Закономерность очевидна. Залез в OEIS и оказалось, что она там есть. Но под другим предлогом: A131668. Возможно кто-нибудь понимает, почему последовательности совпадают? А то я что-то не смог сам додуматься...

[kthxbye]

Вашу проблему можно переформулировать, как

$$a_k(n)=a_k(\left\lfloor\frac{n}{k}\right\rfloor)+(n\mod k)$$

$$b_k(n) = \sum\limits_{m=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\delta_0(a_k(m)-a_k(n-m))$$

$$\delta_0(n)= \begin{cases} 1,&\text{$n=0$}\\ 0,&\text{$n\ne0$}\\ \end{cases}$$

где $k$ - основание системы счисления, $a_k(n)$ - сумма цифр $n$. Что касается $b_k(n)$, то нас интересуют только те значения, которые равны $0$. Последовательно сгенерировать их номера ($q_k(n)$) для четных $k$ можно следующим образом:

$$f_k(n)=\left\lfloor\frac{n}{k-1}\right\rfloor-\left\lfloor\frac{n-1}{k-1}\right\rfloor$$

$$g_k(n)=\left\lfloor\frac{2n}{k-1}\right\rfloor-f_k(n)$$

$$h_k(n)=(k-1)f_k(n)+(2n\mod (k-1))$$

$$q_k(n)=k^{g_k(n)}h_k(n)-1$$

Что примечательно, они опять-таки соответствуют определению из A131668. Но вот почему? Загадка. Проблема интересная, если будут подвижки, обязательно поделюсь.

[daniel starodubtsev]

Интересно, что множество чисел не представимых в виде разности двух чисел с равной суммой цифр, это все те же числа, за очевидным исключением чисел вида $10^k - 1$.

[daniel starodubtsev]

А, нет, с разностью я что-то напутал. Очевидно что если число не кратно 9, то оно не представимо в виде разности двух чисел с равной суммой цифр.

[Munin]

kthxbye
Команда \mod предназначена для того, чтобы набирать сравнения по модулю, здесь она входит в серию команд \mod, \pmod, \pod (от parenthesis):

$\begin{aligned} m&\equiv n\mod{k} &&\texttt{{\textbackslash}mod} \\ m&\equiv n\pmod{k} &&\texttt{{\textbackslash}pmod} \\ m&\equiv n\pod{k} &&\texttt{{\textbackslash}pod} \end{aligned}$

А чтобы набрать символ mod как бинарный оператор остатка от деления, предназначена команда \bmod (от binary operator):

$(n\bmod k)$

[kthxbye]

Munin, благодарю за пояснения!

К слову о задаче. В OEIS определение $a(n)$ следующее

• минимальное число с суммой цифр $2n+1$ в $10$-ной системе счисления

Пусть это число $m$-значное. Тогда первая (естественно слева) цифра должна быть минимальной, отсюда сумма всех остальных должна быть максимальной. Предположим, все эти цифры - девятки. Тогда превращение любой из них в восьмерку либо увеличит первую цифру на 1, либо превратит число в $(m+1)$-значное. В обоих случаях получаем числа, большие исходного. Следовательно, все цифры кроме первой - это девятки.

Если сумма двух цифр оканчивается на $9$, то она не больше девяти, и, следовательно, равна девяти. Отсюда

$$p_1+q_1=k$$

$$p_2+q_2=9$$

$$p_3+q_3=9$$

$$\cdots$$

$$p_m+q_m=9$$

Если суммы цифр каждого из чисел равны друг другу, то складывая левые и правые части, получим

$$2m=2n+1$$

что невозможно. Следовательно, $a(n)$ является как минимум подпоследовательностью последовательности чисел, которые не представимы в виде суммы двух чисел с одинаковой суммой цифр в $10$-ной системе счисления.