Задача про пятерки и семерки

[Alexander Evnin]

На конкурсе 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.

[TOTAL]

Т.к. остатки при делении $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)$ - простое.

[Sonic86]

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

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$
Т.е. даже не $(\forall i,j)|a_{n,i}-a_{n,j}|\leqslant 1$, а даже $(\forall i)|a_{n,i}-\frac{2^n}{7}|<1$.

[Sonic86]

Нет, это бесполезная задача.
Похоже, что $\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 - эти задачи чисто для программирования, смысла в них мало.