Слишком много двоек

Условие задачи

Для ненулевого целого $n$ обозначим через $\nu_2(n)$ наибольшее $r$, для которого $2^r$ делит $n$. Определим

$$ S(n)=\sum_{k=1}^{n}(-2)^k\binom{2k}{k}, \qquad u(n)=\nu_2\bigl(3S(n)+4\bigr), $$

а затем $U(N)=\sum_{n=1}^{N}u(n^3)$. Из условия известны $u(4)=7$, $u(20)=24$ и $U(5)=241$. Требуется найти $U(10^4)$. Полное условие доступно на странице Project Euler 792.

Разбор решения

В этой задаче всё устроено так, чтобы первая естественная идея оказалась почти бесполезной. Нам дают

\[ S(n)=\sum_{k=1}^{n}(-2)^k\binom{2k}{k}, \qquad u(n)=\nu_2\bigl(3S(n)+4\bigr), \]

а затем просят сложить \(u(m^3)\) для \(m\le 10^4\). Последний аргумент равен \(10^{12}\). Уже одно это говорит: вычислять \(S(n)\) по определению нельзя. Даже если забыть про размер целых чисел, понадобилось бы порядка \(10^{12}\) членов только для одного последнего значения.

Но задача спрашивает не само число \(3S(n)+4\). Ей нужна только позиция его первой единицы в двоичной записи, то есть количество нулей на конце. Это совсем другая информация. Иногда ради неё можно выбросить почти всё число — и здесь именно такой случай.

Мой путь к решению начался с трёх наблюдений. Сначала я выписал несколько значений и увидел, что \(u(n)\) держится рядом с \(n\). Затем посмотрел на формулу Лежандра и теорему Куммера: они объяснили, почему рядом с \(n\) постоянно возникает число единиц в двоичной записи. Наконец, производящая функция центральных биномиальных коэффициентов подсказала, что конечная сумма является началом ряда, который сходится в мире \(2\)-адических чисел. После этого огромная сумма развернулась: вместо первых \(n\) членов оказалось достаточно исследовать несколько членов после \(n\).

Ниже я проведу основную линию до конца, а затем вернусь к альтернативам. У этой задачи действительно много дверей: конечное биномиальное тождество, последовательность OEIS, рекуррентность, теорема Куммера, вычисление биномиалов по модулю \(2^r\), гипергеометрическая форма и короткий \(2\)-адический хвост. Они описывают один объект с разных сторон, но вычислительно ведут себя очень по-разному.

1. Что именно измеряет \(\nu_2\)

Для ненулевого целого \(x\)

\[ \nu_2(x)=r \quad\Longleftrightarrow\quad x=2^r q,\qquad q\text{ нечётно}. \]

Это не просто «сколько раз число делится на два». У valuation есть правило, которое управляет всей задачей:

\[ \nu_2(x+y)\ge \min\bigl(\nu_2(x),\nu_2(y)\bigr). \]

Если две valuation различны, неравенство превращается в равенство:

\[ \nu_2(x)<\nu_2(y) \quad\Longrightarrow\quad \nu_2(x+y)=\nu_2(x). \]

Причина проста. Пусть \(x=2^r a\), где \(a\) нечётно, а \(y=2^{r+d}b\), где \(d>0\). Тогда

\[ x+y=2^r\bigl(a+2^d b\bigr), \]

и выражение в скобках остаётся нечётным. Член с меньшей valuation безраздельно определяет первую ненулевую двоичную цифру суммы.

Опасность возникает только при ничьей. Если

\[ \nu_2(x)=\nu_2(y)=r, \]

то после вынесения \(2^r\) складываются два нечётных числа. Их сумма чётна, поэтому valuation обязательно поднимается хотя бы на один, а иногда сразу на несколько уровней. В обычной арифметике мы спрашиваем, насколько велики слагаемые; здесь важнее узнать, на каком двоичном этаже они впервые появляются и не уничтожают ли друг друга на этом этаже.

Именно поэтому дальнейшее решение естественно делится на два случая:

• если среди valuation слагаемых есть единственный минимум, ответ известен сразу;
• если минимум повторяется, приходится вычислять нечётные части и отслеживать переносы.

2. Двоичный вес и центральный биномиальный коэффициент

Обозначим через \(s_2(m)\) число единиц в двоичной записи \(m\). Например,

\[ 13=1101_2, \qquad s_2(13)=3. \]

Формула Лежандра при \(p=2\) принимает особенно красивый вид:

\[ \nu_2(m!)=\sum_{j\ge1}\left\lfloor\frac{m}{2^j}\right\rfloor =m-s_2(m). \]

Применим её к центральному биномиальному коэффициенту:

\[ \begin{aligned} \nu_2\binom{2m}{m} &=\nu_2((2m)!)-2\nu_2(m!)\\ &=\bigl(2m-s_2(2m)\bigr)-2\bigl(m-s_2(m)\bigr). \end{aligned} \]

Умножение на два просто приписывает двоичной записи ноль, поэтому \(s_2(2m)=s_2(m)\). Следовательно,

\[ \boxed{\nu_2\binom{2m}{m}=s_2(m).} \]

