Оценить скорость возрастания последовательности

[Ktina]

Сумма цифр факториала числа $n>1$ в позиционной системе счисления с основанием $n$ для первых 15 значений $n$ (с 2 по 16) выглядит так:

1 2 3 8 5 12 14 16 27 30 11 48 26 42 45

Эти значения получены с помощью маленькой процедурки, нацарапанной на JavaScript:

Используется синтаксис Javascript

function sumDig (n, base) {
let sum = 0;
     while (n) { 
         sum += n % base;
         n = (n - n % base) / base;
      }
return sum; 
}

function factorial(int) {
        if (!int) return 1;
    return factorial(int-1)*int;
}

for (i = 2; i <= 16; i++) {
   console.log(sumDig (factorial(i), i)); 
}
 

Ясно, что последовательность возрастает как минимум линейно, поскольку для каждого $n>1$ сумма обязана быть кратной $n-1$.
Однако в большинстве случаев эта сумма не равна $n-1$, а в несколько раз её превосходит.
Так как же тем не менее оценить скорость возрастания этой последовательности?

GAA:

Предупреждение за искажение названия языка. Отредактировано.

[Peace]

Насколько я понял, четвёртый член Вашей последовательности 8, возникает так: 5!=120 и это вроде равно 240 в пятеричной системе. А сумма цифр 240 равна 6, а не 8. Или я где-то ошибся, или чего-то не понял.

[Yadryara]

Peace в сообщении #1327759 писал(а):

Насколько я понял, четвёртый член Вашей последовательности 8, возникает так: 5!=120 и это вроде равно 240 в пятеричной системе.

Неа. $120_{10} = 440_5$

[Peace]

Yadryara в сообщении #1327775 писал(а):

Неа. $120_{10} = 440_5$

Точно. Спасибо.

[Peace]

Вот прикол: четвёртый член последовательности 8 возникает как сумма цифр пятеричного числа 440 в десятичной системе, но если складывать эти цифры в пятеричной системе, пока не найдём нумерологическую сумму то получим $13\rightarrow1+3=4$. Для $7!$ эта сумма в семиричной системе равна 6, а для $8!$ сумма в восьмеричной системе равна 7-ми. Т.е. исходная последовательность превращается в $1,2,3,4,5,6,7,8,?$. Или я снова ошибаюсь?

[grizzly]

Peace в сообщении #1327807 писал(а):

Вот прикол

Ага:

Ktina в сообщении #1327750 писал(а):

для каждого $n>1$ сумма обязана быть кратной $n-1$.

[Ktina]

Peace

grizzly в сообщении #1327808 писал(а):

Ktina в сообщении #1327750 писал(а):

для каждого $n>1$ сумма обязана быть кратной $n-1$.

Кстати, это обобщение того факта, что в десятичной системе сумма цифр делится на 9, т.т.т. число делится на 9.

[Peace]

grizzly, Ktina,
А почему эта сумма равна $n-1$ при нумерологическом суммировании в n- ричной системе счисления? Как это объяснить? Или это просто совпадение для первых 8-ми членов?

[wrest]

Ktina в сообщении #1327750 писал(а):

Так как же тем не менее оценить скорость возрастания этой последовательности?

Если конкретно этой (то есть конечной последовательности из 15 членов), то применить линейную аппроксимацию методом наименьших квадратов, то есть найти $k$ и $b$ в $y=kx+b$ такие что сумма квадратов отклонений будет минимальна.
Получится что-то вроде $k=3,1786$ - это и есть скорость возрастания

[Someone]

Peace в сообщении #1327811 писал(а):

А почему эта сумма равна $n-1$ при нумерологическом суммировании в n- ричной системе счисления?

В популярной математической литературе для школьников младших классов это называется не "нумерологической суммой", а "цифровым корнем". Чтобы понять, почему так получается, достаточно вспомнить признак делимости числа на $n-1$ в $n$-ичной системе счисления (для младших школьников — признак делимости на $9$ в десятичной системе счисления), о чём Вам уже было сказано. Этот цифровой корень в $n$-ичной системе счисления всегда равен остатку от деления числа на $n-1$. Но нумерологи, видимо, в школьной арифметике не сильны.

[Peace]

Someone
Вы правы. Спасибо.

-- 20.07.2018, 12:22 --

Someone в сообщении #1327814 писал(а):

Этот цифровой корень в $n$-ичной системе счисления всегда равен остатку от деления числа на $n-1$

Извините, но мне непонятно, как при делении некоторого числа на n-1, в n-ричной системе, остаток от деления может быть равен n-1?

[slavav]

До 5000 поведение квадратичное. Голосую за $\Theta(N^2)$. Оценка сверху тривиальна. Не знаю как доказать оценку снизу.

[wrest]

Peace в сообщении #1327815 писал(а):

Извините, но мне непонятно, как при делении некоторого числа на n-1, в n-ричной системе, остаток от деления может быть равен n-1?

Числа не зависят от того, в какой системе счисления они записаны, как и остатки от деления одних чисел на другие числа...

[Peace]

wrest в сообщении #1327828 писал(а):

Числа не зависят от того, в какой системе счисления они записаны, как и остатки от деления одних чисел на другие числа...

Да, это понятно, меняется лишь форма их записи. Вопрос был в другом: Например для числа $440_5$ цифровой корень в пятеричной системе равен 5-1= 4, и равен остатку от деления 440 на 4 в пятеричной системе. Такой вывод (скорее всего неверный) я сделал из утверждения уважаемого Someone, на основе его утверждения:

Someone в сообщении #1327814 писал(а):

Этот цифровой корень в $n$-ичной системе счисления всегда равен остатку от деления числа на $n-1$.

До меня не доходит, как это возможно.

[Someone]

Peace в сообщении #1327815 писал(а):

Извините, но мне непонятно, как при делении некоторого числа на n-1, в n-ричной системе, остаток от деления может быть равен n-1?

Виноват, неточно сформулировал. Остаток равен цифровому корню всегда, кроме случая делимости на $n-1$, когда остаток равен $0$. Поскольку сумма цифр ненулевого числа не может быть равна $0$, то в этом случае цифровой корень равен $n-1$ (разность числа и его цифрового корня всегда делится на $n-1$).