Задача 4. Степени двойки и большие остатки

Что именно надо посчитать

Сумма различных степеней двойки — это двоичная запись числа. Например, $93=64+16+8+4+1$, а в двоичной системе $93=1011101_2$: каждому слагаемому соответствует одна единица записи, а пропущенным степеням ($32$ и $2$) — нули.

Такое представление у натурального числа только одно. Пусть наибольшее слагаемое — $2^s$. Тогда вся сумма не меньше $2^s$ и не больше суммы $1+2+4+\ldots+2^s$ всех степеней двойки до $2^s$. А эта сумма на $1$ меньше, чем $2^{s+1}$. Прибавь к ней $1$ — и она «схлопнется»: $1+1=2$, потом $2+2=4$, и так далее, пока не останется $2^s+2^s=2^{s+1}$. Поэтому

Значит, $2^s$ — наибольшая степень двойки, не превосходящая нашего числа, и её выбирает само число. Вычтем её и повторим рассуждение для того, что осталось.

Слово «целочисленных» разрешает и степени с отрицательным показателем: $\frac12$, $\frac14$, $\frac18$, … Но они не помогут. Несколько различных таких степеней вместе дают больше $0$, но меньше $1$: даже если взять все подряд до $\frac1{2^t}$, получится $1-\frac1{2^t}$ (например, $\frac12+\frac14+\frac18=\frac78$). А остальные слагаемые в сумме дают целое число. Целое число плюс дробь между $0$ и $1$ — не целое, поэтому в представлении целого числа дробных степеней нет.

Итак, количество слагаемых — это количество единиц в двоичной записи числа $N=\dfrac{2^n-1}{m}$. Его и будем считать.

Делим степени двойки на m по очереди

Само число $N$ огромное, и сразу его двоичную запись не увидеть. Зато легко понять, что происходит при переходе от одной степени двойки к следующей. Поэтому разделим с остатком на $m$ все степени двойки по очереди:

Начало: $2^0=1=m\cdot 0+1$ (ведь $m>1$), то есть $q_0=0$ и $r_0=1$.

Два наблюдения про остатки. Остаток не бывает нулём: у числа $2^j$ нет нечётных делителей, кроме $1$, а $m$ нечётное и больше $1$. И остаток не бывает равен $\frac m2$: число $m$ нечётное, поэтому $\frac m2$ — не целое. Значит, каждый остаток либо маленький — меньше $\frac m2$, либо большой — больше $\frac m2$.

Удвоим равенство: $2^{j+1}=m\cdot 2q_j+2r_j$.

Остаток $r_j$ маленький. Тогда $2r_j<m$, и это уже деление с остатком: $q_{j+1}=2q_j$, $r_{j+1}=2r_j$.

Остаток $r_j$ большой. Тогда $m<2r_j<2m$. Отнимем от $2r_j$ одно $m$ и добавим его к произведению $m\cdot 2q_j$. Обозначим $r=2r_j-m$; тогда $0<r<m$ и

Это деление с остатком, значит, $q_{j+1}=2q_j+1$ и $r_{j+1}=2r_j-m$.

Пример для $m=11$: остатки $1$, $2$, $4$ маленькие и просто удваиваются. Остаток $r_3=8$ большой ($8>5{,}5$), поэтому $2^4=16=11\cdot 1+5$: частное стало $2\cdot 0+1=1$, остаток $16-11=5$.

Частное записывается цифра за цифрой

Что делают переходы $q_{j+1}=2q_j$ и $q_{j+1}=2q_j+1$ с двоичной записью частного? Умножить на $2$ в двоичной системе — то же, что в десятичной умножить на $10$: приписать справа $0$. Например, $101_2=5$, а $1010_2=10$. Значит, $2q_j+1$ — это приписать справа $1$.

Получается, что двоичная запись частного растёт по одной цифре справа: на шаге $j$ приписывается $0$, если остаток $r_j$ маленький, и $1$, если он большой. Мы начали с $q_0=0$, поэтому в двоичной записи числа $q_n$ столько единиц, сколько больших остатков среди $r_0, r_1, \ldots, r_{n-1}$.

