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 ] 

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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