Сумма цифр

Основное арифметическое свойство суммы цифр следует из сравнения ${\displaystyle b\equiv 1{\pmod {b-1}}}$: при делении на ${\displaystyle b-1}$ число сравнимо со своей суммой цифр:

${\displaystyle s_{b}(n)\equiv n{\pmod {b-1}}.}$

В частности, десятичная сумма цифр даёт остаток числа при делении на 9 (и на 3). Отсюда следует классический признак делимости: число делится на 9 тогда и только тогда, когда его сумма цифр делится на 9. Цифровой корень выражается формулой

${\displaystyle \operatorname {dr} _{b}(n)=1+(n-1){\bmod {(}}b-1)\qquad (n>0),}$

которая позволяет вычислять его без итераций.

Сумма цифр изменяется при арифметических операциях в точности на величину, определяемую переносами. При сложении

${\displaystyle s_{b}(a+b)=s_{b}(a)+s_{b}(b)-(b-1)\,c,}$

где ${\displaystyle c}$ — суммарное число переносов разрядов. При прибавлении единицы

${\displaystyle s_{b}(n+1)=s_{b}(n)+1-(b-1)\,\nu ,}$

где ${\displaystyle \nu }$ — количество последних цифр ${\displaystyle b-1}$ в записи ${\displaystyle n}$. Поэтому при переходе от 199 к 200 десятичная сумма цифр падает с 19 до 2, а график ${\displaystyle s(n)}$ имеет характерный «пилообразный» вид.

Это свойство лежит в основе теоремы Куммера (1852): показатель степени, с которой простое число ${\displaystyle p}$ входит в разложение биномиального коэффициента ${\displaystyle {\binom {a+b}{a}}}$, в точности равен числу переносов при сложении ${\displaystyle a}$ и ${\displaystyle b}$ в ${\displaystyle p}$-ичной системе счисления^[11][12].

Одно из важнейших применений суммы цифр в теории чисел — формула Лежандра для факториала. Показатель степени ${\displaystyle p}$ (где ${\displaystyle p}$ — простое), делящей ${\displaystyle n!}$, выражается через сумму цифр числа ${\displaystyle n}$ в ${\displaystyle p}$-ичной системе счисления:

${\displaystyle v_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.}$

Эта формула позволяет мгновенно определять, сколько нулей в конце записи числа ${\displaystyle n!}$ (для этого достаточно вычислить ${\displaystyle v_{5}(n!)}$)^[13].

Для всех ${\displaystyle n\geq 1}$

${\displaystyle 1\leq s_{b}(n)\leq (b-1){\bigl (}1+\lfloor \log _{b}n\rfloor {\bigr )},}$

то есть сумма цифр ${\displaystyle k}$-значного десятичного числа не превосходит ${\displaystyle 9k}$. Сумма цифр принимает значение 1 ровно на степенях основания, а максимальное значение на отрезке от 0 до ${\displaystyle b^{k}-1}$ равно ${\displaystyle (b-1)k}$ и достигается единственным числом, состоящим из ${\displaystyle k}$ цифр ${\displaystyle b-1}$.

Средняя сумма цифр по всем ${\displaystyle k}$-значным числам растёт линейно по числу разрядов: она равна ${\displaystyle 4{,}5\,k}$ в десятичной системе, а в системе с основанием ${\displaystyle b}$ — ${\displaystyle (b-1)k/2}$. Буш доказал, что среднее значение суммы цифр у чисел, не превосходящих ${\displaystyle N}$, асимптотически равно ${\displaystyle {\tfrac {b-1}{2}}\log _{b}N}$^[14].

Распределение сумм цифр по числам фиксированной длины близко к нормальному: сумма цифр четырёхзначного числа ведёт себя как сумма четырёх независимых случайных цифр, поэтому значения группируются около среднего ${\displaystyle 18}$ с убыванием к краям диапазона по закону, аппроксимируемому нормальным распределением^[15].

