Вычислима ли функция?

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

Пусть для натурального $n$ число $o(n)$ равно количеству единиц в двоичной записи числа $n$ (к примеру, $o(7) = 3$, $o(8) = 1$ и т. д.) Пусть

$$ f(n) = \min \{ o(n^k) : k \in \mathbb{N},\, k > 0 \} $$

Вычислима ли функция $f$ (то есть существует ли алгоритм её вычисления)?

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

Возможно ли вообще, что $o(n^k) < o(n)$ при $k > 1$?

[ИСН]

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

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

ИСН в сообщении #300142 писал(а):

Здесь было где-то...

А ссылку не можете дать?

-- Вс мар 21, 2010 14:18:06 --

И ответ какой: возможно или нет?

[ИСН]

Вот, поискал и нашёл: topic11591.html

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

Спасибо, буду разбираться.

Там, кстати, явного примера не приведено. Сказано лишь, что при больших $m$ выполнено $s_2(n) > s_2(n^2)$ при

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

Проверил до $m=4$, не выполняется

[Xaositect]

Там есть ссылка на эту статью: http://arxiv.org/abs/1001.4169 , там есть какая-то оценка для минимального $n$, для которого $s_k(n^h)<s_k(n)$.