Rój dwój, czyli potęgowo i parzyście

Znana od ponad 10 wieków anegdota o nagrodzie dla wynalazcy szachów zawiera jedno z najbardziej zwodniczych zadań arytmetycznych. Rzekomy wynalazca miał jakoby zażyczyć sobie od pewnego zachwyconego grą władcy porcję pszenicy zgarniętą z szachownicy, na której najpierw to zboże byłoby układane w następujący sposób: jedno ziarno na pierwszym polu, dwa na drugim, cztery na trzecim, osiem na czwartym itd., czyli na każdym następnym polu, aż do sześćdziesiątego czwartego, liczba ziaren powinna być dwukrotnie większa niż na poprzednim. W pierwszej chwili wydaje się – i władca tak właśnie sądził – że życzenie jest nader skromne i aby je spełnić wystarczy duży wór ze zbożem; no, powiedzmy, kilka worków. Dopiero obliczenia pozwalają ujawnić astronomiczny wymiar nagrody.

Chodzi o sumę wyrazów S₆₄ ciągu geometrycznego o ilorazie q=2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,…, czyli ciągu potęg dwójki 2⁰, 2¹, 2², 2³, 2⁴,…, 2⁶³ (a_i=2^i-1, i=1, 2, 3,…, 62, 63, 64). Jeśli ten ciąg podwoimy, czyli zwiększymy każdy wykładnik o 1, to suma wyrazów nowego ciągu (2¹, 2², 2³, 2⁴,…, 2⁶⁴) wyniesie 2S₆₄. Teraz w sprytny sposób wyznaczymy sumę S₆₄=2S₆₄–S₆₄=2⁶⁴–1, a ogólnie S_n=2S_n–S_n=2ⁿ–1, co oznacza 18 446 744 073 709 551 615, czyli ponad 18 trylionów ziaren. Ponieważ tysiąc ziaren pszenicy waży około 45 g, więc plon z szachownicy wyniesie nieco ponad 8×10¹¹, czyli 800 mld ton. Dysponowanie taką ilością pszenicy wymagałoby zgromadzenia wszystkich zbiorów z całego świata z ponad tysiąca lat, jeśli przyjąć roczną produkcję na obecnym poziomie. Ten wynik wydaje się tak nieprawdopodobny w zestawieniu z okolicznościami, w których się pojawia, że skłania do szukania grubego (niepopełnionego) błędu w obliczeniach.

Dwójka jest najmniejszą liczbą naturalną, która „potężnieje” przy potęgowaniu (zero i jedynka nie zmieniają się), więc jej potęgi tworzą ciąg wnikliwie analizowany jako swego rodzaju wzorzec ciągu potęg. Praktycznie najistotniejszy wniosek z tych analiz brzmi: każda liczba naturalna jest sumą potęg dwójki. Ściślej: każda liczba naturalna N jest sumą unikalnego zestawu różnych potęg dwójki mniejszych od N. Ten wniosek jest oczywisty dla wszystkich, którym nieobce są teoretyczne podstawy systemów liczbowych, a w tym przypadku powszechnie stosowanego w informatyce systemu dwójkowego. Prosty dowód zaczyna się od zapisu liczby X w systemie jedynkowym, czyli w postaci X pionowych kresek. Dalsza procedura przypomina sporządzanie tabeli rozgrywek sportowych systemem pucharowym: po przypisaniu kreskom wartości liczbowych 1=2⁰ w kolejnych etapach łączy się je w pary, a każda para daje liczbę dwukrotnie większą, a więc kolejną potęgę dwójki. Jeśli liczba potęg na danym etapie jest nieparzysta, to jedna potęga pozostaje bez pary i „przechodzi bez gry” do końcowej sumy. Cały taki proces dla liczby 13 przedstawiony jest na rys. 1. Z efektu końcowego wynika zapis trzynastki w systemie binarnym: obecność danej potęgi dwójki to jedynka w zapisie, brak potęgi – zero, czyli 13₁₀=1101₂.

Z podanego wyżej wzoru na liczbę ziaren wynika, że każdy wyraz w ciągu potęg dwójki jest o 1 większy od sumy wszystkich mniejszych. Stąd możliwość zdefiniowania ciągu z pominięciem słowa „potęga”: każdy następny wyraz jest najmniejszym, którego nie uda się utworzyć, sumując dowolne poprzednie. Jeszcze ciekawsze jest inne bezpotęgowe określenie ciągu: tworzą go wyrazy, które nie są sumami co najmniej dwóch kolejnych liczb naturalnych. Czy rzeczywiście, dodając do siebie kolejne liczby naturalne: (a) nigdy nie uzyskamy potęgi dwójki, natomiast (b) możemy utworzyć w ten sposób każdą inną liczbę?

