2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Posted automatically
Сообщение15.03.2015, 17:16 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: Сколько 2014-значных чисел из 1,3,4,6,7,9 делится на 7
Сообщение15.03.2015, 22:21 
Аватара пользователя
На последнем шаге можно попасть в отсутствующий остаток и единицы не будет. Надо последить за остатками во время рекурсии, это нетрудно.

 
 
 
 Re: Сколько 2014-значных чисел из 1,3,4,6,7,9 делится на 7
Сообщение12.09.2017, 09:19 
Честно говоря по намекам я так и не понял, как эту задачу решали.
Я вчера смог так: сначала задачу надо максимально параметризовать, потом рассмотреть рекуррентное соотношение для суммы, выражающей число из цифр.
Пусть $M$ - множество цифр, $p$ - модуль, $r$ - остаток по модулю, $q$ - основание системы счисления, $a_k$ - последовательность цифр, $a_k \in M$, $b_n=\sum\limits_{k=0}^n q^ka_k$ (все параметры $b_n$ не пишу).
Рекуррентное соотношение: $b_n=b_{n-1}+q^na_n$.
Теперь рассмотрим распределение значений величины $b_n \pmod p$ - некий вектор размера $p$ (сумма компонент $=q^n$). Из него легко вычислить распределение значений $b_{n+1} \pmod p$ - это сумма $|M|$ векторов, полученных сдвигом $b_n \pmod p$ на понятно какую величину. Множество сдвигов каждый раз разное, но периодично с периодом, который делит $p-1$, если $p$ простое (если не простое, то то же самое, но картина посложнее). И все, можно просто решить рекуррентное соотношение. В исходном случае это довольно просто, а вот например при $p=5, M=\{0;1;3\}$ сразу везде лезут числа Фибоначчи.

Можно было бы еще поковырять, что там м.б. интересного в общем случае, но что-то ничего не придумал :-(

 
 
 
 Re: Сколько 2014-значных чисел из 1,3,4,6,7,9 делится на 7
Сообщение12.09.2017, 20:30 
Аватара пользователя
Sonic86 в сообщении #1247134 писал(а):
Можно было бы еще поковырять, что там м.б. интересного в общем случае, но что-то ничего не придумал :-(

Через мультисекцию производящей функции можно получить явную формулу.

 
 
 [ Сообщений: 19 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group