Что происходит в задачке?

[orloff]

Всем привет.
На Codewars есть задачка
Given n, take the sum of the digits of n. If that value has more than one digit, continue reducing in this way until a single-digit number is produced. The input will be a non-negative integer.

Пример
16 --> 1 + 6 = 7
942 --> 9 + 4 + 2 = 15 --> 1 + 5 = 6

Я ее честно решил с рекурсией, но потом поискал другие решения и нашел код в одну строку

export const digitalRoot = (n:number): number => {
 // your code here
    return (n - 1) % 9 + 1;
};

Расскажите плиз неучу, что происходит? Мы отнимаем 1 от нашего числа, получаем остаток от деления на 9, и плюсуем единицу. И это подходит к любому числу. Что это вообще за трюк?

[Aetae]

Ну вот такая вот закономерность. Ответы искать в институтской программе теории числел. Не думаю что тут найдётся спец по вопросу.)

[orloff]

Aetae,
Спасибо за ответ. Думал может кто помнит/знает. Уж очень джедайское решение получилось)) Хотя это не решение задачи, а скорее задача под эту закономерность заточена )

[Aetae]

Так тоже верно, кстати:

const digitalRoot = (n, base = 10) => {
    return (n - 1) % (base - 1) + 1;
};

[MallSerg]

Это вроде "Арифметика остатков" из теории чисел

[Alexandroppolus]

Что это вообще за трюк?

навскидку, немного коряво, но тем не менее.

1) Число делится на 9, если сумма его цифр делится на 9 (признак делимости, можно глянуть в википедии). Т.е. если у нас исходное число М = 9*N, то очевидно, digitalRoot придет к 9.

2) Теперь кейс, когда наше число не делится на 9, то есть равно М = 9*N + k, где k=1..8, или, по другому, M % 9 = k
Здесь можно легко доказать, что сумма цифр будет сохранять остаток от деления на 9, при выполнении digitalRoot, на каждой итерации.

Пусть последняя цифра числа 9*N оказалась равна m. Добавим k. Если m + k < 10, то просто последняя цифра увеличилась на k. Иначе, последняя цифра стала равна m + k - 10, стоящие перед ней n девяток обнулились, а недевятка перед ними увеличилась на 1. Сумма цифр поменялась на (m + k - 10) - m - n*9 + 1 = k - 9*p. То есть в любом случае остаток суммы цифр от деления на 9 стал равен k. Что, собственно, и доказывали.

Вот так и вышло, что сохраняя оный остаток, digitalRoot приходит либо к 9 в случае нулевого остатка, либо. самому остатку.

[Alexandroppolus]

Сейчас подумал, что п.1 не более чем частный случай п.2, только для нулевого остатка. В общем, всё доказательство в п.2

[MallSerg]

Такие вещи проще всего объяснять графически.

Взять базу 9 и отобразить ее в виде типа циферблата часов с делениями от нуля до девяти.
Числовую прямую намотать на такой циферблат в виде спирали согласно делениям.
Тогда станет хорошо заметно что к примеру число 10 будет на линии первого деления циферблата а число 20 на втором делении циферблата а к примеру число 14 будет на пятом делении потому что 10 начинается на первом делении и плюс еще четыре деления, число 24 будет на 6м делении циферблата и.т.д. Это пример с десятками, с сотнями тысячами и так далее работает абсолютно аналогично.

Если разобрать по шагам то станет понятно почему это работает для любого числа
и почему в условиях задачи число не должно превышать базу.

[рони]

MallSerg,