Количество степеней 2ки в числе

[zZoMROT]

Простое утверждение:
$\forall m\in\mathbb{N}$ $\exists k\in\mathbb{N}: m = 2^{i_1}+2^{i_2}+...+2^{i_k}, i_j\in\mathbb{N}\cup\{0\}$ $\forall j\in\overline{1.k}$

Можно ли найти это $k$? Понятно, что можно представить $m_{10}$ -> $m_2$ и подсчитать, но это совсем неблагодарное занятие при достаточно больших m. Пробовал скрутить что-нибудь из рядов с остатками, но выходили только суммы, в которых были условия (т.е. суммируем по $i$ от 0, пока выполняется неравенство).
Без неравенств выражается ли $k$ через $m$?

[Alexey1]

Возьмите $k=m, i_1=...=i_k=0$.

[zZoMROT]

Спасибо, а если $i_j \in \mathbb{N}$ ?

Например, имея $x^{2^n} = x + 2 \sum\limits_{k=0}^{n-1} \sum\limits_{i=0}^{x^{2^k}-1} i$, мы можем получить выражение через ряды для любого числа в любой степени: $x^{2^{n_0}}*x^{2^{n_1}}*...$
Так вот, как определить в какой степени будет $x$, который вне сумм с коэффициентом 1?

[Alexey1]

zZoMROT в сообщении #348889 писал(а):

Спасибо, а если $i_j \in \mathbb{N}$ ?

В этом случае, $m$ кратно 2.

[zZoMROT]

Alexey1 в сообщении #348920 писал(а):

zZoMROT в сообщении #348889 писал(а):

Спасибо, а если $i_j \in \mathbb{N}$ ?

В этом случае, $m$ кратно 2.

да, но вопрос о $k$

[Alexey1]

У Вас же написано

zZoMROT в сообщении #348869 писал(а):

Простое утверждение:
$\forall m\in\mathbb{N}$ $\exists k\in\mathbb{N}: m = 2^{i_1}+2^{i_2}+...+2^{i_k}, i_j\in\mathbb{N}\cup\{0\}$ $\forall j\in\overline{1.k}$

то есть $m \in \mathbb N$.

[zZoMROT]

zZoMROT в сообщении #348869 писал(а):

Простое утверждение:
$\forall m\in\mathbb{N}$ $\exists k\in\mathbb{N}: m = 2^{i_1}+2^{i_2}+...+2^{i_k}, i_j\in\mathbb{N}\cup\{0\}$ $\forall j\in\overline{1.k}$

Понял ошибку. Разумеется, таких $k$ существует целое мн-во для каждого $m$. Вопрос о минимальном таком $k$.

[Alexey1]

А Вам алгоритм расчёта такого $k$ надо, или готовую формулу? Сформулируйте задачу полностью.

[zZoMROT]

Alexey1 в сообщении #348931 писал(а):

А Вам алгоритм расчёта такого $k$ надо, или готовую формулу?

Алгоритм понятно как составить. Меня интересует формула.

[Null]

А можно такой вопрос(правда это уже информатика)? Дано длинное число M в 10ичной системе исчисления. Можно ли посчитать его сумму цифр в двоичной системе исчисления быстрее чем за $O(n^2)$, где $n=\log M$?