Это частный случай теоремы Куммера: valuation биномиального коэффициента равна числу переносов при сложении соответствующих чисел в системе счисления по основанию \(p\). Для \(\binom{2m}{m}\) мы складываем \(m+m\) в двоичной системе; число переносов оказывается равным \(s_2(m)\).

Теперь рассмотрим отдельное слагаемое исходной суммы:

\[ t_m=(-2)^m\binom{2m}{m}. \]

Его valuation равна

\[ \boxed{\nu_2(t_m)=m+s_2(m).} \]

Главный член — линейный \(m\). Двоичный вес добавляет лишь \(O(\log m)\). Вот первое объяснение того, почему искомое \(u(n)\) должно быть близко к \(n\).

3. Первая дверь: точное конечное тождество

До \(2\)-адических чисел можно дойти не сразу. Сначала полезно преобразовать конечную сумму в другую конечную сумму. Введём

\[ a_n=\sum_{j=0}^{n}(-2)^j\binom{2n+1}{n-j}. \]

Тогда выполняется точное тождество

\[ \boxed{3S(n)+4=(-2)^{n+2}a_n.} \tag{1} \]

Проверка для \(n=4\) уже выглядит обнадёживающе:

\[ a_4=46, \qquad (-2)^6a_4=64\cdot46=2944. \]

Отсюда немедленно следует

\[ \boxed{u(n)=n+2+\nu_2(a_n).} \tag{2} \]

То есть почти вся valuation известна заранее. Трудная часть, \(\nu_2(a_n)\), растёт лишь логарифмически.

3.1. Аккуратное доказательство тождества

Сумму \(a_n\) удобно записать как коэффициент:

\[ a_n=[x^n]\frac{(1+x)^{2n+1}}{1+2x}. \tag{3} \]

Действительно, разложение \(1/(1+2x)=\sum_{j\ge0}(-2x)^j\) даёт именно нужную свёртку коэффициентов. Обозначим

\[ F_n(x)=\frac{(1+x)^{2n+1}}{1+2x}, \qquad f_r=[x^r]F_n(x). \]

Из равенства \((1+2x)F_n(x)=(1+x)^{2n+1}\) получаем

\[ f_{n+1}+2f_n=\binom{2n+1}{n+1}=\binom{2n+1}{n} \]

и

\[ f_n+2f_{n-1}=\binom{2n+1}{n}. \]

Поскольку \(F_{n+1}(x)=(1+x)^2F_n(x)\),

\[ \begin{aligned} a_{n+1} &=[x^{n+1}](1+x)^2F_n(x)\\ &=f_{n+1}+2f_n+f_{n-1}\\ &=\binom{2n+1}{n}+\frac{\binom{2n+1}{n}-a_n}{2}. \end{aligned} \]

Значит,

\[ 2a_{n+1}+a_n=3\binom{2n+1}{n}. \tag{4} \]

Положим \(R_n=(-2)^{n+2}a_n\). Тогда

\[ \begin{aligned} R_{n+1}-R_n &=(-2)^{n+2}\bigl(-2a_{n+1}-a_n\bigr)\\ &=-3(-2)^{n+2}\binom{2n+1}{n}\\ &=3(-2)^{n+1}\binom{2n+2}{n+1}. \end{aligned} \]

Но правая часть — ровно приращение \(3S(n)\) при переходе от \(n\) к \(n+1\). При \(n=0\) обе стороны (1) равны \(4\), поэтому тождество доказано индукцией.

3.2. Неожиданная встреча с OEIS

Первые значения \(a_n\) таковы:

\[ 1,1,4,13,46,166,610,2269,8518,\ldots \]

Это OEIS A026641. У последовательности есть совсем иная комбинаторная интерпретация: она считает вершины чётной исходящей степени во всех упорядоченных деревьях с \(n\) рёбрами. Для нашей задачи важнее другие записи с той же страницы:

\[ A(z)=\sum_{n\ge0}a_nz^n =\frac{2}{3\sqrt{1-4z}-1+4z}, \tag{5} \]

а также D-конечная рекуррентность

\[ 2n a_n+(4-7n)a_{n-1}+2(1-2n)a_{n-2}=0. \tag{6} \]

Эта находка полезна концептуально: странная сумма не случайна, она сидит внутри хорошо изученной алгебраической производящей функции. Но вычислительно рекуррентность (6) обманчива. Чтобы добраться до \(a_{10^{12}}\), линейный проход всё равно потребует \(10^{12}\) шагов. Попытка ускорить рекуррентность матричными произведениями сталкивается с делением на \(n\), а чётные знаменатели нельзя просто обратить по модулю \(2^r\). Поэтому OEIS объясняет структуру, но не даёт самого короткого алгоритма.

4. Вторая дверь: сумма, которая расходится в \(\mathbb R\), но сходится в \(\mathbb Q_2\)

Теперь начинается самый красивый поворот.

Известная производящая функция центральных биномиальных коэффициентов имеет вид

\[ \frac1{\sqrt{1-4x}} =\sum_{k=0}^{\infty}\binom{2k}{k}x^k. \tag{7} \]