Осталось заметить, что $q_n$ — это и есть наше число $N$. По условию $2^n-1=m\cdot N$, то есть

и $1<m$. Это деление $2^n$ на $m$ с остатком, поэтому $q_n=N$ и $r_n=1$.

Вывод: количество слагаемых равно количеству больших остатков среди $r_0, r_1, \ldots, r_{n-1}$.

Для $m=11$ и $n=10$ (таблица ниже) большие остатки — $8$, $10$, $9$, $7$ и $6$, на шагах $3$, $5$, $6$, $7$ и $9$. И действительно, $\frac{1023}{11}=93=1011101_2$ — ровно $5$ единиц. По сути, мы делим $2^n=100\ldots0_2$ на $m$ столбиком в двоичной системе; в модели «Двоичный столбик» это можно сделать самому.

Остатки идут по кругу

Теперь выясним, как часто попадаются большие остатки. Каждый следующий остаток вычисляется только по предыдущему: удвоить и, если получилось больше $m$, вычесть $m$. Важно, что и предыдущий остаток восстанавливается по следующему. После маленького остатка следующий равен $2r_j$ — он чётный. После большого следующий равен $2r_j-m$ — он нечётный (чётное минус нечётное). Поэтому по $r_{j+1}$ видно, какой был случай, и

Остаток $1$ ещё встретится: $r_n=1$. Пусть $d$ — первый номер, начиная с $1$, для которого снова $r_d=1$.

Остатки $r_0, r_1, \ldots, r_{d-1}$ все различны. Допустим, $r_i=r_j$ при $i<j<d$. Сделаем от обоих остатков по одному шагу назад: по одинаковым остаткам восстанавливаются одинаковые, значит, $r_{i-1}=r_{j-1}$. Повторив это $i$ раз, получим $r_0=r_{j-i}$, то есть $r_{j-i}=1$, где $0<j-i<d$. Но $d$ — первый такой номер. Противоречие.

После $r_d=1=r_0$ всё повторяется: $r_{d+1}=r_1$, $r_{d+2}=r_2$, и так далее. Значит, остатки степеней двойки идут по кругу из $d$ различных чисел $r_0, \ldots, r_{d-1}$, и других остатков у степеней двойки нет. По условию ровно $k$ из этих чисел больше $\frac m2$: на каждом круге ровно $k$ больших остатков.

(Поэтому и неважно, считать ли $2^0=1$ степенью двойки: остаток $1$ всё равно встречается — у числа $2^d$.)

Для $m=11$ круг такой: 1, 2, 4, 8, 5, 10, 9, 7, 3, 6 — всего $d=10$ остатков, из них $k=5$ больших (рисунок ниже).

Считаем большие остатки

Сначала докажем, что $n$ делится на $d$. Разделим с остатком: $n=d\cdot t+s$, где $0\le s<d$. Остатки повторяются через каждые $d$ шагов, поэтому $r_n=r_s$. Но $r_n=1$, а среди различных чисел $r_0, \ldots, r_{d-1}$ единица только одна — $r_0$. Значит, $s=0$ и $n=d\cdot t$.

Тогда остатки $r_0, r_1, \ldots, r_{n-1}$ — это ровно $t$ полных кругов, и на каждом круге $k$ больших. Всего больших остатков $k\cdot t$, и по шагу 3 столько же слагаемых в сумме. Так как $t=\frac nd$, количество слагаемых равно

Это число делится на $k$, что и требовалось доказать.

Пример: $m=11$, $d=10$, $k=5$. При $n=20$ получаем $\frac{2^{20}-1}{11}=95325$, а в двоичной записи это $10111010001011101_2$ — в ней $10=5\cdot 2$ единиц. Цифры $0001011101$ первого круга повторились во втором (нули в начале записи просто не пишутся).