Najpierw udowodnimy (a), korzystając ze wzoru na sumę wyrazów ciągu arytmetycznego skończonego. Suma ta równa jest połowie iloczynu sumy wyrazów pierwszego (a₁) i ostatniego (a_n>a₁) przez liczbę wyrazów, czyli dla kolejnych liczb naturalnych będzie wynosić S_n=(a₁+a_n)×(a_n–a₁+1)/2. Łatwo zauważyć, że jeden z dwu czynników w iloczynie zawsze musi być parzysty, a drugi nieparzysty, zatem S_n będzie wielokrotnością liczby nieparzystej, czyli potęgą dwójki być nie może.

Dowód (b) jest nieco bardziej złożony. Z liczbami nieparzystymi nie ma problemu, bo każdą można przedstawić w postaci 2k+1=k+(k+1), czyli na przykład: 2019=1009+1010. W przypadku liczb parzystych P uwzględniamy oczywiście tylko te, które nie są potęgami dwójki, ale każda jest wielokrotnością przynajmniej jednej z tych potęg i może być przedstawiona w postaci 2^m×(2k+1), gdzie 2^m (m≥1) stanowi największą potęgę dwójki wśród dzielników P. Teraz należy rozpatrzyć dwa przypadki.

Jeżeli 2^m+1>2k+1, to P jest sumą 2k+1 kolejnych liczb od 2^m–k do 2^m+k.

Przykład: P=56=8×7=2³×(2×3+1), czyli 2^m+1=2⁴>7 (m=3, k=3), a więc P=56=5+6+7+8+9+10+11.

Jeżeli 2^m+1<2k+1, to P jest sumą 2^m+1 kolejnych liczb od k+1–2^m do k+2^m.

Przykład: P=58=2×29=2¹×(2×14+1), czyli 2^m+1=2²<29=2×14+1=2k+1, a więc P=58=13+14+15+16.

Potęgi dwójki można określać również kombinatorycznie i to na kilka sposobów. 2ⁿ jest na przykład liczbą n-elementowych wariacji z powtórzeniami ze zbioru 2-elementowego. Bardziej obrazowo: jeśli mamy ścianę z n oknami i w każdym wieczorem może się palić światło, to na ścianie pojawia się jeden z 2ⁿ różnych świetlnych wzorów. 2ⁿ jest także liczbą permutacji unimodalnych zbioru n+1 różnych liczb. Unimodalność oznacza, że istnieje co najwyżej jedno ekstremum lokalne. Inaczej mówiąc, w permutacji nie więcej niż jedna liczba umieszczona jest między dwiema mniejszymi od niej. Na przykład, pięć cyfr nieparzystych tworzy 16 permutacji unimodalnych: 13579, 13597, 13795, 15793, 13975, 15973, 17953 i 19753 plus cała ósemka zapisana wspak. I jeszcze jedno kombinatoryczne określenie, ale z grona bardziej wyszukanych: 2ⁿ jest liczbą permutacji n+1 elementów, z których żaden nie jest przesunięty dalej niż o jedno miejsce w prawo w stosunku do początkowego ustawienia (np. 8 permutacji ABCD: ABCD, ABDC, ACBD, ADBC, BACD, BADC, CABD, DABC).

Inny dwójkowy temat stanowią początkowe i końcowe fragmenty liczb będących potęgami dwójki. Końcówki są mniej problematyczne – ostatnie cyfry kolejnych potęg tworzą ciąg okresowy z okresem 4-cyfrowym: 1, 2, 4, 8, 6, [2, 4, 8, 6], …. Cyklicznie potarzają się także końcowe pary, a w okresie jest ich dwadzieścia: 01, 02, [04, 08, 16, 32, 64, 28, 56, 12, 24, 48, 96. 92, 84, 68, 36, 72, 44, 88, 76, 52], 04, 08 … Ogólnie wszystkie t-cyfrowe końcówki tworzą ciągi, których okres wynosi 4×5^t-1, więc np. dla finalnych tercetów jest równy okrągłej setce.

