Łańcuchy dodawań Ulama

Mate­ma­ty­ka jest sztu­ką nada­wa­nia tej samej nazwy róż­nym rze­czom.¹
H. Poincaré

Wpro­wa­dze­nie
Sło­wo mate­ma­ty­ka pocho­dzi od grec­kie­go sło­wa μανθάνω (=uczę się).
Myśleć, odkry­wać, uczyć się to isto­ta tego, czym jest matematyka.
Nauka nie wyklu­cza oczy­wi­ście zabawy.

Zapra­sza­my cię do pra­cow­ni mate­ma­tycz­nej, w któ­rej będzie­my zaj­mo­wać się łańcuchami.
Do pra­cy będzie ci potrzeb­ny zeszyt w krat­kę i długopis.

Pierw­sze pro­jek­ty łańcuchów
Ogni­wa, czy­li „oczka” naszych łań­cu­chów będą dwóch rozmiarów.

Powyż­szy rysu­nek przed­sta­wia pro­jek­ty łań­cu­chów o roz­mia­rach: 3, 4, 6, 8 i 11.²

Rów­no­ści zapi­sa­ne przy pro­jek­tach łań­cu­chów są infor­ma­cją na temat spo­so­bu utwo­rze­nia łań­cu­cha: pierw­szy łań­cuch jest złą­cze­niem „oczek” o roz­mia­rach 1 i 2, dru­gi łań­cuch jest złą­cze­niem „oczka” roz­mia­ru 1, i tak dalej. Ostat­ni łań­cuch powstał przez złą­cze­nie dwóch łań­cu­chów o roz­mia­rach 3 i 8.
Przed­sta­wio­ne na rysun­ku łań­cu­chy powsta­ły więc według ści­śle okre­ślo­nych zasad. Te regu­ły rzą­dzą­ce pro­jek­to­wa­niem naszych łań­cu­chów ujaw­ni­my w kolej­nych akapitach.
Łań­cu­chy speł­nia­ją­ce regu­ły będzie­my nazy­wać popraw­ny­mi łańcuchami.

Pro­jek­ty łań­cu­chów o więk­szych rozmiarach
Two­rząc pro­jek­ty kolej­nych łań­cu­chy będzie­my postę­po­wa­li w spo­sób sys­te­ma­tycz­ny – będzie­my szu­kać naj­krót­sze­go popraw­ne­go łań­cu­cha dłuż­sze­go od wszyst­kich zna­le­zio­nych do tej pory.
Dla­cze­go wśród pro­jek­tów na rysun­ku nie było łań­cu­chów dłu­go­ści 5, 7, 9 ani 10?
Otóż popraw­ne łań­cu­chy takich dłu­go­ści po pro­stu nie ist­nie­ją. Wyma­ga­my bowiem, by nowy łań­cuch dał się przed­sta­wić jako złą­cze­nie dwóch róż­nych popraw­nych łań­cu­chów jed­no­znacz­nie, czy­li w jeden tyl­ko sposób.
Dla łań­cu­cha dłu­go­ści 5 wybór pary krót­szych łań­cu­chów nie był­by jed­no­znacz­ny – spo­so­by są dwa:

W podob­ny spo­sób moż­na wyja­śnić, dla­cze­go nie ma popraw­nych łań­cu­chów dłu­go­ści 7, 9 ani 10.

Co cie­ka­we, dla licz­by 23 – ina­czej niż dla wszyst­kich mniej­szych liczb, dla któ­rych nie da się utwo­rzyć łań­cu­cha o tym roz­mia­rze w spo­sób jed­no­znacz­ny – w ogó­le nie da się zbu­do­wać żad­ne­go łań­cu­cha, któ­ry powstał­by przez złą­cze­nie dwóch krót­szych popraw­nych łańcuchów.

Licz­by Ulama
Gdy zapi­sze­my dłu­go­ści łań­cu­chów speł­nia­ją­cych regu­ły w kolej­no­ści ich zna­le­zie­nia (utwo­rze­nia), oddzie­la­jąc kolej­ne licz­by prze­cin­kiem, to utwo­rzy­my ciąg licz­bo­wy: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18. Licz­ba 1 jest pierw­szym, licz­ba 2 – dru­gim, a licz­ba 18 – dzie­sią­tym ele­men­tem tego ciągu.
Mate­ma­ty­kiem, któ­ry zaj­mo­wał się tym cią­giem licz­bo­wym był Sta­ni­sław Ulam (1909–1984), Polak żydow­skie­go pocho­dze­nia, mate­ma­tyk słyn­nej Lwow­skiej Szko­ły Mate­ma­tycz­nej, któ­ry od sierp­nia 1939 r. miesz­kał w USA. W 1954 r. przy­jął ame­ry­kań­skie obywatelstwo.

