Számautomaták és számsorok

A mai pénzrendszerek kerek aprópénz-címleteket használnak, állapítja meg John D. Barrow amerikai fizikus, vagyis rendszerint 1, 2, 5, 10, 20, 25, 50 (vagy ezek közül néhány) fordulhat elő fizetéskor. És innentől kezdve persze kérdés, hogy milyen egységekből lenne a legkevesebbre szükség ahhoz – illetve felmerülhetnek az egész számok „legenerálhatóságára” vonatkozó kérdések is.
Ami az előbbit illeti, Jeffrey Shallit (Ontario) számítógépes modellezéssel azt mutatta ki, hogy amennyiben csupán 1, 5, 10 és 25 centest használhatunk, akkor 100 centen belül maradva egy adott összeghez átlagosan 4,7-re lesz szükségünk.  Ám 1, 5, 18 és 29 centesekkel a zsebünkben átlagosan 3,89 darab is elég lenne (mint ahogy az 1, 5, 18, 25 centesek esetében is). Kizárólag 1 centesekből viszont – nem különösebben meglepő módon – átlagosan 49,5 kellene.
Ezt a problémát általánosítva kiindulhatnánk azonban abból is, hogy mi lenne, ha a (természetes) számokat egy egyszerű szám „számautomatával” kellene létrehoznunk az alábbi, nem éppen bonyolult szabályok alapján:

• kiindulásként a 0 adott , vagyis az, hogy „nincs semmi”.
• Egy összeadás 1 műveletet jelent; egy szorzás szintén 1-et.
• Egy ciklusban csak egy műveletet végezhetünk.
• Csak olyan számokat használhatunk, melyeket már „létrehoztunk” (tehát ha már legeneráltuk a hármat, akkor azt hozzáadhatjuk egy másik, legenerált számhoz vagy összeszorozhatjuk vele, de ha újra szükségünk lenne rá, akkor nem ránthatjuk csak úgy elő a kalapból).