O ile końcówkami są tylko parzyści wybrańcy, o tyle czołówka jest bardziej demokratyczna – może nią być każda liczba naturalna, choć początek ciągu potęg dwójki wydaje się temu przeczyć. Ciąg pierwszych cyfr kolejnych wyrazów zaczyna się bowiem jak okresowy z 10-cyfrowym okresem [1, 2, 4, 8, 1, 3, 6, 1, 2, 5], powtarzającym się 4-krotnie do 2³⁹=549755813888. Stąd goszczące czasem w podręcznikach zadania w rodzaju następującego: czy potęga dwójki może zaczynać się siódemką?

Konkretny przykład łatwo znaleźć, mnożąc w kolejnych krokach najmniejszą potęgę dwójki, zaczynającą się szóstką (2⁶=64) przez wielokrotności jak najmniejszej potęgi dwójki nieznacznie przekraczającej jakąś potęgę dziesiątki – odpowiednią jest 2¹⁰=1024. W każdym następnym iloczynie (2¹⁶, 2²⁶, 2³⁶, …) druga cyfra będzie coraz większa, zbliżając się do granicy (9), po przekroczeniu której „wymusi” zmianę pierwszej szóstki na siódemkę. Stanie się tak dla 2⁴⁶=70 368 744 177 664. Podobnie można znaleźć potęgę zaczynającą się nieobecną w powyższym 10-cyfrowym okresie dziewiątką. W tym przypadku obliczamy iloczyny z mnożną równą 8=2³, czyli 2¹³, 2²³, 2³³, … Szukany wynik pojawia się dla 2⁵³=9 007 199 254 740 992. Korzystanie z mnożnika wielokrotności 2¹⁰ jest teoretycznie skuteczne dla wszystkich czołówek. Na przykład, szukając potęg zaczynających się od 33 (2⁵+1) i 65 (2⁶+1), dotrzemy do celu dla 33 w drugim kroku – 2²⁵=33 554 432, a dla 65 natychmiast – 2¹⁶=65 536. Praktycznie skuteczność tej metody jest ograniczona ze względu na żmudne obliczenia (przydaje się kalkulator z bardzo długim okienkiem), a także pomijanie niektórych małych wyników. Gdybyśmy na przykład szukali potęgi dwójki zaczynającej się od 257, korzystając z mnożnej 256=2⁸, to dotarlibyśmy do 2342-cyfrowego giganta równego 2⁷⁷⁷⁸. Po drodze, niestety, pominęlibyśmy najkrótszą, bo „tylko” 62-cyfrową, zaczynającą się od 257 potęgę 2²⁰⁴.

Ogólny dowód tego, że potęga dwójki może zaczynać się dowolną liczbą, nie jest trudny, ale dość długi. Jego podstawę stanowi niewymierność logarytmu dziesiętnego z 2. Oczywiście, im dłuższe czołówki, tym częściej rozpoczynają one potęgi-giganty. Liczba potęg dwójki z wykładnikiem mniejszym od 1000, których 4-cyfrowe czołówki stanowią lata XXI wieku, jest równa – jakżeby inaczej – 22. Z dwóch najmniejszych potęg pierwsza dotyczy roku 2048=2¹¹, a druga ostatniego „potęgowego”, czyli 2097, bo 2²¹=2097152. Bieżący rok wymaga wykładnika 2044 i daje zaczynającą się kwartetem 2019 liczbę 616-cyfrową.

Łatwo zauważyć, że ciąg kolejnych potęg dwójki składa się z następujących po sobie grup 3- i 4-wyrazowych. Każdą grupę tworzą liczby, w których jest tyle samo cyfr. Pierwsza liczba w grupie zawsze zaczyna się jedynką, druga – dwójką lub trójką, trzecia – czwórką, piątką, szóstką lub siódemką, czwarta (jeśli jest) – ósemką lub dziewiątką. Stąd wniosek, który potwierdza statystyka: im większa cyfra (liczba jednocyfrowa), tym rzadziej występuje na początku potęg dwójki; dziewiątka ponad 6-krotnie rzadziej niż jedynka. Ta reguła była jedną z inspiracji do sformułowania tzw. prawa Benforda, zgodnie z którym w większości wykazów liczbowych, dotyczących różnych rzeczywistych sytuacji (dane statystyczne, księgowość, bankowość itp.), rozkład prawdopodobieństwa występowania określonych cyfr na początku liczb z grubsza odpowiada ich rozkładowi wśród pierwszych cyfr liczb 2ⁿ.