Defi­ni­cja cią­gu poda­na przez Sta­ni­sła­wa Ula­ma w 1962 roku³ w prze­kła­dzie na język pol­ski brzmi: Defi­niu­je­my ciąg liczb cał­ko­wi­tych w nastę­pu­ją­cy spo­sób: zaczy­na­jąc od liczb cał­ko­wi­tych 1, 2, kon­stru­uje­my kolej­no nowe, bio­rąc pod uwa­gę sumy dwóch wcze­śniej zde­fi­nio­wa­nych liczb cał­ko­wi­tych, ale nie włą­cza­jąc do nasze­go zbio­ru tych liczb cał­ko­wi­tych, któ­re moż­na uzy­skać jako sumę poprzed­nich w wię­cej niż w jeden spo­sób. Nigdy nie doda­je­my licz­by do samej siebie.

W mate­ma­ty­ce mówi się o cią­gu Ula­ma, a ele­men­ty cią­gu nazy­wa się licz­ba­mi Ula­ma⁴.
Regu­ły two­rze­nia popraw­nych łań­cu­chów są toż­sa­me regu­łom two­rze­nia cią­gu Ulama.
Co ty na to, by w takim razie popraw­ne łań­cu­chy nazy­wać łań­cu­cha­mi Ula­ma?

Łań­cu­chy [doda­wań]
Pierw­szym łań­cu­chem o dłu­go­ści więk­szej niż 18, któ­ry będzie jede­na­stym na liście łań­cu­chów Ula­ma, jest łań­cuch dłu­go­ści 26, któ­ry jest połą­cze­niem łań­cu­chów o dłu­go­ściach 8 i 18:

Ile doda­wań trze­ba wyko­nać, aby obli­czyć 26, czy­li jede­na­stą licz­bę w cią­gu Ulama?
Przy­wo­łaj­my rów­no­ści licz­bo­we, któ­ry­mi opi­sy­wa­li­śmy nowo utwo­rzo­ne (zna­le­zio­ne) łańcuchy.

3 = 1 + 2
4 = 1 + 3
6 = 2 + 4
8 = 2 + 6
11 = 3 + 8
13 = 2 + 11
16 = 3 + 13
18 = 2 + 16
26 = 8 + 18

Łatwo poli­czyć, że doda­wań jest 9.
W mate­ma­ty­ce aku­mu­la­cyj­ny ciąg doda­wań, w któ­rym skład­ni­ki każ­dej sumy, nie licząc pierw­szej, są wyzna­czo­ne wcze­śniej jako sumy, nazy­wa się łań­cu­chem doda­wań (ang. addi­tion cha­in)⁵.
Łatwiej prze­ko­nać się, że ta nazwa jest ade­kwat­na, gdy ten ciąg doda­wań przed­sta­wi­my na rysunku

lub w posta­ci rów­no­ści z tzw. zagnież­dżo­nym doda­wa­niem, gdzie nawia­sy okre­śla­ją kolej­ność dzia­łań 26 = 8 + (2 + (3 + (2 + (3 + (2 + (2 + (1 + (1 + 2)))))))).

Kolej­ną, czy­li dwu­na­stą licz­bą Ula­ma jest 28, któ­ra jest sumą 2 i 26.
Aby ją wyzna­czyć trze­ba wyko­nać 10 doda­wań. Pierw­sze z nich to oczy­wi­ście 1 + 2, a ostat­nie: 2 + 26.

Wyjąt­ko­wy łańcuch
Wszyst­kie do tej pory wymie­nio­ne licz­by Ula­ma (oczy­wi­ście poza 1 i 2) były sumą poprze­dza­ją­cej je licz­by Ula­ma i innej mniej­szej licz­by z cią­gu Ula­ma. Podob­nie jest w przy­pad­ku dwóch kolej­nych liczb (36 i 38) tego cią­gu: 36 = 8 + 28, nato­miast 38 = 2 + 36.
Oka­zu­je się, że wca­le tak być nie musi! Przy­kła­dem jest 47, czy­li pięt­na­sta licz­ba w cią­gu Ulama.

Ilu­stra­cja łań­cu­cha doda­wań dla licz­by 47 wyglą­da tak:

Licz­ba 47 jest sumą liczb 11 i 36, a więc siód­mej licz­by w cią­gu Ula­ma i trzy­na­stej licz­by tego cią­gu. To ozna­cza, że moż­na ją wyzna­czyć, wyko­nu­jąc 12 doda­wań. Tyle samo co dla czter­na­stej licz­by (38).

Dla­te­go w wyra­że­niu (poni­żej) po pra­wej stro­nie rów­no­ści znaj­du­je 12 zna­ków dodawania.

47 = ((1+2) + (2 + (2 + (1 + 3)))) + (8 + (2 + (8 + (2 + (3 + (2 + 11)))))))

Zain­te­re­so­wa­nych tema­tem cią­gu Ula­ma odsy­ła­my do inter­ne­to­wej ency­klo­pe­dii https://oeis.org/ ⁸.
Te zagad­nie­nia kry­ją zapew­ne jesz­cze wie­le tajem­nic, któ­re cze­ka­ją na odkry­cie⁹.

Zakoń­cze­nie
Nasza pra­ca, kolej­ne jej eta­py, była namiast­ką tego, czym jest two­rze­nie (odkry­wa­nie?) mate­ma­ty­ki. Jeśli ci się to podo­ba­ło, to może war­to o tym komuś opowiedzieć?