В вещественных числах подставлять \(x=-2\) нельзя: члены растут примерно как \(8^k/\sqrt{k}\). Но \(2\)-адическая сходимость смотрит не на вещественный размер. Ряд сходится, если valuation его членов стремится к бесконечности. А мы уже знаем

\[ \nu_2\left((-2)^k\binom{2k}{k}\right)=k+s_2(k)\longrightarrow\infty. \]

Следовательно,

\[ T=\sum_{k=0}^{\infty}(-2)^k\binom{2k}{k} \]

корректно определён в \(\mathbb Q_2\). Хорошее строгое введение в такую сходимость и ультраметрическое неравенство можно найти в конспекте по \(p\)-адическим числам.

Формальное тождество (7) можно возвести в квадрат, а затем непрерывно вычислить при \(x=-2\). Получаем

\[ T^2=\frac1{1-4(-2)}=\frac19. \]

Значит, \(T=\pm1/3\). В \(2\)-адическом мире нельзя выбирать знак по вещественному понятию «положительности», поэтому посмотрим на несколько младших битов. Все члены начиная с \(k=2\) делятся на \(8\), следовательно,

\[ T\equiv1-4\equiv5\pmod8. \]

При этом

\[ -\frac13\equiv5\pmod8, \]

так что правильная ветвь корня равна

\[ \boxed{T=-\frac13.} \tag{8} \]

Поскольку \(S(n)\) начинается с \(k=1\), бесконечный предел равен

\[ \sum_{k=1}^{\infty}(-2)^k\binom{2k}{k} =T-1=-\frac43. \]

И вот зачем в условии стояла комбинация \(3S(n)+4\): она уничтожает весь бесконечный ряд.

\[ \begin{aligned} 3S(n)+4 &=-3\sum_{k=n+1}^{\infty}(-2)^k\binom{2k}{k}. \end{aligned} \tag{9} \]

Множитель \(-3\) нечётен и valuation не меняет. Поэтому

\[ \boxed{ u(n)=\nu_2\left(\sum_{k=n+1}^{\infty}(-2)^k\binom{2k}{k}\right). } \tag{10} \]

Исходные \(n\) членов исчезли. Остался хвост, и valuation его членов быстро растёт.

5. Сначала попробуем обойтись только valuation слагаемых

Положим

\[ \lambda(k)=\nu_2(t_k)=k+s_2(k). \]

Если минимум \(\lambda(k)\) среди \(k>n\) достигается ровно один раз, ультраметрическое правило немедленно даёт

\[ u(n)=\min_{k>n}\lambda(k). \tag{11} \]

Бесконечный минимум искать не нужно. Первый кандидат \(k=n+1\) имеет высоту

\[ \lambda(n+1)=n+1+s_2(n+1). \]

А для

\[ k\ge n+1+s_2(n+1) \]

выполнено

\[ \lambda(k)\ge k+1>\lambda(n+1). \]

Значит, достаточно проверить короткое окно

\[ n+1\le k<n+1+s_2(n+1), \tag{12} \]

длина которого не превосходит числа двоичных разрядов \(n\).

Например, при \(n=20\)

\[ \lambda(21)=21+s_2(21)=21+3=24 \]

и это единственный минимум. Мы сразу получаем данное в условии \(u(20)=24\), не вычислив ни одного большого биномиального коэффициента.

Для кубов \(m^3\), \(1\le m\le10^4\), критерий единственного минимума срабатывает в \(9618\) случаях. Остаются \(382\) ничьи, причём в каждом из них минимальных членов ровно два. Это уже решает более \(96\%\) задачи с помощью одних двоичных весов.

6. Почему ничья меняет всё

Рассмотрим первый особенно наглядный куб:

\[ n=21^3=9261. \]

В хвосте два одинаковых минимальных уровня:

\[ \lambda(9262)=9268, \qquad \lambda(9264)=9268. \]

Если бы минимум был один, ответом было бы \(9268\). Но после деления соответствующих слагаемых на \(2^{9268}\) их нечётные части по модулю \(64\) равны \(25\) и \(55\). Уже их сумма

\[ 25+55=80=16\cdot5 \]

содержит четыре дополнительные двойки. Члены следующих уровней тоже участвуют в переносах. Если последовательно добавить существенные слагаемые хвоста и каждый раз смотреть на накопленный остаток по модулю \(64\), получится двоичная картина ниже.

Финальный остаток на этом масштабе равен \(48=110000_2\): четыре младших бита исчезли, поэтому valuation хвоста поднимается с \(9268\) до \(9272\). Этот пример хорошо показывает, почему одной функции \(k+s_2(k)\) недостаточно. Она говорит, где могут начаться слагаемые, но при совпадении уровней надо знать хотя бы несколько битов их нечётных частей.

7. Рекомендуемый путь: вынести первый член хвоста

Можно вычислять нечётные части центральных биномиальных коэффициентов по модулю \(2^r\). Это универсальный путь, и мы к нему вернёмся. Но в данной задаче есть более короткий приём: отношения соседних слагаемых известны точно.

Напомним

\[ t_k=(-2)^k\binom{2k}{k}. \]

Тогда

\[ \frac{t_{k+1}}{t_k} =-2\frac{(2k+2)(2k+1)}{(k+1)^2} =-4\frac{2k+1}{k+1}. \tag{13} \]