Potęgi dwójki stanowią „generator” różnych specyficznych rodzajów liczb. Dwa z nich są podobnej postaci: 2ⁿ–1, czyli suma n początkowych wyrazów ciągu 2ⁿ – to tzw. liczby Mersenne’a oraz 2ⁿ+1 – to liczby ogólnie bezimienne. Racją bytu obu tych rodzajów jest ich powiązanie z liczbami pierwszymi. Liczba Mersenne’a jest liczbą pierwszą wtedy, gdy n także jest liczbą pierwszą (warunek konieczny). Szukanie największych liczb pierwszych sprowadza się więc do podnoszenia dwójki do gigantycznej potęgi, będącej liczbą pierwszą, i sprawdzania, czy liczbę o jeden mniejszą uda się rozłożyć na czynniki pierwsze. Aktualne rekordowe znalezisko ma blisko 25 mln cyfr i powstało w wyniku działania 2^{82 589 933}–1.

Liczby postaci 2ⁿ+1 są pierwsze tylko jako tzw. liczby Fermata, w których potęga dwójki jest… potęgą dwójki (n=2^k) – to także warunek tylko konieczny. Niestety, na razie znanych jest zaledwie pięć liczb pierwszych Fermata – dla k=0, 1, 2, 3, 4, ale nikt nie udowodnił, że nie ma ich więcej.

Potęgi dwójki najbliżej spokrewnione są z liczbami doskonałymi. Każda z nich jest z definicji sumą wszystkich swoich dzielników właściwych, ale każdą można utworzyć w sposób niemający z dzielnikami pozornie nic wspólnego. W tym celu należy skorzystać z dwóch kolejnych potęg dwójki. Od większej trzeba odjąć 1 i jeśli różnica będzie liczbą pierwszą, to po pomnożeniu jej przez mniejszą potęgę otrzymamy liczbę doskonałą. Na przykład, 2⁵–1=31 jest liczbą pierwszą i po pomnożeniu przez 2⁴=16 daje 496, czyli trzecią liczbę doskonałą, ponieważ jest ona równa sumie swoich dziewięciu dzielników właściwych – 1+2+4+8+16+31+62+124+248=496. Ogólnie korzystamy ze wzoru (2^p–1)×(2^p–1), w którym mnożna jest liczbą pierwszą Mersenne’a.

Z potęgami dwójki związanych jest jeszcze kilka innych nierozstrzygniętych problemów bliskich teorii liczb. Na przykład nie wiadomo, czy 2⁸⁶ jest największą potęgą dwójki, która nie zawiera zera (77 371 252 455 336 267 181 195 264). Wiadomo natomiast, że wspomniana na początku tego artykułu „szachownicowa” potęga 2⁶⁴ nie jest największą potęgą dwójki bez… dwójki.

Potęgi dwójki pojawiają się także w niektórych rozrywkach i zabawach matematycznych. Dwie z nich, klasyczną i współczesną, dzieli blisko 150 lat. Klasyczna, zwana wieżą Hanoi (rys. 2), jest raczej evergreenem niż przeżytkiem. Polega na przeniesieniu kilku krążków z otworami ze słupka A na C, z wykorzystaniem pośrednictwa słupka B, na który także można, a właściwie trzeba nadziewać krążki. Wolno przenosić wyłącznie po jednym krążku i umieszczać na słupkach zawsze tylko mniejszy krążek na większym. Minimalną liczbę ruchów potrzebną do uporania się z tą łamigłówką nietrudno ustalić, korzystając z metody indukcji.

Zakładamy, że minimalna liczba ruchów dla n-1 krążków równa jest R_n-1 i szukamy R_n. Przy n krążkach w pewnym momencie konieczne okaże się przeniesienie największego krążka ze słupka A na pusty C; na słupku B będzie wówczas n-1 krążków ułożonych jak należy, czyli sytuacja ta nastąpi po wykonaniu R_n-1 ruchów. Następnie trzeba będzie powtórzyć przeniesienie n-1 krążków, ale tym razem ze słupka B na największy krążek leżący na słupku C, co ponownie będzie wymagać R_n–1 ruchów. A zatem R_n=2R_n–1+1. Ponieważ R₁=1, więc z wzoru rekurencyjnego wynikają wartości R₂=3, R₃=7, R₄=15, R₅=31 itd., a w końcu wzór na najmniejszą liczbę ruchów: R_n=2ⁿ–1, czyli ponownie liczby Mersenne’a.

