2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача про пятерки и семерки
Сообщение04.08.2016, 10:41 
Заморожен
Аватара пользователя


31/10/11
123
Челябинск
На конкурсе Gordian Knot (The Project Euler of Felicity, январь 2014 г.) предлагалась такая задача:
сколько существует 15-значных чисел, составленных из цифр 5 и 7, и кратных 5 и 7?

Решая эту задачу, я сделал такое наблюдение.

Пусть $a_{n.k}$ - количество $n$-значных чисел указанного вида и имеющих остаток $k$ от деления на 7. Тогда для любых $n$, $i$ и $j$ справедливо $|a_{n,i}-a_{n,j}|\le1$.

Отсюда следует, что $a_{n,k}\approx 2^n/7$.

Чтобы решить исходную задачу, нужно найти $a_{14,3}$ (поскольку к 14-значному числу нужно приписать 5).

Вопросы: 1) как коротко доказать указанное наблюдение?
2) Как ещё можно решать исходную задачу?

Замечание. Можно в условии семерки заменить нулями, пятёрки единицами и рассматривать $n$-значные числа, составленные из нулей и единиц (ведущие нули допускаются), интересуясь их остатками от деления на 7.

 Профиль  
                  
 
 Re: Задача про пятерки и семерки
Сообщение05.08.2016, 08:59 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Т.к. остатки при делении $5, 50, 500, \dots$ на $7$ равны соответственно $5, 1, 3, 2, 6, 4$, то количество чисел с остатками $0,1,2,3,4,5,6$ для чисел со всё большим количеством знаков находится последовательно:

$0$ знаков: $(1,0,0,0,0,0,0)$
$1$ знак $(5): $ $(1+T^5)(1,0,0,0,0,0,0)=(1,0,0,0,0,1,0)$
$2$ знака $(1): $ $(1+T^1)(1,0,0,0,0,1,0)=(1,1,0,0,0,1,1)$
$3$ знака $(3): $ $(1+T^3)(1,1,0,0,0,1,1)=(1,2,1,1,1,1,1)$
$4$ знака $(2): $ $(1+T^2)(1,2,1,1,1,1,1)=(2,3,2,3,2,2,2)$
$5$ знаков $(6): $ $(1+T^6)(2,3,2,3,2,2,2)=(5,5,5,5,4,4,4)$
$6$ знаков $(4): $ $(1+T^4)(5,5,5,5,4,4,4)=(10,9,9,9,9,9,9)=(1,0,0,0,0,0,0)+(9,9,9,9,9,9,9)$

Дальше все зацикливается, так что легко найти количество чисел указанного вида с заданным количеством знаков и заданным остатком при делении на $7$.

Можно было для циклического сдвига $T$ сразу использовать
$(1+T^1)(1+T^2) \cdots (1+T^{p-1}) = 1 + \dfrac{2^{p-1}-1}{p}(1+T^1+T^2 + \cdots + T^{p-1}),$
где $T^p=1$, $p (\ne 2)$ - простое.

 Профиль  
                  
 
 Re: Задача про пятерки и семерки
Сообщение05.08.2016, 09:02 
Заслуженный участник


08/04/08
8556
Я слабый вариант напишу, чтобы хоть какой-то ответ был. не успел :-)

Alexander Evnin в сообщении #1141960 писал(а):
Отсюда следует, что $a_{n,k}\approx 2^n/7$.
Наши числа имеют вид $A=\sum\limits_{k=0}^n10^k(5+2b_k), b_k\in\{0;1\}$.
$A \bmod 7\equiv \sum\limits_{k=0}^n3^k(5+2b_k)=C+2\sum\limits_{k=0}^n3^kb_k=$ $C+2\sum\limits_{r=0}^53^r\sum\limits_{k\equiv r \pmod 7}{b_k \pmod 7}$
Далее достаточно доказывать равномерность распределения $\sum\limits_{r=0}^53^r\sum\limits_{k\equiv r \pmod 7}b_k$, т.к. линейное преобразование на равномерность не влияет.
Значения суммы $\sum\limits_{r=0}^Ac_rx_r$ равномерно распределены на $\mathbb{Z}_p$ при $c_r\not\equiv 0\pmod 7$. При $A=0$ это и так видно, а для остальных $A$ можно доказать по индукции (или по критерию Вейля должно получаться).
Наконец, уравнение $x_r\equiv \sum\limits_{k\equiv r \pmod 7}b_k \pmod 7, b_k\in\{0;1\}$ не дает равномерного распределения числа решений по $x_r$, но это распределение становится равномерным при $k\to\infty$. Это не совсем ясно, но более интуитивно очевидно, чем требуемое утверждение.

Причем значение $k=14$ - это довольно мало, т.к. ему соответствует всего 2 слагаемых, когда распределение еще не равномерно, надо хотя бы $100$ примерно.
При $k=14$ распределение числа решений вообще равномерно? Кто-нибудь считал?

Alexander Evnin в сообщении #1141960 писал(а):
Пусть $a_{n.k}$ - количество $n$-значных чисел указанного вида и имеющих остаток $k$ от деления на 7. Тогда для любых $n$, $i$ и $j$ справедливо $|a_{n,i}-a_{n,j}|\le1$.
Неверно при $n=6,7, i=0$.
Нет, в самом деле - здесь максимальная степень равномерности для всех $n$ :shock:
Т.е. даже не $(\forall i,j)|a_{n,i}-a_{n,j}|\leqslant 1$, а даже $(\forall i)|a_{n,i}-\frac{2^n}{7}|<1$.

 Профиль  
                  
 
 Re: Задача про пятерки и семерки
Сообщение09.08.2016, 16:51 
Заслуженный участник


08/04/08
8556
Нет, это бесполезная задача.
Похоже, что $\sum\limits_{k=0}^n b_ka^k, b_k\in\{0;1\}$ распределено очень равномерно только при $a=\pm 2$ при всех модулях $m$ чисто за счет единственности представления в двоичной системе счисления, остальные случаи (как и приведенный здесь $m=7,a=3$) - чисто спорадические. Никаких закономерностей тут почти не видно. Почему очень равномерное распределение для $n=0$ так и остается очень равномерным для всех $n$ - непонятно. Почему неравномерное распределение никогда не превращается в очень равномерное - тоже непонятно.
Насколько я помню, это характеристика задач с Project Euler - эти задачи чисто для программирования, смысла в них мало.

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

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



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

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


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

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