Вынесем первый член хвоста:

\[ \sum_{k=n+1}^{\infty}t_k=t_{n+1}R_n, \]

где

\[ R_n=1+r_1+r_2+\cdots, \qquad r_j=\frac{t_{n+1+j}}{t_{n+1}}. \]

Начинаем с \(r_0=1\), а последующие члены получаем рекуррентно:

\[ \boxed{ r_{j+1}=r_j\left(-4\frac{2n+2j+3}{n+j+2}\right). } \tag{14} \]

Ни одного огромного \(\binom{2k}{k}\) в этой формуле нет. В каждом шаге участвуют лишь числа порядка \(n\), то есть не более \(40\) бит при \(n\le10^{12}\).

Valuation вынесенного члена известна по формуле Куммера:

\[ \nu_2(t_{n+1})=n+1+s_2(n+1). \]

Следовательно,

\[ \boxed{ u(n)=n+1+s_2(n+1)+\nu_2(R_n). } \tag{15} \]

Именно эта формула является самой удобной вычислительной магистралью.

7.1. Почему хвост можно остановить строго, а не «на глаз»

Нужно убедиться, что обрезание бесконечного \(R_n\) не меняет valuation. Для отдельного нормированного члена

\[ \begin{aligned} \nu_2(r_j) &=\nu_2(t_{n+1+j})-\nu_2(t_{n+1})\\ &=j+s_2(n+1+j)-s_2(n+1). \end{aligned} \tag{16} \]

Пусть

\[ R_n^{(J)}=\sum_{j=0}^{J}r_j \]

— уже вычисленная часть. Обозначим \(s=s_2(n+1)\). Для любого пропущенного \(j\ge J+1\)

\[ \nu_2(r_j) =j+s_2(n+1+j)-s \ge J+2-s. \]

Поэтому условие

\[ \boxed{ \nu_2\bigl(R_n^{(J)}\bigr)<J+2-s_2(n+1) } \tag{17} \]

является сертификатом завершения. Вся оставшаяся бесконечная сумма начинается строго выше уже найденной первой единицы и изменить её не может.

Это важная деталь. Мы не утверждаем заранее, что «двадцати членов обычно хватает». Мы увеличиваем \(J\), пока не получим проверяемое неравенство (17). Так исключаются неприятные редкие случаи с длинной цепочкой отмен.

Для всех \(10^4\) требуемых кубов самый длинный реально понадобившийся префикс дошёл лишь до \(J=32\). Это не предположение алгоритма, а результат применения строгого критерия к каждому аргументу.

7.2. Как складывать рациональные числа \(2\)-адически

В (14) встречаются знаменатели. Это не проблема. Любое ненулевое рациональное число можно представить как

\[ x=2^e\frac{p}{q}, \]

где \(p\) и \(q\) нечётны. Тогда \(\nu_2(x)=e\), а \(q\) обратимо по модулю любой степени двойки. Для вычисления нескольких младших \(2\)-адических битов достаточно хранить:

• показатель \(e\);
• нечётную единицу \(p q^{-1}\pmod{2^r}\).

При умножении показатели складываются, единицы перемножаются. При сложении выносится меньшая степень двойки, а единицы складываются на общем уровне. Если младшие биты уничтожились, valuation результата повышается — ровно тот эффект, который мы видели при \(n=9261\).

Для математической проверки можно вообще хранить обычные точные рациональные числа: префикс короткий, поэтому числители и знаменатели остаются умеренного размера. Для быстрой реализации удобнее нормализованная пара «valuation + нечётная единица по модулю \(2^r\)».

8. Как из отдельных \(u(m^3)\) получается \(U(N)\)

Подставим \(n=m^3\) в (15). Если обозначить

\[ c_m=\nu_2(R_{m^3}), \]

то

\[ u(m^3)=m^3+1+s_2(m^3+1)+c_m. \]

Сумма кубов известна:

\[ \sum_{m=1}^{N}m^3 =\left(\frac{N(N+1)}2\right)^2. \]

Поэтому

\[ \boxed{ U(N)= \left(\frac{N(N+1)}2\right)^2 +N +\sum_{m=1}^{N}s_2(m^3+1) +\sum_{m=1}^{N}c_m. } \tag{18} \]

Первая часть вычисляется в замкнутом виде. Двоичный вес считается непосредственно по записи \(m^3+1\). Коррекция \(c_m\) получается из короткого хвоста и критерия (17).

На требуемом диапазоне в \(9235\) случаях из \(10000\) коррекция \(c_m\) равна нулю. Но редкие ненулевые коррекции нельзя просто игнорировать: они имеют оба знака и иногда по модулю достигают двузначных значений.

9. Почти правильная формула и ловушка «ответ сошёлся случайно»

Эксперименты быстро подталкивают к ещё более простой догадке:

\[ u(m^3)\stackrel{?}{\approx}m^3+s_2(m^3)+1. \tag{19} \]

Она выглядит правдоподобно из-за формулы Куммера и действительно даёт удивительно точную сумму. Определим накопленную ошибку

