Ilość dwójek w rozkładzie liczby

[fon_nojman]

Podać wzór na liczbę dwójek występujących w rozkładzie liczby \(\displaystyle{ n\in N}\) na czynniki pierwsze.

PS: Nie chodzi tu o jakiś algorytm np dzielenie przez \(\displaystyle{ 2}\) dopóki nie uzyska się liczby nieparzystej tylko o konkretny wzór.

[Zordon]

heh, no to napiszmy wzór

niech \(\displaystyle{ f:\mathbb{R} \rightarrow \{0,1\}}\)
\(\displaystyle{ f(x)=1}\) gdy \(\displaystyle{ x \in \mathbb{Z}}\)
\(\displaystyle{ f(x)=0}\) w p.p.

oznaczmy funkcję "liczba dwójek" przez L. Wtedy:
\(\displaystyle{ L(n)= \sum_{k=1}^{ \infty }f(\frac{n}{2^k})}\)
wykazanie, że ten szereg jest zbieżny nie jest trudne

edit: można zamiast nieskończonej napisać sumę skończoną
\(\displaystyle{ L(n)= \sum_{k=1}^{ n }f(\frac{n}{2^k})}\)

[fon_nojman]

Fajny wzorek, myślałem że ktoś na początek napisze \(\displaystyle{ \max \{ k\in N:2^k|n \}}\).

Nie o to mi chodziło bardziej coś w stylu, że jak mamy np liczbę \(\displaystyle{ 50096}\) to jak z kolejnych jej cyfr można odczytać (jeżeli w ogóle można) liczbę dwójek występujących w jej rozkładzie (nie mylić z rozkładem martwej materii), bo wiadomo, że jak cyfra jedności jest parzysta to liczba dzieli się co najmniej przez \(\displaystyle{ 2}\), żeby dzieliła się przez \(\displaystyle{ 4}\) też jest reguła itd. Czy można to jakoś uogólnić na \(\displaystyle{ 2^k}\) i zapisać jakimś wzorkiem. Teraz już chyba jaśniej to sformułowałem.

[Zordon]

Fajny wzorek, myślałem że ktoś na początek napisze \(\displaystyle{ \max \{ k\in N:2^k|n \}}\).

Nie o to mi chodziło bardziej coś w stylu, że jak mamy np liczbę \(\displaystyle{ 50096}\) to jak z kolejnych jej cyfr można odczytać (jeżeli w ogóle można) liczbę dwójek występujących w jej rozkładzie (nie mylić z rozkładem martwej materii), bo wiadomo, że jak cyfra jedności jest parzysta to liczba dzieli się co najmniej przez \(\displaystyle{ 2}\), żeby dzieliła się przez \(\displaystyle{ 4}\) też jest reguła itd. Czy można to jakoś uogólnić na \(\displaystyle{ 2^k}\) i zapisać jakimś wzorkiem. Teraz już chyba jaśniej to sformułowałem.

Bardzo łatwo to zrobić, jeśli mamy rozwinięcie dwójkowe. Wtedy liczymy ile jest zer na końcu i mamy wynik.

[Inkwizytor]

Rozumiem fon_nojman, że chcesz poznać metodę w stylu: "paczem" na liczbe i wiem ile siedzi w niej dwójek. Owszem skuteczna to metoda gdy mamy do czynienia z zerem, z liczbą nieparzystą. Dla parzystych górnym ograniczeniem jest cecha z \(\displaystyle{ log_2(n)}\)

[Brzytwa]

Czy można to jakoś uogólnić na \(\displaystyle{ 2^k}\) i zapisać jakimś wzorkiem. Teraz już chyba jaśniej to sformułowałem.

Jedyną regułą jest to, że aby sprawdzić, czy dana liczba jest podzielna przez \(\displaystyle{ 2^k}\), że wystarczy sprawdzić dla \(\displaystyle{ k}\) ostatnich cyfr. Pozostałe wzory raczej opierają się na algorytmie dzieleniu przez 2 i sprawdzaniu czy liczba jest całkowita. W ostateczności można ręcznie liczyć .