S(n)/S(n^2)

[RIP]

maxal в сообщении #61910 писал(а):

6. (Э.Туркевич) Обозначим через $s(n)$ сумму цифр числа $n$. Ограничена ли последовательность $s(n)/s(n^2)$?

Для $m\in\mathbb{N}$ рассмотрим $n=5\cdot10^{2^m-1}-\sum_{k=1}^m10^{2^m-2^k}$. Тогда:

$$n^2=24\cdot10^{2^{m+1}-2}+2\sum_{1\leqslant k<l\leqslant m}10^{2^{m+1}-2^k-2^l}+1;$$

$$S(n)=9\cdot2^m-m-4;$$

$$S(n^2)=m^2-m+7.$$

Перенесено из Задачи из Математического Просвещения N11 (2007)

[Батороев]

RIP писал(а):

maxal писал(а):

6. (Э.Туркевич) Обозначим через $s(n)$ сумму цифр числа $n$. Ограничена ли последовательность $s(n)/s(n^2)$?

Для $m\in\mathbb{N}$ рассмотрим $n=5\cdot10^{2^m-1}-\sum_{k=1}^m10^{2^m-2^k}$. Тогда:

$$n^2=24\cdot10^{2^{m+1}-2}+2\sum_{1\leqslant k<l\leqslant m}10^{2^{m+1}-2^k-2^l}+1;$$

$$S(n)=9\cdot2^m-m-4;$$

$$S(n^2)=m^2-m+7.$$

Хочу спросить: $ S(n^2) $ - это сумма цифр числа $ n^2 $?
Если - "да", то не должна ли она быть больше $ S(n) $?

[ИСН]

И близко не должна. $49^2=2401$, so what?

[Батороев]

ИСН писал(а):

И близко не должна. $49^2=2401$, so what?

Да, лень-матушка сыграла шутку - прикинул в отношении верхнего предела до числа 38 и успокоился

Видно, недалеко я потом эту "мать" отогнал, ибо отношение $ S(n)/S(n^2) $, меньшее, чем $ 1:9,1 $, найти не смог

[Edward_Tur]

Обозначим через $s(n)$ сумму цифр числа $n$. Ограничена ли последовательность $\frac{{s(n)}}{{s(n^2 )}}$?

[Imperator]

Есть предположение, что $\frac{s(n)}{s(n^2)}\leqslant 1$.

[Профессор Снэйп]

Imperator писал(а):

Есть предположение, что $\frac{s(n)}{s(n^2)}\leqslant 1$.

Неверное предположение.

$$ s(39)/s(39^2) = s(39)/s(1521) = 12/9 > 1 $$

[Imperator]

Профессор Снэйп писал(а):

Imperator писал(а):

Есть предположение, что $\frac{s(n)}{s(n^2)}\leqslant 1$.

Неверное предположение.

$$ s(39)/s(39^2) = s(39)/s(1521) = 12/9 > 1 $$

Да, точно.

[Kid Kool]

Пусть t(n) - количество цифр числа n.

Заметим, что $s(ab) = s(a)s(b) - 9k$, где k - количество переносов при сложении в столбик. Сложим теперь s(n) с самим собой s(n) раз. Т.к. всего мы делали s(n) сложений, в каждом из которых оба числа не превышали $s(n)^2$, и, следовательно, в каждом из них число переносов не превышало 2t(s(n)), то общее число переносов не превышает 2t(s(n))s(n). Отуда

$s(n^2) \geqslant s(n)^2 - 18s(n)t(s(n))$, значит, $\frac {s(n^2)} {s(n)} \geqslant s(n) - 18t(s(n)) \geqslant s(n) - 18([log_{10}s(n)] + 1) $, таким образом,

$\frac {s(n)} {s(n^2)} \leqslant \frac {1} {s(n) - 18([log_{10}s(n)] + 1)}$.

При $s(n) \geqslant 37$ знаменатель правой дроби $>= 1$, и исходное отношение ограничено единицей. А если s(n) < 37, то исходная дробь им и ограничена.

[TOTAL]

Kid Kool писал(а):

$\frac {s(n)} {s(n^2)} \leqslant \frac {1} {s(n) - 18([log_{10}s(n)] + 1)}$.