\[ D(M)=\sum_{m=1}^{M} \Bigl(u(m^3)-m^3-s_2(m^3)-1\Bigr). \]

Отдельные ошибки вовсе не малы и не всегда нулевые, но положительные и отрицательные отклонения долго компенсируют друг друга. При \(M=10^4\) наивная сумма промахивается всего на единицу. Это прекрасная проверка здравого смысла и одновременно опасная ловушка: близость итогов не доказывает формулу для отдельных членов.

Математическая причина близости ясна. Первый хвостовой член даёт \(n+1+s_2(n+1)\), а добавочные изменения возникают только из переносов и совпадений низких уровней. Они логарифмические на фоне основного \(n\) и часто меняют знак. Но утверждение о почти полной компенсации на конкретном конечном диапазоне остаётся наблюдением, а не заменой точного вычисления.

10. Альтернативная ветка: считать \(a_n\pmod{2^r}\)

Вернёмся к конечному тождеству (1). Оно предлагает другой строгий алгоритм:

\[ a_n=\sum_{j=0}^{n}(-2)^j\binom{2n+1}{n-j}. \]

Если нужна valuation меньше \(r\), все члены с \(j\ge r\) автоматически исчезают по модулю \(2^r\). Поэтому

\[ a_n\equiv \sum_{j=0}^{r-1}(-2)^j\binom{2n+1}{n-j}\pmod{2^r}. \tag{20} \]

Если полученный остаток ненулевой, его число конечных двоичных нулей и есть \(\nu_2(a_n)\). Если остаток равен нулю, увеличиваем \(r\) и повторяем. На рассматриваемых кубах максимальная встретившаяся valuation \(a_{m^3}\) равна \(32\), поэтому несколько десятков бит точности достаточно, но алгоритм не обязан знать это заранее.

10.1. Соседние биномиальные коэффициенты

Положим

\[ B_j=\binom{2n+1}{n-j}. \]

Тогда

\[ \frac{B_{j+1}}{B_j}=\frac{n-j}{n+j+2}. \tag{21} \]

Значит, после вычисления \(B_0=\binom{2n+1}{n}\) остальные \(r-1\) коэффициентов строятся короткой рекуррентностью. Деление снова выполняется после отделения степеней двойки: нечётная часть знаменателя обратима по модулю \(2^r\).

Valuation каждого \(B_j\) можно получить без самого коэффициента по теореме Куммера:

\[ \nu_2(B_j) =s_2(n-j)+s_2(n+j+1)-s_2(2n+1). \tag{22} \]

Остаётся трудная деталь: найти нечётную часть огромного \(B_0\).

10.2. Нечётная часть факториала

Определим

\[ F_r(m)=\frac{m!}{2^{\nu_2(m!)}}\pmod{2^r}. \]

Тогда нечётная часть биномиального коэффициента выражается через

\[ F_r(2n+1)F_r(n)^{-1}F_r(n+1)^{-1}\pmod{2^r}. \]

Все обратные существуют, потому что \(F_r(m)\) нечётно. Нечётный факториал имеет естественную рекурсию. Если

\[ P_r(m)=\prod_{\substack{1\le j\le m\\j\text{ нечётно}}}j\pmod{2^r}, \]

то после удаления одного множителя \(2\) из каждого чётного числа остаются нечётные части чисел до \(\lfloor m/2\rfloor\). Поэтому

\[ F_r(m)=P_r(m)F_r\left(\left\lfloor\frac m2\right\rfloor\right), \]

и, разворачивая рекурсию,

\[ F_r(m)=\prod_{q\ge0}P_r\left(\left\lfloor\frac{m}{2^q}\right\rfloor\right). \tag{23} \]

Для малой точности таблицу префиксных произведений нечётных остатков можно подготовить заранее. Для большой точности и огромных аргументов нужен более серьёзный алгоритм. Стандартная ссылка здесь — обзор Эндрю Гранвилла The Arithmetic Properties of Binomial Coefficients, где биномиальные коэффициенты систематически вычисляются по модулю степеней простого числа.

Эта ветка универсальна: она работает не только с центральными биномиальными коэффициентами и не зависит от удачного отношения (13). Но для конкретной задачи 792 она тяжелее, чем нормированный хвост.

11. Гипергеометрическая дверь

Конечная сумма \(a_n\) является гипергеометрическим многочленом. Вынесем центральный коэффициент:

\[ \frac{\binom{2n+1}{n-j}}{\binom{2n+1}{n}} =\frac{(-1)^j(-n)_j}{(n+2)_j}, \]

где \((x)_j\) — возрастающий факториал Похгаммера. Поэтому

\[ \boxed{ a_n=\binom{2n+1}{n}\, {}_2F_1(-n,1;n+2;2). } \tag{24} \]

Ряд заканчивается, потому что параметр \(-n\) — отрицательное целое. Формула (24) удобна, если уже есть библиотека для \(p\)-адических или модульных гипергеометрических вычислений.

У хвостовой формы тоже есть гипергеометрическая запись. Из (14)

\[ R_n={}_2F_1\left(1,n+\frac32;n+2;-8\right) \]

