Morse-csüd sorozat
A Morse-Thue sorozat nullák és egyesek ( bitek ) végtelen sorozata , amelyet először 1906 -ban Axel Thue norvég matematikus javasolt egy időszakos, rekurzívan kiszámítható karakterlánc példájaként.[ adja meg ] . A sorozatnak két változata létezik, amelyeket bitinverzióval kapunk meg:
10010110011010010110100110010110 … ( OEIS sorozat A010059 ) - opcionális 01101001100101101001011001101001… ( A010060 sorozat az OEIS -ben ) - főA Morse-Thue sorozat a fraktálok legegyszerűbb példája, és a fraktál képtömörítési algoritmusokban használatos .
Definíciók
Egy sorozatot többféleképpen is definiálhatunk:
- Az átalakítás végrehajtása ; , az első iterációhoz :
- 1-től indulunk. Minden lépésben hozzáadjuk ennek a számnak az inverzét a számhoz. Az inverziót úgy kapjuk meg, hogy az összes nullát egyesekkel, az egyeseket pedig nullákkal helyettesítjük. Például az 1001-es szám inverze a 0110 lesz. (Más módon a szám megfordítása a következőképpen írható le: ez egy olyan szám, amely a már leírtakat kiegészíti egy olyan számmal, amely csak egyesekből áll; például 1001+0110=1111 kettes számrendszerben)
- Írjuk a kettes rendszerbe egy sorba a 0,1,2,3... számokat, és számoljuk meg az egyes számok 1-es számjegyeit. (Az OEIS - ben az A000120 sorozatot kapjuk .) Ezután ennek a számnak a maradékát vesszük, ha elosztjuk 2-vel.
| decimális jelöléssel | binárisan | egységek száma | egységek száma mod 2 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| egy | 01 | egy | egy |
| 2 | tíz | egy | egy |
| 3 | tizenegy | 2 | 0 |
| négy | 100 | egy | egy |
| 5 | 101 | 2 | 0 |
| 6 | 110 | 2 | 0 |
| 7 | 111 | 3 | egy |
Történelem
A sorozatot 1851-ben fedezte fel Prouhet ( fr. E. Prouhet ), aki megtalálta alkalmazását a számelméletben, de nem írta le a sorozat kivételes tulajdonságait. Axel Thue pedig csak 1906-ban fedezte fel újra a kombinatorika tanulmányozása közben.
Thue munkájának németországi publikálása nyomtalanul telt el, és Marson Morse 1921-ben újra felfedezte a sorozatot , alkalmazva a differenciálgeometriában.
A sorozatot sokszor egymástól függetlenül fedezték fel: Max Euwe nagymester például felfedezte annak alkalmazását a sakkban, megmutatva, hogyan lehet a végtelenségig játszani anélkül, hogy megszegnék a döntetlen szabályait.
Tulajdonságok
Szimmetriák
Mint minden fraktálnak , a Morse-Thue sorozatnak is számos szimmetriája van. Tehát a sorrend ugyanaz marad:
- Ha minden elemet egyenletes helyeken távolít el:
- Két olyan rész cseréjekor, amelyekből egy egészet alkothat, másik két karakterrel. Ez azt jelenti, hogy a sorozat nem archiválható a Huffman algoritmussal , mivel az "archívum" sorozat egybeesik magával a Morse-Thue sorozattal:
Egyéb tulajdonságok
- A sorozat soha nem tartalmaz három azonos, egymást követő részt (lehetetlen az " AAA" teljesítése , ahol " A" - nullák és egyesek sorozatai);
- A sorozat diszkrét Fourier -transzformációja ugyanazokkal a maximumokkal rendelkezik ⅓ és ⅔ frekvenciákon;
- Azt a számot, amelynek bináris reprezentációja a Morse-Csú szekvencia, Prue-Thue-Morse számnak nevezzük:
hol vannak a Morse-Thue sorozat elemei. Ez a szám transzcendentális ( 1929 -ben K. Mahler bizonyította ).
Változatok és általánosítások
Általánosítás tetszőleges ábécére
Adott egy tetszőleges n karakterből álló ábécé , ennek az ábécének pontosan n különböző ciklikus permutációja hozható létre. Ezután az ábécé minden egyes "betűjét" a megfelelő permutációra cserélve Morse-Thue sorozatot kaphatunk. Így például három ciklikus permutáció készíthető három „1”, „2”, „3” karakterből: „123”, „231”, „312”:
egy 1 2 3 1 2 3 2 3 1 3 1 2 1 2 3 2 3 1 3 1 2 2 3 1 3 1 2 1 2 3 3 1 2 1 2 3 2 3 1...
Többdimenziós általánosítás
A többdimenziós Morse-Thue sorozatot hasonló módon határozzuk meg. Például egy kétdimenziós sorozat (mátrix) egy olyan sorozat határa, amelynek minden következő tagja a transzformáció segítségével az előzőből származik.
;
Ezenkívül a kétdimenziós Morse-Thue sorozat egydimenziós sorozatként is ábrázolható.
Linkek
- Weisstein, Eric W. Morse – Csütörtök szekvencia a Wolfram MathWorldnél .