При $s(n) \geqslant 37$ знаменатель правой дроби $>= 1$, и исходное отношение ограничено единицей. А если s(n) < 37, то исходная дробь им и ограничена.

Для $n=1$ получаем $\frac {s(n)} {s(n^2)} \leqslant \frac {1} {s(n) - 18([log_{10}s(n)] + 1)} < 0$?

[worm2]

Kid Kool писал(а):

При $s(n) \geqslant 37$ знаменатель правой дроби $>= 1$, и исходное отношение ограничено единицей.

То есть Вы хотите сказать, что если $s(n) \geqslant 37$, то $s(n^2) \geqslant s(n)$?
Это неверно. Рассмотрите, например, n = 33166247903554.

Добавлено спустя 1 час 41 минуту 22 секунды:

Похоже, ответ отрицательный. Если взять, например,

$$n=\frac{(10^{m^2}-1)(10^{m-1}-1)}{10^m-1}$$

,
то, увеличивая m, кажется, можно добиться неограниченного роста отношения.
Вычислительный эксперимент показывает, что при m=50 отношение больше 11. Неохота возиться с этим и пытаться строго доказывать...

[Edward_Tur]

Положим $b_1 = 49;b_{k + 1} = b_k \cdot 10^{2^k } - 1$, т.е.
$b_k = \overline {48} {\rm{ }}\overline {98} {\rm{ }}\overline {9998} {\rm{ }}\overline {99999998} {\rm{ }} \cdots {\rm{ }}\overline {99 \cdots 98} {\rm{ }}\overline {99 \cdots 99} $,

Тогда $S(b_k^2 ) = S(b_1^2 ) + 2(k - 1) + \cdots + 2 \cdot 1 = 7 + k(k - 1) = k^2 - k + 7$.
Имеем: $\frac{{S(b_k )}}{{S(b_k^2 )}} > \frac{{2^k }}{{k^2 - k + 7}} = \to \infty $
“Наглядный” пример:
$48989998999999989999999999999999^2=$
$ = 2400020002020000020200020000000002020002000000020000000000000001$

[Kid Kool]

TOTAL писал(а):

Для $n=1$ получаем $\frac {s(n)} {s(n^2)} \leqslant \frac {1} {s(n) - 18([log_{10}s(n)] + 1)} < 0$?

Нет, переворачивать дроби в неравенстве можно лишь если их произведение положительно (поэтому здесь подразумевалось, что знаменатель уже больше 0). Не охота было разжевывать все до таких мелочей : )). А ошибку в своем рассуждении я нашел: нужно было складывать s(n) с собой не s(n), а n раз.

[juna]

Edward_Tur писал(а):

Положим $b_1 = 49;b_{k + 1} = b_k \cdot 10^{2^k } - 1$, т.е.
$b_k = \overline {48} {\rm{ }}\overline {98} {\rm{ }}\overline {9998} {\rm{ }}\overline {99999998} {\rm{ }} \cdots {\rm{ }}\overline {99 \cdots 98} {\rm{ }}\overline {99 \cdots 99} $,

Тогда $S(b_k^2 ) = S(b_1^2 ) + 2(k - 1) + \cdots + 2 \cdot 1 = 7 + k(k - 1) = k^2 - k + 7$.
Имеем: $\frac{{S(b_k )}}{{S(b_k^2 )}} > \frac{{2^k }}{{k^2 - k + 7}} = \to \infty $
“Наглядный” пример:
$48989998999999989999999999999999^2=$
$ = 2400020002020000020200020000000002020002000000020000000000000001$

С таким же успехом можно подобрать последовательность, для которой ограничена.
Например, $b_k=5^{2^k}\mod 10^{k+2}$.
Здесь $b_k^2$ содержит в конце $b_k$

[Профессор Снэйп]

Edward_Tur писал(а):

Положим $b_1 = 49;b_{k + 1} = b_k \cdot 10^{2^k } - 1$

...

Имеем: $\frac{{S(b_k )}}{{S(b_k^2 )}} > \frac{{2^k }}{{k^2 - k + 7}} = \to \infty $

Значит, если мы записываем числа в десятичной системе, то $s(n)/s(n^2)$ не ограничено.

Интересно, выполняется ли то же самое, если записывать числа в двоичной системе счисления?