в \(2\)-адическом смысле. Но практический алгоритм от этого не меняется: вычисление гипергеометрического ряда и есть последовательное умножение на рациональное отношение соседних членов. Громкое название здесь полезно скорее для классификации, чем для реализации.

12. Рекуррентность: красивая теория, неудобная арифметика

Производящая функция (5) алгебраична, поэтому последовательность \(a_n\) D-конечна и удовлетворяет (6):

\[ a_n=\left(\frac72-\frac2n\right)a_{n-1} +\left(2-\frac1n\right)a_{n-2}. \tag{25} \]

Для первых миллионов значений это отличный способ. Но у нас нужны только \(10000\) разреженных индексов вида \(m^3\), крупнейший из которых равен \(10^{12}\). Обычная рекурсия тратит работу на все промежуточные индексы.

Можно мечтать о быстром произведении переходных матриц. Над полем рациональных чисел применимы двоичное расщепление и методы для голономных последовательностей. Однако наша конечная цель — арифметика по модулю \(2^r\), а коэффициенты (25) содержат \(1/n\). Когда \(n\) чётно, обратного элемента по модулю \(2^r\) нет. Приходится отдельно отслеживать valuation числителей и знаменателей, после чего метод постепенно превращается в ту же \(2\)-адическую арифметику, но с более тяжёлой организацией.

Вывод не в том, что рекуррентность «плохая». Она превосходно доказывает структурные свойства и порождает последовательность. Просто разреженные гигантские индексы и модуль — не её естественная геометрия.

13. Ещё одна ветка: уровни минимумов вместо полного хвоста

Между чистым критерием единственного минимума и точным рациональным хвостом есть промежуточный алгоритм.

1. Для \(k>n\) вычисляем уровни \(\lambda(k)=k+s_2(k)\).
2. Находим минимальный уровень и все слагаемые на нём.
3. Складываем их нечётные части по модулю небольшой степени двойки.
4. Если они не уничтожились, valuation найдена.
5. Если уничтожились, поднимаемся на следующий уровень и добавляем слагаемые, начинающиеся там.

Это буквально сложение двоичных столбиков снизу вверх. Метод может быть очень быстрым: почти всегда первый уровень содержит один член. Но реализация сложнее, чем короткий хвост, потому что надо аккуратно собирать нечётные части центральных биномиалов. Его главное достоинство — объяснительное: он показывает, что редкие аномалии \(u(n)\) являются не хаосом, а каскадами отмен на нескольких младших уровнях.

13.1. «Постоянный бит»: ещё один взгляд на тот же алгоритм

Можно рассуждать вообще без слов «\(2\)-адическая сходимость», только на языке двоичных записей. Слагаемое

\[ t_k=(-2)^k\binom{2k}{k} \]

делится как минимум на \(2^k\). Поэтому оно не затрагивает разряды с номерами меньше \(k\). После того как мы дошли до члена \(t_k\), все более младшие биты частичной суммы стали постоянными: ни один будущий член уже не сможет их изменить.

Но бесконечная комбинация

\[ 3\sum_{k=1}^{\infty}t_k+4 \]

равна нулю. Следовательно, каждый бит конечной частичной суммы, который уже стал постоянным, обязан совпасть с соответствующим битом нуля. Если среди «замороженных» разрядов вдруг появилась единица, она должна быть уничтожена ещё не учтённой частью, а значит мы неверно оценили границу того, какие разряды действительно заморожены.

В корректной формулировке это приводит к той же проверке: найдя первую единицу частичной хвостовой суммы, нужно убедиться, что valuation каждого оставшегося слагаемого строго выше неё. Тогда единица постоянна, и valuation известна. Условие (17) является компактной алгебраической записью этого рассуждения.

Этот взгляд полезен педагогически. \(2\)-адическая норма перестаёт выглядеть экзотикой: она всего лишь организует вычисление справа налево, от младших двоичных разрядов к старшим.

13.2. Дерево классов по модулю \(2^q\)

Ещё один естественный эксперимент — группировать \(n\) по остаткам modulo \(16,32,64,\ldots\) и искать формулу для \(u(n)-n\) внутри каждого класса. На первых уровнях возникают очень чистые закономерности. Это неудивительно: функции

\[ s_2(n+1+j)-s_2(n+1) \]

полностью определяются цепочками переносов в двоичной записи, а переносы локально зависят от нескольких младших битов.

Для кубов ситуация выглядит особенно соблазнительно. Кубы по модулю \(16\) занимают только классы

\[ 0,1,3,5,7,8,9,11,13,15. \]

Можно построить дерево:

• сначала выбрать остаток \(m^3\bmod16\);
• затем, если на текущем уровне возникает ничья, уточнить остаток по модулю \(32\);
• потом по модулю \(64\), и так далее;
• на каждом листе записать значение коррекции.

Такой алгоритм в принципе точен, если продолжать ветвление до появления сертификата. Но у него есть две проблемы. Во-первых, красивые первые ветви создают ложное ощущение короткой замкнутой формулы. Редкие исключения уходят глубоко в дерево. Во-вторых, дерево фактически вручную воспроизводит вычисление \(\nu_2(R_n)\): каждый новый бит модуля — ещё один \(2\)-адический уровень точности.

