2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Posted automatically
Сообщение15.03.2015, 17:16 
Модератор


20/03/14
7799
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: Сколько 2014-значных чисел из 1,3,4,6,7,9 делится на 7
Сообщение15.03.2015, 22:21 
Заслуженный участник
Аватара пользователя


24/02/12
1749
Москва
На последнем шаге можно попасть в отсутствующий остаток и единицы не будет. Надо последить за остатками во время рекурсии, это нетрудно.

 Профиль  
                  
 
 Re: Сколько 2014-значных чисел из 1,3,4,6,7,9 делится на 7
Сообщение12.09.2017, 09:19 
Заслуженный участник


08/04/08
8417
Честно говоря по намекам я так и не понял, как эту задачу решали.
Я вчера смог так: сначала задачу надо максимально параметризовать, потом рассмотреть рекуррентное соотношение для суммы, выражающей число из цифр.
Пусть $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 
Модератор
Аватара пользователя


11/01/06
5240
Sonic86 в сообщении #1247134 писал(а):
Можно было бы еще поковырять, что там м.б. интересного в общем случае, но что-то ничего не придумал :-(

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу Пред.  1, 2

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



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

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


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

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