Például az első lépésben meglévő nullához hozzáadunk 1-et, és mivel egy műveletet már végrehajtottunk, a ciklus véget is ér – viszont van egy darab 1-esünk, úgyhogy a következő körben 0 helyett ezzel indíthatunk, és egy újabb +1-nek köszönhetően az eredmény 2 lehet. Majd pedig ha újból végig csináljuk a procedúrát, akkor eljutunk a fentebb említett 3-hoz.
Ami mindezidáig nem is különbözik olyan nagyon attól, mintha a természetes számokat ábrázoló számegyenesen lépkednénk végig 0-tól 3-ig, és amihez esetünkben három ciklus kellett (röviden: 3c), és innentől kezdve a számokhoz hozzárendelhetjük, hogy minimum hány ciklusból konstruálhatóak meg. Tehát a szorzást (1)-gyel jelölve a számok így építhetőek fel:
1=1c
2=2c
3=3c
4=4c
5=5c
6=6c
7=7c
8=7c (2,4, (1))
9=7c (3,3, (1))
10=8c (2,5, (1))
11=9c (2,5,(1),1)
12=8c (3,4, (1))
13=9c (3,4, (1),1)
14=10c (2,7,(1))
15=9c (3,5, (1))
16= 9c (4,4, (1))
17=10c (4,4, (1), 1)
18=10c (3,6, (1))
19= 11c (3,6, (1), 1)
20=10c (5,4, (1))
21=11c (5,4, (1), 1)
22=12c (3,7, (1), 1)
23= 13c (3,7, (1), 2)
24=11c (6,4, (1))
25=11c (5,5, (1))
26= 12c (5,5, (1), 1)
27= 13c (3,9, (1))
28= 12c (4,7, (1))
29=13c (4,7, (1), 1)
30=12c (5,6, (1))
31=13c (5,6, (1), 1)
32=13c (4,8, (1))
33=14c (4,8, (1), 1)
34=13c (4,8, (1))
35=13c (5,7, (1))
36=13c (6,6, (1))
37=14c (6,6,(1), 1)
.
.
.
100= 21c (10,10, (1))
.
.
.
1000=32c (10,10, (1), 10, (1))
Ami persze ideáig is elég izgalmas, mert innentől kezdve a számokat úgy foghatjuk fel, mint egy számautomata adott állapotát, és azt is megfigyelhetjük, hogy vannak olyan számok, melyeket a legegyszerűbben ismételt összeadással állíthatjuk elő. Ezeknek a „komplexitása” azonos magával a számmal, miként 1,2,3,4,5,6,7 esetében történik. 8-tól a jelek szerint ilyesmi nem fordulhat elő, de a komplexitás viszonylag lassan nő, és akadnak olyan számok is, melyeket kétféleképpen lehet egyformán kevés lépésből legenerálni: ilyen pl. a 6 (egyszerű számlálással, 6 lépésben, vagy 2 és 3 létrehozása után ezek összeszorzása) vagy éppen a 23.
Továbbá eljátszhatunk azzal is, hogy mondjuk a 19 –es szám 13 lépésből állítható elő; a 13 pedig 9 lépésből, míg a 9-es létrehozásához 7 lépés kell, vagyis
19 esetén:
19 – 13 – 9 – 7
az 1000 esetén:
1000 – 32 – 13 –  9 – 7
a 37 esetén:
37 – 17 – 10 – 8- 7
a 28 esetén:
28 – 12 – 8- 7
stb., és erős a gyanúm, hogy vagy a 9 – 7, vagy a 10 – 7 utat befutva mindig a 7-nél ér véget a történet.
Mindent egybevetve megtehetjük, hogy úgy fogjuk fel a számokat, mint egymást (nem feltétlenül egyesével) követő számok sorozatát, amelyek végén eljutunk a kívánt eredményhez. Ekkor többféle lehetőség képzelhető el.
1. Az első megoldás az, ahol véges sok lépésben elérjük a kívánt számot, és közben azt is pontosan meg tudjuk mondani, hogy hány lépés kell ehhez. Erre a legegyszerűbb példa egy olyan számautomata, amely nem képes másra, mint az előző számhoz mindig 1-et hozzáadni: ekkor a 0-tól indulva az 1 pontosan 1, a 137 pontosan 137 lépésre lesz. Ami, valljuk be, nem különösebben fantáziadús.
2. A másik lehetőség a Collatz-sejtés: itt az a szabály, hogy ha a szám páros, akkor oszd el kettővel; ha páratlan, akkor szorozd meg 3-mal és adj hozzá 1-et. Mindeddig bármilyen természetes számot választottak is kiindulásul, véges sok lépésben mindig „lejutott” (sic!) 1-hez; viszont lehetetlen előre megmondani, hogy ez hány lépés múlva fog bekövetkezni (egyelőre egyébként bizonyítani sem sikerült, hogy mindig így történik). Ami azért érdekes a számunkra, mert a Collatz-féle számautomatát visszafelé „üzemeltetve” az 1-től feltehetően bármelyik számhoz eljuthatunk véges sok, de előre megjósolhatatlan számú lépésben.
3. És végül ott van a fentebb részletesen leírt számautomata is, ahol a számegyenesen egyesével való előre araszolás helyett a szorzás is megengedett. Itt is véges sok lépésben jutunk el a célként kitűzött számig, és az első néhány (ld. fentebb) szám kivételével feltehetően mindig van egy rövidebb út az egyesével való összeadogatásnál. A négyzetszámok esetén (a 4 kivételével) a szám gyökének kétszerese + 1 lépésre van szükség; különben azonban nem tűnik úgy a számomra, hogy azon túl, hogy lassan nő a szükséges lépések száma, lenne szabály, amely nem csak hozzávetőlegesen, hanem pontosan előre jelezhetővé teszi a végeredményt.
Vagyis mintegy átmenet a számegyenes unalma meg a fordított Collatz-automata kiszámíthatatlan számú lépést igénylő megoldásai között.