Поэтому классы остатков хороши для исследования и визуального поиска закономерностей, но плохи как основной текст доказательства. Хвостовой метод автоматически проходит ровно столько уровней, сколько требуется конкретному \(n\), и не заставляет заранее печатать огромное дерево случаев.

13.3. Взвешенные раскраски как комбинаторное объяснение тождества

У конечного тождества (1) есть не только алгебраическое доказательство. Используя симметрию биномиальных коэффициентов,

\[ \binom{2n+1}{n-j}=\binom{2n+1}{n+j+1}, \]

его правую часть можно записать как

\[ (-2)^{n+2}a_n =-2\sum_{m=n+1}^{2n+1}\binom{2n+1}{m}(-2)^m. \tag{26} \]

Представим \(2n+1\) позиций. Выбираем \(m>n\) небелых позиций, а каждую выбранную красим в один из двух цветов. Таких раскрасок

\[ \binom{2n+1}{m}2^m. \]

Знак \((-1)^m\) зависит от чётности числа небелых позиций, а внешний множитель \(-2\) можно воспринимать как дополнительный двухцветный маркер со сменой знака.

Теперь увеличим \(n\) на единицу, то есть добавим две новые позиции и поднимем минимально допустимое число небелых позиций. Почти все способы раскрасить две новые позиции разбиваются на пары противоположных знаков:

• две небелые позиции дают четыре выбора цветов;
• одна небелая и одна белая тоже дают четыре выбора;
• их чётности различны, поэтому веса сокращаются.

Несокращёнными остаются только граничные конфигурации, у которых старые \(2n+1\) позиций содержали ровно минимально необходимое число небелых. Их суммарный вклад превращается в

\[ 3(-2)^{n+1}\binom{2n+2}{n+1}, \]

то есть в приращение \(3S(n)\). Это комбинаторная тень рекуррентности (4). Она не даёт более быстрого алгоритма, зато объясняет, почему в странном тождестве появляются именно коэффициент \(3\), степень \((-2)^{n+2}\) и центральный биномиальный коэффициент.

13.4. Каталановская ветвь выбора корня

Правильный корень в (8) можно определить ещё одним способом. Производящая функция чисел Каталана

\[ C(x)=\sum_{k\ge0}\frac1{k+1}\binom{2k}{k}x^k =\frac{1-\sqrt{1-4x}}{2x} \]

удовлетворяет

\[ C(x)=1+xC(x)^2. \tag{27} \]

При \(x=-2\) ряд снова сходится \(2\)-адически. Уравнение становится

\[ 2C^2+C-1=0, \]

то есть \(C(-2)\in\{1/2,-1\}\). Но сам ряд начинается как

\[ 1-2+8-\cdots\equiv-1\pmod8, \]

поэтому \(C(-2)=-1\).

Центральная биномиальная производящая функция связана с каталановской равенством

\[ \frac1{\sqrt{1-4x}}=\frac1{1-2xC(x)}. \]

Подставляя \(x=-2\) и \(C(-2)=-1\), получаем

\[ \frac1{1+4C(-2)}=-\frac13. \]

Это тот же результат, но ветвь корня выбирается через квадратичное уравнение Каталана. Такой путь особенно естественен, если начать исследование не с центральных биномиальных коэффициентов, а с их деления на \(k+1\).

13.5. Формальный принцип переноса между \(\mathbb R\) и \(\mathbb Q_2\)

Иногда подстановка \(x=-2\) вызывает закономерный вопрос: почему тождество, знакомое из вещественного анализа, обязано сохраниться в другом поле?

Ответ состоит в том, что равенство (7) прежде всего является равенством формальных степенных рядов над \(\mathbb Q\). Его можно проверить коэффициент за коэффициентом, не говоря ни о вещественных, ни о \(2\)-адических числах. Формальные операции сложения, умножения и возведения в конечную степень сохраняют это равенство.

Дальше мы выбираем полное нормированное поле и точку, в которой оба ряда сходятся. В \(\mathbb Q_2\) при \(x=-2\) valuation коэффициента, умноженного на \(x^k\), стремится к бесконечности. Значит:

• частичные суммы образуют последовательность Коши;
• произведение пределов равно пределу произведений;
• коэффициентное тождество можно вычислить в выбранной точке.

Осторожность требуется при произвольной композиции бесконечных рядов, но здесь мы используем только умножение и квадрат. Поэтому переход полностью строг.

13.6. Оценка сложности разных маршрутов

Полезно сравнить не только формулы, но и объём работы.

Подход	Работа для одного \(u(n)\)	Что происходит при \(n\approx10^{12}\)
Сумма по определению	\(O(n)\) биномиальных членов	практически невозможно
Рекуррентность \(a_0,\ldots,a_n\)	\(O(n)\) шагов	практически невозможно
Единственный минимум \(\lambda(k)\)	\(O(\log n)\) popcount	закрывает большинство кубов
Конечная сумма modulo \(2^r\)	\(O(r)\) биномиалов плюс нечётный факториал	быстро при хорошем алгоритме Granville
Нормированный хвост	\(O(J)\) рациональных отношений	\(J\le32\) на всём нужном диапазоне