Współczesna dwójkowa zabawa wiąże się z potęgami dwójki bezpośrednio i formalnie. To niebezpiecznie wciągająca łamigłówkowa gra komputerowa 2048, która podbiła internet przed pięciu laty. W polach planszy 4×4 pojawiają się i są przesuwane płytki z potęgami dwójki. Na początku jest zwykle tylko para płytek – każda z dwójką lub czwórką, a po każdym ruchu na jakimś pustym polu pojawia się kolejna dwójka lub czwórka. Ruch polega na przesunięciu za pomocą klawisza-strzałki równocześnie wszystkich płytek, każdej do oporu, w jedną z czterech głównych stron. Jeśli przed lub po przesunięciu w stronę K dwie takie same liczby są lub znajdą się obok siebie, to ta od strony K jakby „wciąga” sąsiadkę, ulegając podwojeniu. Gdy takie same są trzy kolejne liczby, znika środkowa a podwojeniu ulega tylko skrajna od strony K, gdy cztery – rezultatem są dwie podwojone od strony K. Warianty te ilustrują przykłady na rys. 3: w środku układ przed ruchem, a z każdej strony sytuacja po przesunięciu w daną stronę. W grze chodzi o utworzenie liczby 2048. Nie jest to łatwe ze względu na sporą szansę zablokowania rozgrywki, gdy liczby pojawią się na wszystkich polach, ale nigdzie na sąsiednich nie będzie jednakowych. Teoretycznie możliwe jest jednak dotarcie nawet do 131 072=2¹⁷. Mimo losowości związanej z pojawianiem się w każdym ruchu dwójki lub czwórki na dowolnym pustym polu, gra jest w znacznym stopniu logiczna i ma ciekawą strategię, której ogólną podstawę stanowi umiar w dążeniu do celu. Ale to już całkiem inna historia.

Zadania

1. Który z trzech poniższych iloczynów i dla jakich najmniejszych dodatnich wartości a i b jest potęgą dwójki?

(16a+b)×(a+16b)

(25a+b)×(a+25b)

(36a+b)×(a+36b)

2. Liczba dziesiętna równa 2²⁰¹⁹ ma 608 cyfr i zaczyna się szóstką. Ile potęg dwójki w zakresie od 2⁰ do 2²⁰¹⁹ zaczyna się czwórką?

3. Uczeń przestawił cyfry w liczbie równej 2ⁿ i oświadczył, że powstała liczba jest równa:

a) także potędze dwójki;

b) potędze trójki;

c) potędze piątki.

Które ze stwierdzeń a, b, c mogło (mogły) być prawdziwe?

4. Zbiór wszystkich dotychczasowych lat naszej ery, czyli liczb całkowitych od 1 do 2019 dzielimy na dwa podzbiory: A – zawierający liczby które można przedstawić w postaci sumy pięciu potęg dwójki (niekoniecznie różnych) oraz B – pozostałe liczby. Który zbiór będzie liczniejszy?

Rozwiązania prosimy nadsyłać do 31 lipca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 7/19. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Szczególna teoria względności i klasyczna teoria pola Leonarda Suskinda i Arta Friedmana ufundowaną przez wydawnictwo Prószyński Media. Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:

Zapoznałam/em się z regulaminem Konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji Konkursu.

Regulamin Konkursu jest dostępny na stronie www.swiatnauki.pl

***

ROZWIĄZANIA ZADAŃ Z NUMERU MAJOWEGO

1. Z ośmiu wskazanych kamieni tym, który nie znalazł się w mnożeniach, był kamień 1-1. Ułożone mnożenia: 66×5=330, 554×4=2216.

2. Mnożenie: 66×154=10164.

3. Mnożnik – 202; całe mnożenie: 666×202=134532.

4. Wszystkie mnożenia: 50×30=1500, 54×21=1134, 55×44=2420, 62×36=2232, 64×40=2560, 66×16=1056.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Maxa Tegmarka Życie 3.0. Człowiek w erze sztucznej inteligencji, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Jakub Berkowski z Twardogóry, Joanna Budzyn z Warszawy, Mateusz Filarowski z Wrocławia, Łukasz Jach z Czeladzi, Zbigniew Kapusta z Banina.