2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Две одинаковых последовательности
Сообщение13.05.2019, 16:57 


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

 Профиль  
                  
 
 Re: Две одинаковых последовательности
Сообщение16.05.2019, 12:16 
Аватара пользователя


22/11/13
496
Вашу проблему можно переформулировать, как
$$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. Но вот почему? Загадка. Проблема интересная, если будут подвижки, обязательно поделюсь.

 Профиль  
                  
 
 Re: Две одинаковых последовательности
Сообщение19.05.2019, 20:40 


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

 Профиль  
                  
 
 Re: Две одинаковых последовательности
Сообщение08.08.2019, 11:13 


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

 Профиль  
                  
 
 Re: Две одинаковых последовательности
Сообщение08.08.2019, 11:31 
Заслуженный участник
Аватара пользователя


30/01/06
72407
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)$

 Профиль  
                  
 
 Re: Две одинаковых последовательности
Сообщение12.03.2021, 18:28 
Аватара пользователя


22/11/13
496
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$-ной системе счисления.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group