Главная страница » Что такое цифровой корень

Что такое цифровой корень

  • автор:

Цифровой корень — 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, справедливы следующие две формулы:

    Эти две формулы можно собрать объединить формулой:

    Из этой формулы, например, следует периодичность цифрового корня.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *