Цифровой корень — Digital root
цифровой корень (также повторяющаяся цифровая сумма ) натурального число в заданном числовом основании — это (однозначное) значение, полученное с помощью итеративного процесса суммирования цифр, на каждой итерации с использованием результата предыдущей итерации для вычисления цифра сумма. Процесс продолжается до тех пор, пока не будет достигнуто однозначное число.
Содержание
- 1 Формальное определение
- 1.1 Пример
- 2.1 Формула сравнения
- 2.2 Использование минимальной функции
- 2.3 Свойства
Формальное определение
Пусть n <\ displaystyle n>— натуральное число. Для базового b>1 <\ displaystyle b>1> , мы определяем сумму цифр F b: N → N <\ displaystyle F_ : \ mathbb
\ rightarrow \ mathbb > должно быть следующим: где k = ⌊ log b n ⌋ + 1 <\ displaystyle k = \ lfloor \ log _
\ rfloor + 1> — количество цифр в числе в базе b <\ displaystyle b>, а — значение каждой цифры числа. Натуральное число n <\ displaystyle n>— это цифровой корень, если это фиксированная точка для F b <\ displaystyle F_ > , которое происходит, если F b (n) = n <\ displaystyle F_ (n) = n> .
Все натуральное числа n <\ displaystyle n>— препериодические точки для F b <\ displaystyle F_ > , независимо от основания. Это потому, что если n ≥ b <\ displaystyle n \ geq b>, то
F b (n) = ∑ i = 0 k — 1 di
, потому что b>1 <\ displaystyle b>1> . Если n , то тривиально
Следовательно, единственными возможными цифровыми корнями являются естественные числа 0 ≤ n , и нет никаких циклов, кроме фиксированных точек 0 ≤ n .
Пример
В базе 12 8 является мультипликативный цифровой корень по основанию 10 числа 3110, как для n = 3110
d 0 = 3110 mod 12 0 + 1 — 3110 mod 1 2 0 12 0 = 3110 mod 12 — 3110 mod 1 1 = 2 — 0 1 = 2 1 = 2 <\ displaystyle d_ <0>= <\ frac <3110 <\ bmod <12 ^ <0 + 1>>> — 3110 < \ bmod <1>> 2 ^ <0>> <12 ^ <0>>> = <\ frac <3110 <\ bmod <12>> — 3 110 <\ bmod <1>>> <1>> = <\ frac <2-0><1>> = <\ frac <2><1>> = 2> d 1 = 3110 mod 12 1 + 1 — 3110 mod 1 2 1 12 1 = 3110 mod 144 — 3110 mod 1 2 12 = 86 — 2 12 = 84 12 = 7 <\ displaystyle d_ <1>= <\ frac <3110 <\ bmod <12 ^ < 1 + 1>>> — 3110 <\ bmod <1>> 2 ^ <1>> <12 ^ <1>>> = <\ frac <3110 <\ bmod <144>> — 3110 <\ bmod <1>> 2> <12>> = <\ frac <86-2><12>> = <\ frac <84><12>> = 7> d 2 = 3110 mod 12 2 + 1 — 3110 mod 1 2 2 12 2 = 3110 мод. 1728 — 3110 мод. 1 44 144 = 1382 — 86 144 = 1296 144 = 9 <\ displaystyle d_ <2>= <\ frac <3110 <\ bmod <12 ^ <2 + 1>>> -3110 <\ bmod <1>> 2 ^ <2>> <12 ^ <2>>> = <\ frac <3110 <\ bmod <1728>> — 3110 <\ bmod <1>> 44> <144>> = <\ frac <1382-86><144>> = <\ frac <1296><144>> = 9> d 3 = 3110 mod 12 3 + 1 — 3110 mod 1 2 3 12 3 = 3110 mod 20736 — 3110 mod 1 728 1728 = 3110 — 1382 1728 = 1728 1728 = 1 <\ displaystyle d_ <3>= <\ frac <3110 <\ bmod <12 ^ <3 + 1>>> — 3110 <\ bmod < 1>> 2 ^ <3>> <12 ^ <3>>> = <\ frac <3110 <\ bmod <20736>> — 3110 <\ bmod <1>> 728> <1728>> = <\ frac < 3110-1382><1728>> = <\ frac <1728><1728>> = 1> F 12 (3110) = ∑ i = 0 4 — 1 di = 2 + 7 + 9 + 1 = 19 <\ displaystyle F_ <12>(3110) = \ sum _ ^ <4-1>d_ = 2 + 7 + 9 + 1 = 19>
Этот процесс показывает, что 3110 — 1972 в базе 12. Теперь для F 12 (3110) = 19 <\ displaystyle F_ <12>(3110) = 19>
d 0 = 19 mod 12 0 + 1-19 mod 1 2 0 12 0 = 19 mod 12 — 19 мод 1 1 = 7-0 1 = 7 1 = 7 <\ displaystyle d_ <0>= <\ frac <19 <\ bmod <12 ^ <0 + 1>>> — 19 <\ bmod <1>> 2 ^ <0>> <12 ^ <0>>> = <\ frac <19 <\ bmod <12>> — 19 <\ bmod <1>>> <1>> = <\ frac <7-0>< 1>> = <\ frac <7><1>> = 7> d 1 = 19 mod 12 1 + 1 — 19 mod 1 2 1 12 1 = 19 mod 144 — 19 mod 1 2 12 = 19 — 7 12 = 12 12 = 1 <\ displaystyle d_ <1>= <\ frac <19 <\ bmod <12 ^ <1 + 1>>> — 19 <\ bmod <1>> 2 ^ <1>> <12 ^ <1>>> = <\ frac <19 <\ bmod <144>> — 19 <\ bmod <1>> 2> <12>> = <\ frac <19-7><12>> = <\ гидроразрыва <12><12>> = 1> F 12 (19) = ∑ я = 0 2 — 1 di = 1 + 7 = 8 <\ displaystyle F_ <12>(19) = \ sum _ ^ <2-1>d_ = 1 + 7 = 8>
, показывая, что 19 равно 17 в базе 12. А поскольку 8 — это однозначное число в базе 12,
Прямые формулы
Мы можно определить корень цифры непосредственно для базы b>1 <\ displaystyle b>1> dr b: N → N <\ displaystyle \ operatorname
_ : \ mathbb \ rightarrow \ mathbb > следующими способами: Формула сравнения
Формула в базе b <\ displaystyle b>равно:
В base 10 соответствующая последовательность имеет вид (sequence A010888 в OEIS ).
Цифровой корень — это значение по модулю b — 1 <\ displaystyle b-1>, потому что b ≡ 1 mod b — 1, <\ displaystyle b \ Equiv 1 <\ bmod
>,> и, следовательно, bk ≡ 1 k ≡ 1 mod b — 1, <\ displaystyle b ^ \ Equiv 1 ^ \ Equiv 1 <\ bmod >,> поэтому независимо от позиции значение n mod b — 1 <\ displaystyle n <\ bmod > — 1> то же самое — ab 2 ≡ ab ≡ a mod b — 1 <\ displaystyle ab ^ <2>\ Equiv ab \ Equiv a <\ bmod >> — поэтому цифры могут быть добавлены осмысленно. В частности, для трехзначного числа n = a 1 b 2 + a 2 b 1 + a 3 b 0 <\ displaystyle n = a_ <1>b ^ <2>+ a_ <2>b ^ <1 >+ a_ <3>b ^ <0>> dr b (n) ≡ a 1 b 2 + a 2 b 1 + a 3 b 0 ≡ a 1 (1) + a 2 (1) + a 3 (1) ≡ (a 1 + a 2 + a 3) mod b — 1 <\ displaystyle \ operatorname
_ (n) \ Equiv a_ <1>b ^ <2>+ a_ <2>b ^ <1>+ a_ <3>b ^ <0>\ Equiv a_ <1>(1) + a_ <2>(1) + a_ <3>(1) \ Equiv (a_ <1>+ a_ < 2>+ a_ <3>) <\ bmod >> . Чтобы получить модульное значение по отношению к другим числам n <\ displaystyle n>, можно взять взвешенные суммы, где вес на k <\ displaystyle k>-й цифре соответствует значению bk <\ displaystyle b ^
> по модулю n <\ displaystyle n>. В с основанием 10 это проще всего для 2, 5 и 10, где старшие цифры исчезают (поскольку 2 и 5 делят 10), что соответствует известному факту, что делимость десятичного числа по отношению к 2, 5 и 10 можно проверить по последней цифре (четные числа заканчиваются на 0, 2, 4, 6 или 8). Также следует отметить модуль n = b + 1 <\ displaystyle n = b + 1>: поскольку b ≡ — 1 mod b + 1, < \ displaystyle b \ Equiv -1 <\ bmod >,> и, следовательно, b 2 ≡ (- 1) 2 ≡ 1 (mod b + 1), <\ displaystyle b ^ <2>\ Equiv (-1) ^ <2>\ Equiv 1 <\ pmod >,> взятие переменной суммы цифр дает значение по модулю b + 1 <\ displaystyle b + 1>.
Использование минимальной функции
Это помогает увидеть цифровой корень положительного целого числа как позицию, которую он занимает по отношению к наибольшему кратному b — 1 < \ displaystyle b-1>меньше, чем само число. Например, в с основанием 6 цифровой корень 11 равен 2, что означает, что 11 является вторым числом после 6 — 1 = 5 <\ displaystyle 6-1 = 5>. Аналогично, цифровой корень 2035 по основанию 10 равен 1, что означает, что 2035 — 1 = 2034 | 9 <\ displaystyle 2035-1 = 2034 | 9>. Если число дает цифровой корень точно из b — 1 <\ displaystyle b-1>, то это число кратно b — 1 <\ displaystyle b-1>.
Имея это в виду, цифровой корень положительного целого числа n <\ displaystyle n>может быть определен с помощью функции пола ⌊ x ⌋ <\ displaystyle \ lfloor x \ rfloor>, поскольку
dr b (n) = n — (b — 1) ⌊ n — 1 b — 1 ⌋. <\ displaystyle \ operatorname
_ (n) = n- (b-1) \ left \ lfloor <\ frac > \ right \ rfloor.> Свойства
- Цифровой корень a 1 + a 2 <\ displaystyle a_ <1>+ a_ <2>> в базе b <\ displaystyle b>— это цифровой корень суммы цифрового корня из a 1 <\ displaystyle a_ <1>> и цифрового корня из a 2 <\ displaystyle a_ <2>> . Это свойство можно использовать как своего рода контрольную сумму, чтобы проверить правильность вычисления суммы.
- Цифровой корень a 1 — a 2 <\ displaystyle a_ <1>-a_ <2>> в базе b <\ displaystyle b>совпадает с разницей цифрового корня a 1 <\ displaystyle a_ <1>> и цифровой корень из a 2 <\ displaystyle a_ <2>> по модулю b — 1 <\ displaystyle b-1>.
- Цифровой корень — n <\ displaystyle -n>в базе b < \ displaystyle b>следующим образом:
- Цифровой корень произведение ненулевых однозначных чисел a 1 ⋅ a 2 <\ displaystyle a_ <1>\ cdot a_ <2>> в базе b <\ displaystyle b>задается Ведическим квадратом в основании b <\ displaystyle b>.
- Цифровой корень a 1 ⋅ a 2 <\ displaystyle a_ <1>\ cdot a_ < 2>> в базе b <\ displaystyle b>— цифровой корень продукта цифрового корня a 1 <\ displaystyle a_ <1>> и цифровой корень из a 2 <\ displaystyle a_ <2>> .
Аддитивная стойкость
аддитивная стойкость подсчитывает, сколько раз мы должны суммируйте цифры, чтобы получить цифровой корень.
Например, аддитивная стойкость 2718 в base 10 равна 2: сначала мы находим, что 2 + 7 + 1 + 8 = 18, а затем 1 + 8 = 9.
Не существует ограничений на аддитивную стойкость числа в базе счисления b <\ displaystyle b>. (Доказательство: для данного числа n <\ displaystyle n>, постоянство числа, состоящего из n <\ displaystyle n>повторений цифры 1 на 1 больше, чем у n <\ displaystyle n>). Наименьшие числа аддитивной стойкости 0, 1. в базе 10:
0, 10, 19, 199, 19999999999999999999999. (последовательность A006050 в OEIS )
Следующее число в последовательности (наименьшее число аддитивной стойкости 5) равно 2 × 10 — 1 (то есть 1, за которой следует 2222222222222222222222 9). Для любого фиксированного основания сумма цифр числа пропорциональна его логарифм ; следовательно, аддитивная стойкость пропорциональна повторному логарифму.
Пример программирования
В приведенном ниже примере реализуется сумма цифр, описанная в определении выше, для поиска цифровых корни и аддитивные постоянства в Python.
В популярной культуре
Цифровые корни используются в западной нумерологии, но некоторые числа считаются имеющими оккультное значение (например, 11 и 22) не всегда полностью сводятся к одной цифре.
Цифровые корни образуют важную механику в визуальной приключенческой игре Девять часов, девять человек, девять дверей.
Эксперименты с цифровым корнем
Немногие, увлекающиеся теорией чисел, знают про существование такой банальной и многим кажущейся неинтересной процедуры, такой как извлечение цифрового корня из некоторого целого числа.
Что такое цифровой корень ?
Цифровой корень — это небольшая процедура суммирования цифр, составляющих некоторое число, и которая дает некоторую цифру. Однако, не всегда при простом суммировании входящих в число цифр дает однозначное число (т.е некоторую цифру), иногда получается так, что сумма цифр либо двузначное число, либо трехзначное. Но в этом случае, процедура вычисления цифрового корня не останавливается и продолжается, но теперь уже при приложении к двухзначной или трехзначной сумме — и применение процедуры будет продолжено до тех пор, пока на выходе цифрового корня не получится однозначное целое число.
Таким образом, можно заключить, что функция вполне тривиальна и реализуется через рекурсию, однако не все было так просто и с первого раза реализовать вычисление этой функции получилось только для для двухзначных чисел… Несмотря на это устойчивую функцию цифрового корня все-таки удалось реализовать:
Для того, чтобы испытать эту функцию, необходимо ей на выход подать любое целое неотрицательное число: например, для числа 1234 функция ciphroot выдаст 1, а для числа 990 функция выдаст 9.
Эта функция очень интересна тем, что может порождать некоторые простые, но все-таки очень интересные графические эффекты: с ее помощью можно получать простенькие узоры из цветных квадратиков, демонстрирующих любопытную закономерность.
Для того, чтобы увидеть наглядно, как ведет себя цифровой корень на инкрементально возрастающей последовательности неотрицательных целых чисел, можно воспользоваться следующим кодом:
где x,y — это размеры окна с графикой, а w,h — длина и ширина «квадратиков» (строго говоря, прямоугольников).
Этот код работает крайне просто: вначале определяется переменная-накопитель num, которая будет отражать номер квадратика в некоторой матрице квадратиков, а также определяется таблица цветов, которыми будут раскрашены квадратики в матрице (очевидно, что цифровой корень принимает значения от 0 до 9, и поэтому потребуется 10 цветов для раскраски), затем в цикле происходит отрисовка самих квадратиков с выбором их цвета (индексация списков в Icon начинается с 1, поэтому потребуется номер цвета на 1 больше, чем значение, выдаваемое функцией цифрового корня).
Экспериментируя с размерами квадратиков можно получать самые разнообразные покрытия узорами, например:
выдаст вот такую картинку:
Помимо эффектов с квадратиками, функция цифрового корня в сочетании с периодическими функциями может давать крайне забавный эффект, который я назвал «множественные гармоники».
Итак, код эффекта:
И как результат, получаем вот такую забавную картинку:
Немного пояснений о том, как оно работает.
По сути дела, здесь не происходит ничего необычного — эта процедура практически калька с процедуры отрисовки графиков, описанной в ранних статьях этого блога, однако тут есть некоторые нюансы: исходная периодическая функция (в данном случае, синус) умножается в этом примере на цифровой корень от ее аргумента.
Однако, цифровой корень работает только для целых неотрицательных чисел, а в данном отрывке кода он применяется ко всем без исключения числам, в том числе и к отрицательным и к дробным.
Для того, чтобы подобное стало возможным, пришлось ввести несколько предположений, которые были совмещены в небольшой формуле перед описанием функции для построения: первое предположение состоит в том, что при умножении дробном числа с переводом в целое, его цифровой корень не изменяется (и это действительно так !); второе предположение заключается в том, что цифровой корень для отрицательных чисел — неотрицателен.
Исходя из вышеописанного, в принципе можно получить процедуру для получения «спектрального» отображения периодических функций, однако, я этого не сделал 🙂
Напоследок, скриншоты еще парочки функций:
И в заключение: этот эффект с множеством гармоник был получен в ходе случайных экспериментов, но несмотря на это, получилось весьма прикольно.
Кроме того, я придумал процедуру, которая рисует схожим образом целую радугу из одной периодической функции !
Цифровой корень натурального числа получается следующим образом
Если мы сложим все цифры какого-либо числа, затем все цифры найденной суммы и будем повторять много раз, мы, наконец, получим однозначное число (цифру), называемое цифровым корнем данного числа. Например, цифровой корень числа 34697 равен 2 (3+4+6+9+7=29; 2+9=11; 1 + 1=2). Составим программу для нахождения цифрового корня натурального числа.
program prim5;
uses crt;
var n, k, s: longint;
begin
clrscr;
writeln(‘ число=’); readln(n);
s:=n;
<Пока сумма является двузначным числом.>
while s>9 do
begin
k:=s;s:=0;
<Вычисляем сумму цифр числа.>
repeat
S:=s+k mod 10; k:=k div 10;
until k=0;
end;
writeln(‘ цифр. корень числа ‘,n, ‘ равен ‘,s);
readln;
end.Раскрытие тайны цифрового корня.
Недавно мне посчастливилось подготовить задачу про цифровой корень на Russian Code Cup. В результате прорешивания, а также комментариев к разбору, я заметил, что, к сожалению, отнюдь не каждый осведомлен о свойствах данной функции. Я просто не мог остаться равнодушным к этой проблеме.
Для начала рассмотрим определение цифрового корня, взятое с англоязычной Википедии с моим переводом:
Цифровой корень натурального числа — это цифра, полученная в результате итеративного процесса суммирования цифр, на каждой итерации которого для подсчета суммы цифр берут результат, полученный на предыдущей итерации. Этот процесс повторяется до тех пор, пока не будет получена одна цифра.
Например цифровой корень 65,536 это 7, потому что 6 + 5 + 5 + 3 + 6 = 25 и 2 + 5 = 7.Для начала заметим очевидное свойство ( dr(n) — цифровой корень числа n ):
Дальше докажем следующий факт: Сумма цифр числа n имеет такой же остаток при делении на 9, как и число n .
В доказательстве нам понадобится формула
, докажем ее по индукции:
База:
Переход:.
Нужно доказать. Просто распишем
Таким образом мы доказали по индукции, что.
Вернемся к основному доказательству. Пусть
, тогда: n = a k·10 k + a k — 1·10 k — 1 + . a 1·10 + a 0 . По только что доказанной формуле:
следовательно
. Что и требовалось доказать.
Теперь по только что доказанному утверждению понятно, что остаток при делении на 9 — инвариант относительно взятия цифрового корня, а поскольку сумма цифр числа меньше самого числа, если число больше 9, справедливы следующие две формулы:
Эти две формулы можно собрать объединить формулой:
Из этой формулы, например, следует периодичность цифрового корня.
Любая задача про цифровой корень становится легче при знании этого несложного факта, надеюсь, что кому-нибудь этот пост покажется полезным.
Поддержано грантом для одаренной молодежи А. А. Шалыто.
Математические головоломки Топологические С отвлеченными числами Числовые Геометрические Еще головоломки Математический портал О портале "Математика. ру" mainmenu Математика в афоризмах Сущность математики Значение математики Изучение математики О красоте математики Элементарная математика Высшая математика Математические фокусы С картами С мелкими предметами Со снаряжением Исчезновение фигур Без обмана Занимательная арифметика Немного истории О цифрах и нумерации Потомок древнего абака Недесятичные системы Числовые диковинки Вечный календарь Числовые великаны Числовые лилипуты Путешествие Решение математических задач По высшей математике №1-100 По высшей математике №101-200 По высшей математике №201-300 По высшей математике №301-400 По высшей математике №401-500 Задачи-головоломки Р. Курант, Г. Роббинс
Дедукция, выраженная в адекватной математической форме, — необходимое основание индукции, которая дает нам новые обобщения и, следовательно, новые факты [314, с. 462].
Цифровые корни
Цифровые корни
Если сложить все цифры некоторого числа, затем все цифры только что найденной суммы и так продолжать достаточно далеко, то получится одна единственная цифра, которая носит название цифрового корня первоначального числа. Быстрее всего можно получить цифровой корень при помощи так называемого «процесса отбрасывания девяток». Допустим, например, что мы хотим найти цифровой корень числа 87345691. Сначала сложим цифры 8 и 7, будет 15; затем тут же складываем 5 и 1, получаем 6. Этот же результат получится, если вычесть или «исключить» из 15 девятку. Теперь прибавим 6 к следующей цифре, т. е. к тройке, получится 9. Девять плюс 4 дает 13 — число, которое после исключения девятки опять сводится к числу 4. Так же мы поступаем, пока не дойдем до последней цифры. Цифра 7, полученная этим путем, будет цифровым корнем заданного числа 87345691.
Большое количество фокусов с числами основано на операции, которая приводит к числу, кажущемуся случайным, хотя в действительности имеющим своим цифровым корнем девятку. Если производилась именно такая операция, можно предложить зрителю обвести кружком любую цифру ответа (за исключением нуля), а остальные цифры назвать в любом порядке. После этого показывающий может объявить отмеченную цифру. Для этого ему нужно просто складывать называемые зрителем цифры, вычитая по ходу дела девятки; таким образом, при объявлении последней цифры он уже будет знать цифровой корень совокупности записанных им чисел. Если этим корнем окажется девятка, то была отмечена кружком эта же цифра. В остальных случаях, чтобы получить отмеченную цифру, нужно вычесть найденный цифровой корень из девятки. Вот некоторые из многих операций, которые приводят к числам, цифровой корень которых равен 9.
1. Напишите число (оно может быть сколь угодно большим) и переставьте его цифры в любом порядке; вычтите меньшее из этих чисел из большего.
2. Напишите какое-нибудь число, сложите все его цифры и вычтите полученную сумму из первоначального числа.
3. Напишите какое-нибудь число. Найдите сумму его цифр, умножьте ее на 9 и сложите результат с первоначальным числом. Напишите какое-нибудь число, умножьте его на 9 или на число, кратное девяти. (Все числа, кратные девяти, имеют своим цифровым корнем девятку, и обратно, все числа, имеющие своим цифровым корнем девятку, кратны девяти.)
4. Напишите какое-нибудь число, сложите два числа, полученных из него путем любой перестановки цифр, и возведите полученный результат в квадрат.
Если вы хотите еще более затемнить метод получения чисел, цифровой корень которых равен 9, вы можете перед существенным в этом методе действием вводить произвольные числа и операции. Например, можно предложить зрителю записать количество мелочи в его кармане, умножить это число на число людей в комнате, прибавить к результату самый знаменательный год в его жизни и т. д. и, наконец, умножить результат на 9. Ясно, что только последнее действие имеет отношение к делу. Как только получено число, цифровой корень которого равен 9, вы можете предложить зрителю обвести какую-нибудь цифру результата кружком и показывать фокус, как это было описано выше.
Что такое цифровой корень
AaronHe → Google Code Jam and Kick Start 2023 Is Cancelled
shubhamgrg1000 → Invitation to CodeChef Starters 82 (Rated till 6-stars) — 22nd March
code2000hackersupreme → My first blog post
mazihang2022 → Codeforces Round #858 (Div. 2) Editorial
todorokishotoua1 → Help Needed in a Problem
ashwanth106121023 → Invitation to Code Venture
ZZ_ZZ → why i can't do this ??
E869120 → JOI Spring Camp 2023 Online Contest
DNA. → USACO 2023 February Contest, Gold: Problem 2. Fertilizing Pastures
serialcomder → An interesting problem
AAK → Indian ICPC 2022-23 Regionals — Discussion
18o3 → Indian ICPC 2022-23 Regionals — Qualifier Rounds
awoo → Разбор Educational Codeforces Round 142
DanielB999 → 2022-2023 ICPC Latin American Regional Programming Contest
lis05 → codeforces.com not working
FelixArg → Зеркало личной олимпиады по программированию VrnCTF-2023
nHimanshu → Hard work in cp
xiaowuc1 → USACO 2022-2023 First Contest
DeadlyPillow → [feature request] Blind hour in virtuals
rajb_957 → A difficult / interesting problem
Amartya2018 → List of programming resources and Tough problems I solve
SirRembocodina → Codeforces Round 859 (Div. 4) problem F – extended constraints solution (Diophantine Equations)
PARTHO_DAS → Compiler Error in (C++17, C++20)
mesanu → Codeforces Round #859 (Div. 4) Editorial
ajay_mnc → [Pattern] PermutationsБлог пользователя GShark
Раскрытие тайны цифрового корня.
Автор GShark, 8 лет назад ,
Недавно мне посчастливилось подготовить задачу про цифровой корень на Russian Code Cup. В результате прорешивания, а также комментариев к разбору, я заметил, что, к сожалению, отнюдь не каждый осведомлен о свойствах данной функции. Я просто не мог остаться равнодушным к этой проблеме.
Для начала рассмотрим определение цифрового корня, взятое с англоязычной Википедии с моим переводом:
Цифровой корень натурального числа — это цифра, полученная в результате итеративного процесса суммирования цифр, на каждой итерации которого для подсчета суммы цифр берут результат, полученный на предыдущей итерации. Этот процесс повторяется до тех пор, пока не будет получена одна цифра.
Например цифровой корень 65,536 это 7, потому что 6 + 5 + 5 + 3 + 6 = 25 и 2 + 5 = 7.Для начала заметим очевидное свойство ( dr(n) — цифровой корень числа n ):
dr(n) = n, n ≤ 9
Дальше докажем следующий факт: Сумма цифр числа n имеет такой же остаток при делении на 9, как и число n .
В доказательстве нам понадобится формула
, докажем ее по индукции:
База:
Переход:.
Нужно доказать. Просто распишем
Таким образом мы доказали по индукции, что.
Вернемся к основному доказательству. Пусть
, тогда: n = ak·10 k + ak — 1·10 k — 1 + . a1·10 + a0 . По только что доказанной формуле:
следовательно
. Что и требовалось доказать.
Теперь по только что доказанному утверждению понятно, что остаток при делении на 9 — инвариант относительно взятия цифрового корня, а поскольку сумма цифр числа меньше самого числа, если число больше 9, справедливы следующие две формулы:
Эти две формулы можно собрать объединить формулой:
Из этой формулы, например, следует периодичность цифрового корня.
Любая задача про цифровой корень становится легче при знании этого несложного факта, надеюсь, что кому-нибудь этот пост покажется полезным.