Главное различие — зависимость от самого \(n\). В первых двух строках \(n\) задаёт число шагов. В последних трёх оно влияет в основном на длину двоичной записи и размер операндов. Именно такой переход нужен во всех задачах, где индекс огромен, а искомая \(p\)-адическая точность мала.

14. Как выбрать подход

У задачи нет единственного «правильного» языка. Выбор зависит от цели.

Если хочется самого прозрачного доказательства

Начните с конечного тождества

\[ 3S(n)+4=(-2)^{n+2}a_n. \]

Оно полностью элементарно и сразу объясняет линейную часть \(u(n)\).

Если нужен самый короткий точный вычислительный путь

Используйте \(2\)-адический предел, вынесите \(t_{n+1}\), стройте \(r_j\) по (14) и останавливайтесь по сертификату (17). Это избегает и огромных сумм, и вычисления огромного биномиального коэффициента.

Если уже есть библиотека биномиалов по модулю \(p^r\)

Используйте конечную сумму (20), теорему Куммера и нечётные факториалы. Этот путь тяжелее, но лучше переносится на другие простые \(p\) и другие биномиальные задачи.

Если исследуется структура последовательности

Полезны OEIS A026641, производящая функция (5), рекуррентность (6), гипергеометрическая форма (24) и распределение popcount. Они объясняют, откуда взялись закономерности, хотя не все из них одинаково хороши для финального подсчёта.

Если хочется сначала решить большинство случаев без модульной арифметики

Проверяйте уникальность минимума \(\lambda(k)\) в коротком окне (12). Для этой задачи так закрываются \(9618\) из \(10000\) кубов. Оставшиеся случаи передаются точному хвостовому методу.

15. Что здесь особенно легко сделать неправильно

Подставить \(x=-2\) в вещественную производящую функцию без оговорок

В \(\mathbb R\) ряд расходится. Подстановка имеет смысл только после перехода к \(2\)-адической норме и доказательства, что valuation членов стремится к бесконечности.

Выбрать неправильный квадратный корень

Из \(T^2=1/9\) ещё не следует, какая из двух \(2\)-адических ветвей нужна. Знак выбирается сравнением по модулю \(8\), а не вещественной положительностью.

Остановить хвост фиксированным числом членов без проверки

То, что двадцати или тридцати членов хватает на тестах, — полезное наблюдение, но не доказательство. Условие (17) превращает эвристику в сертификат.

Считать, что минимум valuation суммы всегда равен минимуму valuation членов

Это верно лишь при уникальном минимуме. Два нечётных числа на одном уровне обязательно уничтожают младший бит.

Делить на чётное число по модулю \(2^r\)

Чётный знаменатель необратим. Сначала надо вынести его степень двойки, а обращать только нечётную часть.

Довериться почти совпавшему ответу

Popcount-приближение для итоговой суммы ошибается всего на единицу. Это особенно коварный вид ошибки: численный результат выглядит слишком хорошим, чтобы быть случайным, но всё равно остаётся неверным.

16. Проверки, которые замыкают решение

Надёжная реализация должна пройти несколько независимых уровней контроля.

1. Для малых \(n\) вычислить \(S(n)\) буквально и сравнить с хвостовой формулой. Проверка первых ста значений уже хорошо ловит ошибки индекса и знака.
2. Воспроизвести \(u(4)=7\) и \(u(20)=24\).
3. Воспроизвести \(U(5)=241\).
4. Для каждого куба останавливаться только после выполнения (17), а не после заранее выбранного количества итераций.
5. Отдельно проверить случаи с двумя минимумами, например \(n=21^3\).
6. Сравнить итог с конечным тождеством (1) на диапазоне, где \(a_n\) ещё можно вычислить напрямую.

При таком наборе проверок формула (18) уже не является догадкой. Каждый её член либо замкнут, либо вычисляется короткой сертифицированной процедурой. Финальное сложение намеренно оставлено без публикации численного ответа: математически существенная часть задачи заканчивается не последней арифметической операцией, а доказательством того, почему для каждого \(m^3\) достаточно нескольких десятков \(2\)-адических шагов вместо \(m^3\) исходных слагаемых.

17. Короткое резюме всей истории

Исходная сумма выглядит огромной, потому что мы сначала смотрим на неё вещественными глазами. В \(2\)-адическом мире множители \(2^k\) делают поздние члены всё меньше, и производящая функция сходится к \(-1/3\). Специальная комбинация \(3S(n)+4\) вычитает этот предел, оставляя хвост.

Дальше теорема Куммера сообщает высоту каждого хвостового члена:

\[ \nu_2\left((-2)^k\binom{2k}{k}\right)=k+s_2(k). \]

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

\[ \frac{t_{k+1}}{t_k}=-4\frac{2k+1}{k+1}. \]

Наконец, ультраметрическое неравенство даёт строгий критерий остановки. Так задача с индексами до \(10^{12}\) сводится примерно к нескольким сотням тысяч операций над небольшими \(2\)-адическими числами.

Это и есть главный урок Too Many Twos: когда требуется только число двоек, нельзя позволять огромным целым числам диктовать способ вычисления. Нужно сразу перейти в пространство, где двойки являются не помехой, а системой координат.