Сумма цифр демонстрирует самоподобие: знакопеременная последовательность ${\displaystyle (-1)^{s_{2}(n)}}$ совпадает с последовательностью Туэ — Морса, обладающей фрактальными свойствами. Если построить функцию, значения которой на отрезке ${\displaystyle [0,1]}$ определяются кумулятивной суммой этой последовательности, мы получим кривую Бланманже (или функцию Такаги) — классический пример функции, которая непрерывна всюду, но не дифференцируема нигде^[16].

Столарский доказал, что отношение числа единиц в двоичной записи квадрата к числу единиц в записи самого числа не ограничено сверху:

${\displaystyle \limsup _{n\to \infty }{\frac {s_{2}(n^{2})}{s_{2}(n)}}=\infty .}$

Это означает, что суммы цифр степеней могут во много раз превышать суммы цифр оснований^[17]. Для последовательности ${\displaystyle s(2^{n})}$ Дрмота и Гайдошик доказали, что значения распределены асимптотически нормально вокруг среднего ${\displaystyle 4{,}5\log _{10}2\cdot n}$ с флуктуациями порядка ${\displaystyle {\sqrt {n}}}$^[18].

Равенство ${\displaystyle s(n)\equiv n{\pmod {9}}}$ даёт признаки делимости на 3 и на 9 и лежит в основе средневекового приёма «отбрасывания девяток»: чтобы проверить умножение, вычисляют цифровые корни сомножителей и произведения и сравнивают остатки. Так, для 123 × 456 = 56 088 остатки по модулю 9 равны 6, 6 и 0, и поскольку 6 · 6 = 36 ≡ 0 (mod 9), противоречия нет. Метод обнаруживает любую ошибку, изменяющую остаток по модулю 9, однако пропускает перестановки цифр, не меняющие суммы, и не является строгим доказательством правильности^[19].

В информатике и теории кодирования сумма цифр числа в двоичной системе счисления (${\displaystyle s_{2}(n)}$) называется весом Хэмминга (или popcount). Эта величина используется:

• в криптографии вес Хэмминга используется при анализе атак по побочным каналам (power analysis), так как энергопотребление процессора часто коррелирует с количеством единичных битов при выполнении операций;
• в алгоритмах существуют высокооптимизированные методы вычисления веса Хэмминга. Например, алгоритм Брайана Кернигана использует операцию ${\displaystyle n\ {\text{AND}}\ (n-1)}$, которая обнуляет младшую единичную цифру, позволяя вычислить сумму цифр за время, пропорциональное количеству единиц, а не общей длине числа^[20].

Схемы контрольных цифр в идентификационных номерах строятся на взвешенных суммах цифр, вычисляемых по модулю 9, 10 или 11: контрольная цифра ISBN-13 получается как дополнение до кратности десяти чередующейся суммы цифр с весами 1 и 3; алгоритм Луна для номеров банковских карт использует удвоение каждой второй цифры (что эквивалентно вычитанию 9, если результат удвоения превышает 9). Выбор модуля и весов направлен на то, чтобы гарантированно обнаруживать типовые ошибки человека — одиночную ошибку в цифре и перестановку соседних цифр^[21].

Сумма цифр определяет ряд интересных числовых множеств, популярных в занимательной математике:

• числа Харшада (или числа Нивена) — числа, делящиеся на свою сумму цифр (например, 18 делится на 1+8=9);
• числа Смита — составные числа, сумма цифр которых равна сумме цифр всех их простых множителей (например, 4 937 775 = 3 × 5 × 5 × 65 837, сумма цифр числа: 4+9+3+7+7+7+5 = 42, сумма цифр множителей: 3 + 5 + 5 + (6+5+8+3+7) = 42);
• числа Дьюдени — числа, сумма цифр которых равна их кубическому корню (например, 512: 5+1+2 = 8, и ${\displaystyle 8^{3}=512}$). В десятичной системе их всего три: 1, 512 и 4913;
• числа Армстронга (нарциссические числа) — числа, равные сумме своих цифр, возведённых в степень, равную количеству цифр (например, 153 = 1³ + 5³ + 3³).