Przy­pi­sy
¹ Poin­ca­re, H.: 1911 [1908], Nauka i Meto­da, War­sza­wa 1911.
² Ponie­waż ogni­wa two­rzą­ce łań­cu­chy będą na kart­ce w krat­kę przed­sta­wia­ne jako okrę­gi opi­sa­ne na kwa­dra­tach o bokach dłu­go­ści jed­nej lub dwóch kra­tek, to mówiąc o roz­mia­rach ogniw i two­rzo­nych przez nie łań­cu­chów, będzie­my – dla uprosz­cze­nia wywo­du – posłu­gi­wać się licz­bą kra­tek jako jed­nost­ką miary.
³ Defi­ni­cja cią­gu Ula­ma jest defi­ni­cją reku­ren­cyj­ną. W języ­ku angiel­skim brzmia­ła tak:
Sup­po­se we defi­ne a sequ­en­ce of inte­gers as fol­lows: star­ting with inte­gers 1, 2 we con­struct new ones in sequ­en­ce by con­si­de­ring sums of two pre­vio­usly defi­ned inte­gers but not inc­lu­ding in our col­lec­tion tho­se inte­gers which can be obta­ined as a sum of pre­viu­os ones in more than one way. We never add an inte­ger to itself.
S. Ulam, On some mathe­ma­ti­cal pro­blems con­nec­ted with pat­terns of growth of figu­res, pp. 215–224 of R. E. Bel­l­man, ed., Mathe­ma­ti­cal Pro­blems in the Bio­lo­gi­cal Scien­ces, Proc. Sym­pos. Applied Math., Vol. 14, Amer. Math. Soc., 1962.
W lite­ra­tu­rze na temat ana­li­zy gieł­do­wej uży­wa się bar­dziej ogól­nej defi­ni­cji liczb Ula­ma.^10
4 Moż­na wyka­zać, że pro­ce­du­rę two­rze­nia kolej­nych liczb Ula­ma moż­na powta­rzać bez koń­ca. To ozna­cza, że ciąg Ula­ma jest cią­giem nie­skoń­czo­nym, o czym krót­ko w zapi­sie infor­mu­je wie­lo­kro­pek zapi­sy­wa­ny na koń­cu, po ostat­niej licz­bie Ula­ma zapi­sa­nej jaw­nie: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, ….
⁵ Por. A. Ste­pa­nov, D. Rose, Od mate­ma­ty­ki do pro­gra­mo­wa­nia uogól­nio­ne­go. Gli­wi­ce 2015, s. 22.
W defi­ni­cji łań­cu­cha doda­wań przyj­mu­je się, że pierw­sze doda­wa­nie to 1 + 1 słu­żą­ce ^{obli­cze­niu 2.
6} https://19m40s.bandcamp.com/track/ulam-numbers
⁷ Licz­ba 48 jest rów­nież licz­bą Ulama.
⁸ Moż­na tam zna­leźć narzę­dzie do zilu­stro­wa­nia cią­gu (jako funk­cji liczb natu­ral­nych) na wykre­sie. Może­my zorien­to­wać się, na przy­kład, że na 200. pozy­cji w cią­gu Ula­ma jest licz­ba mniej­sza niż 2000.
⁹ Nie zna­my, na przy­kład, odpo­wie­dzi na pyta­nie, czy oprócz liczb 3 (=1+2) i 131 (=62+69) są inne licz­by Ula­ma, któ­re są suma­mi kolej­nych dwóch liczb z cią­gu Ulama.
¹⁰ Oddaj­my głos Mar­ko­wi Kaco­wi (1914–1984), mate­ma­ty­ko­wi, któ­ry w jed­nym z wywia­dów mówił: „[S. Ulam] przy­szedł raz i powie­dział: »Popatrz, wymy­śli­łem nastę­pu­ją­cą mody­fi­ka­cję liczb Fibo­nac­cie­go. (…)« Według pomy­słu Sta­na [Ula­ma], wzór na a_n+1 był­by teraz: a_n+1 = a_n + któ­ryś z a₁, a₂, … , a_n−1 wzię­ty z praw­do­po­do­bień­stwem 1/n.” Dalej M. Kac wspo­mi­nał: „Mój Boże, to jest cie­ka­we jako roz­mo­wa przy kawie, ale z jakie­goś dziw­ne­go powo­du to mnie tak wzię­ło, że zaczą­łem nad tym pra­co­wać. Zna­la­złem nawet śred­nie an i nawet warian­cję. (…). Spę­dzi­łem nad tym praw­do­po­dob­nie naj­mniej tydzień cięż­kiej pra­cy. Dla­cze­go? Nie mam poję­cia, poza tym, że nie mogłem zosta­wić w spo­ko­ju tej prze­klę­tej rzeczy.”
Źró­dło: Reflek­sje pol­skich mistrzów, Wia­do­mo­ści Mate­ma­tycz­ne, XXX.1, 1993, s. 113.