S(n)/S(n^2)

[worm2]

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

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

Мне опять же кажется, можно показать, что при

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

$s_a(n)/s_a(n^2)\to\infty$ при $\m\to\infty$, где $s_a(n)$ --- это сумма цифр в записи числа n в a-ичной системе счисления. Вроде бы в этом случае $s_a(n^2)$ можно оценить как $O(m \log_a m)$, а $s_a(n)$ легко считается и равно (a-1)m(m-1), т.е. $O(m^2)$.

Добавлено спустя 11 минут 33 секунды:

Кстати, пример Edward_Tur для 16-ричной системы счисления можно записать так: $b_1 = \rm{0x6F}$, $b_{k+1} = b_k \cdot 16^{2^k}-1$. А поскольку можно показать, что $8s_{16}(n) \leqslant s_2(n) \leqslant s_{16}(n)$, то для двоичной системы ответ получается "автоматически".

[juna]

А вот еще одно решение этой задачи от RIPa

[maxal]

Докажите, что для любого натурального $n$ справедливо неравенство:

$$s_2(n^2) \leq \frac{1}{2} s_2(n)(1+s_2(n))$$

а также, что существует бесконечно много чисел $n$, обращающих его в равенство.

[ИСН]

Это двоичных цифр сумма, что ли? Дак это легко: в равенство его обращают "хорошие" числа, у которых единички друг за друга "не цепляются", т.е. каждая пара единичек в числе даёт конкретную единичку в его квадрате:

$$101^2=11001$$

$$100101^2=10101011001$$

$$10000100101^2=100010010110101011001$$

Всякое отклонение от этого правила только уменьшит число единичек.

[Kid Kool]

Доказательство неравенства - индукция по n c применением неравенства $s_2(a+b) \leq s_2(a) + s_2(b)$.

[maxal]

Edward_Tur в сообщении #97301 писал(а):

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

Неограниченность этой последовательности для двоичной системы счисления в частности была доказана в
K. B. Stolarsky (1978) The binary digits of a power, Proc. Amer. Math. Soc. 71, 1–5.
Обобщение на произвольные полиномы от $n$ и произвольные основания системы счисления дано в статье:
K.G. Hare, S. Laishram, T. Stoll (2010) Stolarsky's conjecture and the sum of digits of polynomial values.

[Edward_Tur]

В журнале "Квант" задача появилась в 1980 году:
http://kvant.mirror1.mccme.ru/1980/12/p14.htm

[maxal]

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

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

Решение из 14-го выпуска:

А. Я. Канель-Белов в http://www.mccme.ru/free-books/matpros/mpe.pdf писал(а):

Ответ: последовательность $s(n)/s(n^2)$ неограниченна.

Пусть $n=1+10^k-10^{2k-1}+10^{3k}+10^{4k}$. Ясно, что $s(n)=9k+12$, когда $k\ge 2$, так что $s(n)\to\infty$ при $k\to\infty$.

С другой стороны,

$$n^2=1+2\cdot 10^k+8\cdot 10^{2k-1}+18\cdot 10^{3k-1}+10^{4k-2}+4\cdot 10^{4k}+18\cdot 10^{5k-1}+8\cdot 10^{6k-1} +2\cdot 10^{7k}+10^{8k}$$

так что $s(n^2)=54$ при $k\ge 2$ и $\lim_{k\to\infty}s(n)/s(n^2)=\lim_{k\to\infty}(9k+12)/54=\infty$. Задача решена.

Замечания.
1. Решение задачи выглядит просто, однако для его получения потребовался месяц работы. Она в своё время довольно долго стояла во Второй школе (её нам сообщил В. А. Сендеров) как «полуоткрытый вопрос», т. е. задача с неясным решением. Немного видоизменив конструкцию, можно показать, что для любого $k>1$ последовательность $s(n)/s(n^k)$ неограничена. Более того, $n$ можно возводить в целую степень $\psi_n\sim (\ln n)^{0.5-\varepsilon}$. Для этого надо рассмотреть случаи $k=2,3$ и воспользоваться неравенством $s(nm)\le s(n)s(m)$ (верно также $s(n+m)\double \le s(n)+s(m)$, равенство достигается когда нет переноса разрядов).

2. Можно показать также, что $s(k^n)\to\infty$ при $n \to\infty$ если $k\ne 10^m$. Это следует из результатов Дж. Бейкера о диофантовых приближениях линейной комбинации логарифмов.

3. Можно построить число $n$ со сколь угодно большой суммой цифр, такое, что $s(n^3)=s(n)^3$ и $s(n^2)=s(n)^2$. Если же $s(n^4)=s(n)^4$ то либо $n=10^k$, либо $n=10^k+10^l$, $k\ne l$. Если $s(n^k)=s(n)^k$, $k\ge 5$, то $n=10^k$.

4. См. также задачу О. Ф. Крыжановского, предложенную на отборе 1994 года команды Москвы (10 класс) на Всероссийскую олимпиаду:

Пусть $P(x)^2$ имеет все положительные коэффициенты. Может ли многочлен $P(x)$ иметь коэффициенты разного знака?

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

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

Пусть $P(x)^2$ имеет все положительные коэффициенты. Может ли многочлен $P(x)$ иметь коэффициенты разного знака?

$$(x^4 + x^3 + x + 1)^2 = x^8 + 2x^7 + x^6 + 2x^5 + 4x^4 + 2x^3 + x^2 + 2x + 1$$

Значит, при достаточно малых положительных $\varepsilon$ коэффициенты многочлена $(x^4 + x^3 - \varepsilon x^2 + x + 1)^2$ положительны.

[maxal]

Я думаю, имелось в виду, что коэффициенты $P(x)$ целочисленны. В противном случае связь с исходной задачей не улавливается.
Впрочем, беря $\epsilon = \frac{1}{k}$ для достаточно большого $k$ и домножая на $k$, можно получить многочлен с целыми коэффициентами. Работает уже $k=2$:

$$(2x^4 + 2x^3 - x^2 + 2x + 2)^2 = 4x^8 + 8x^7 + 4x^5 + 17x^4 + 4x^3 + 8x + 4.$$

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

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

Работает уже $k=2$.

Не работает. У Вас коэффициенты при $x^6$ и $x^2$ нулевые, а надо, чтоб были положительные. Наверное, надо брать $k=3$

[maxal]

Профессор Снэйп в сообщении #347867 писал(а):

У Вас коэффициенты при $x^6$ и $x^2$ нулевые, а надо, чтоб были положительные.

Я понял так, что все ненулевые коэффициенты положительны, что выполняется и для $k=2$.