Количество двоек в разложении числа

[maximus1986]

Здравствуйте. Скажите плиз, есть ли формула для определения количества двоек в разложении числа на простые сомножители? Т.е. чтобы можно было подставить это число в формулу и она бы выдала количество двоек?:) И вообще есть ли такие формулы для количества любого простого числа в разложении на простые сомножители?

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

А что понимается под "формулой"?

$$ k(n) = \max \{ p : 2^p | n \} $$

годится?

[maximus1986]

Ну под формулой я имею в виду использование основных математических операций: +, -, :, *(умножение), возведение в степень, факториал, а также тригонометрические функции, интегралы, производные... ээээ... ну и всё вроде:)
А как подскажите плиз пользоваться вашей формулой? Что то не пойму Что такое k, n, p?

[neo66]

maximus1986 писал(а):

Что такое k, n, p?

Ну, $k$ - это просто имя, $n$ - это ваше число, $p$ - это тоже натуральное число.

[maximus1986]

А можно по-подробней, как все-таки пользоваться этой формулой?

[ИСН]

Тупо как слоновья нога: делить, пока не перестанет делится. Когда перестанет делиться, тогда перестаём делить.
Да, увы, эта "формула" не подходит под Ваши "основные операции". Наверняка её можно с помощью синусов, косинусов и какой-то матери через них выразить, но вот поверьте на слово: не надо, не надо этого. Будет хуже. Не надо.

[RIP]

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

Наверняка её можно с помощью синусов, косинусов и какой-то матери через них выразить

Например, так

$$\sum_{k=1}^n2^{-k}\sum_{a=0}^{2^k-1}\cos\frac{\pi an}{2^{k-1}}.$$

[maximus1986]

Ух ты RIP, спасибо за формулу:) А для количества троек нужно в формуле вместо 2 поставить 3? Или это слишком наивно будет?

[RIP]

Для произвольного простого $p$ формула будет выглядеть так:

$$\sum_{k=1}^np^{-k}\sum_{a=0}^{p^k-1}\cos\frac{2\pi an}{p^k}.$$

Во внешней сумме в качестве верхнего предела подойдёт любое целое число $\ge\lfloor\frac{\log n}{\log p}\rfloor$.
А зачем Вам эта формула? Для счёта она совершенно бесполезна.

[maximus1986]

Да чисто для себя:) Когда-то хотел найти формулу для перевода из одной системы в другую. Ну т.е. чтобы подставить допустим в нее число в десятичной системе отсчета, произвести вычисления по этой формуле опять же в десятичной системе и в итоге получить результат, который будет в точности совпадать с этим числом в двоичной системе:) Формулу как нистранно получил, но там была одна неизвестная, которая портила всю картину - это как раз количество двоек в разложении числа на сомножители:) Сейчас вот вспомнил про это и решил узнать, может есть такая формула:)

[gris]

maximus1986 писал(а):

в десятичной системе отсчета

Это не та, которую Космонавты используют? Ключ на старт... 10...9...8...7...6...5...4...3...2...1...Поехали!

[maximus1986]

Было бы прикольно, если бы они говорили: 1010...1001...1000...111...110...101...100...11...10...1...Поехали!

[vlad239]

maximus1986 писал(а):

Было бы прикольно, если бы они говорили: 1010...1001...1000...111...110...101...100...11...10...1...Поехали!

Ей было тысяча сто лет,
Она в сто первый класс ходила,
В портфеле по сто книг носила —
Все это правда, а не бред.
Когда, пыля десятком ног,
Она шагала по дороге,
За ней всегда бежал щенок
С одним хвостом, зато стоногий.
Она ловила каждый звук
Своими десятью ушами,
И десять загорелых рук
Портфель и поводок держали.
И десять темно-синих глаз
Рассматривали мир привычно...
Но станет все совсем обычным,
Когда поймете наш рассказ.

Влад.

[maximus1986]

Ладно, шутки шутками... Я вот формулу получил для количества двоек в разложении числа, правда она не работает для чисел 16m, где m=1, 2, 3,... :

$$ \frac 1 {32} \left( 9+ i^ \frac n 2 \left(1+ i^ \frac n 2 + i^n \right) \right) \left( 3+ i^n \right) \left( 1+ \left( -1 \right) ^n \right) $$

Может кто-нибудь поможет ее усовершенствовать?

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

n - проверяемое число, i - мнимая единица.

[gris]

Ну нечётные сразу отбросим, форула справедливо выдаёт 0. Подставим $n=2k$

$$ \frac 1 {32} \left( 9+ i^ \frac {2k} 2 \left(1+ i^ \frac {2k} 2 + i^{2k}\right) \right) \left( 3+ i^{2k} \right) \left( 1+ \left( -1 \right) ^{2k} \right) =$$

$$ \frac 1 {16} \left( 9+ i^ k \left(1+ i^ k +(-1)^k\right) \right) \left( 3+ (-1)^k \right)$$

Для нечётных $k$ справедливо выдаёт 1.

Подставим $k=2m$

$$ \frac 1 {4} \left( 9+ (-1)^m \left(2+(-1)^m\right) \right)\right) $$

Для нечётных $m$ справедливо выдаёт 2.

Подставим $m=2l$

$$ \frac 1 {4} \left( 9+1 \left(2+1\right) \right)\right) =3$$

Как видим, формула может определить только 3 двойки. Но не беда! Для 93% чисел формула работает. Только объясните, как Вы будете возводить $i$ скажем в 1460-ю степень? И в половинку от неё?

Хотя даже при подстановке $n=1$ начинаются проблемы. Вы переставили бы сомножители, чтобы ноль отлавливать. Или для того, чтобы применять формулу, нужно сначала кое-что сделать?