Podzielność liczby 2^2006!

[BlueSky]

Wyznaczyć największą liczbę naturalną \(\displaystyle{ k}\) taką, że \(\displaystyle{ 2^k}\) dzieli liczbę \(\displaystyle{ 2^{2006}!}\).

[Vax]

Skorzystaj z tego, że \(\displaystyle{ v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i}\right\rfloor}\)

[BlueSky]

Niestety mało mi ta wskazówka mówi...

[Vax]

Nasze \(\displaystyle{ k}\) to po prostu \(\displaystyle{ \sum_{i=1}^{\infty}\left\lfloor\frac{2^{2006}}{2^i}\right\rfloor = 2^{2005}+2^{2004}+...+2+1 = 2^{2006}-1}\)

[Marcinek665]

Jako że obydwa posty Vaxa są zupełnie niezrozumiałe w przypadku braku znajomości odpowiedniej aparatury, pozwolę sobie zabrać głos.

Chcemy w ogólności sprawdzić, z jakim wykładnikiem wchodzi liczba \(\displaystyle{ 2}\) w rozkład liczby \(\displaystyle{ n!}\) (potem wstawimy \(\displaystyle{ n=2^{2006}}\) i rozwiążemy zadanie). Liczbę taką oznaczamy jako \(\displaystyle{ v_2(n!)}\).

No ale w tym celu wystarczy sprawdzić ile jest liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), które dzielą się przez \(\displaystyle{ 2}\), potem przez \(\displaystyle{ 2^2}\), potem przez \(\displaystyle{ 2^3}\) itp, a następnie wszystko to po prostu zsumować. Liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), które dzielą się przez \(\displaystyle{ 2^k}\) jest oczywiście \(\displaystyle{ \left\lfloor\frac{n}{2^k}\right\rfloor}\), zatem wystarczy wysumować to od \(\displaystyle{ k=1}\) do nieskończoności. W rzeczywistości ta suma będzie oczywiście skończona, bo gdy licznik będzie mniejszy od mianownika, to w sumie występować będą same zera.

Liczymy więc: \(\displaystyle{ \sum_{i=1}^{\infty}\left\lfloor\frac{2^{2006}}{2^i}\right\rfloor = 2^{2005}+2^{2004}+...+2+1 = 2^{2006}-1}\)

i jest ok.

[Ponewor]

Gwoli uzupełnienia dodam, że nie ma powodu by traktować dwójkę w szczególny sposób - można ją z powodzeniem zastąpić dowolną liczbą pierwszą. Tutaj, też ktoś coś podobnego zliczał, ale ujął to nieco innymi słowami niż Marcinek665.

[BlueSky]

ok, dziękuję wszystkim za pomoc