Gijsvijts ketma-ketligi - Gijswijts sequence - Wikipedia

Yilda matematika, Gijsvijtning ketma-ketligi (nomi bilan Dion Gijsvayt tomonidan Nil Sloan^[1]) a o'z-o'zini ta'riflash ketma-ketlik bu erda har bir atama ushbu muddat oldidan ketma-ketlikdagi takrorlangan raqamlarning maksimal sonini hisoblaydi.

Ketma-ketlik bilan boshlanadi:

1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, ... (ketma-ketlik A090822 ichida OEIS )

Ushbu ketma-ketlik ta'rifi bo'yicha o'xshashdir Kolakoski ketma-ketligi, lekin bitta terminlarning eng uzun muddatini hisoblash o'rniga, ketma-ketlik har qanday uzunlikdagi atamalar bloklarining eng uzun muddatini hisoblaydi. Gijsvijtning ketma-ketligi juda sekin o'sish sur'ati bilan tanilgan. Masalan, birinchi 4-chi 220-davrda, birinchi 5-chi yaqinda paydo bo'ladi ${ displaystyle 10 ^ {10 ^ {23}}}$ uchinchi muddat.^[1]

Ta'rif

Ketma-ketlikdagi atamalarni yaratish jarayoni ketma-ketlikni harflar qatori sifatida ko'rib chiqish orqali aniqlanishi mumkin alifbo ning natural sonlar:

${ displaystyle a (1) = 1}$ va
${ displaystyle a (n + 1) = k}$ , qayerda ${ displaystyle k}$ so'zining eng katta tabiiy sonidir ${ displaystyle a (1) a (2) a (3) ... a (n)}$ shaklida yozilishi mumkin ${ displaystyle xy ^ {k}}$ ba'zi so'zlar uchun ${ displaystyle x}$ va ${ displaystyle y}$ , bilan ${ displaystyle y}$ nolga teng bo'lmagan uzunlikka ega.

Ketma-ketlik tayanch - diagnostik. Ya'ni, agar takrorlangan 10 ta blok topilgan bo'lsa, ketma-ketlikning keyingi atamasi bitta emas, balki undan keyin 0 ga teng bo'lgan bitta 10 raqami bo'ladi.

Izoh

Ketma-ketlik ta'rifi bo'yicha 1 bilan boshlanadi. Ikkinchi davrdagi 1, keyin birinchi davrda oldin topilgan 1 sonli blokning 1 uzunligini anglatadi. Uchinchi davrdagi 2 birinchi va ikkinchi davrda joylashgan 1 lar blokining 2 uzunligini anglatadi. Shu nuqtada ketma-ketlik birinchi marta pasayadi: to'rtinchi davrda 1-son, 3-chorakdagi 2 sonli blokning 1 uzunligini, shuningdek, ikkinchi va "1, 2" blokning 1 uzunligini anglatadi. uchinchi muddat. To'rtinchi haddan oldingi uzunlikdan uzunroq bo'lgan biron bir takrorlangan ketma-ketlik bloki yo'q. Birinchi va ikkinchi davrdagi ikkita 1 ning bloki 4-davr uchun ko'rib chiqilishi mumkin emas, chunki ular uchinchi davrda boshqa raqam bilan ajratilgan .

Beshinchi davrda 1 "takrorlanadigan" bloklarning "1" va "2, 1" va "1, 2, 1" va "1, 1, 2, 1" ning beshinchi muddatidan oldin 1 uzunligini anglatadi. Ushbu bloklarning hech biri bir necha marotaba takrorlanmagan, shuning uchun beshinchi had 1 dir. Oltinchi davrdagi 2-son darhol oltinchi davrga, ya'ni 4 va 5-davrlarga to'g'ri keladigan 1s takrorlangan blok uzunligini anglatadi. Ettinchi davrda 2, 1-3 va keyin 4-6 atamalarni qamrab olgan "1, 1, 2" blokning 2 ta takrorlanishini anglatadi. Ushbu "3 raqamli so'z" ettinchi davrga qadar darhol ikki marta uchraydi - shuning uchun ettinchi hadning qiymati 2 ga teng.

Sakkizinchi muddatdagi 2 sakkizinchi davrga, ya'ni oltinchi va ettinchi davrdagi ikkitaga zudlik bilan olib boriladigan takrorlangan 2s blok uzunligini anglatadi. 9-chi davrdagi 3-chi, darhol 9-chi davrga etaklaydigan bitta 2 sonli uch marta takrorlangan blokni, ya'ni oltinchi, ettinchi va sakkizinchi davrlardagi ikkitani anglatadi.

Xususiyatlari

Faqatgina cheklangan tadqiqotlar Gijsvijt ketma-ketligiga qaratilgan. Shunday qilib, ketma-ketlik haqida juda oz narsa isbotlangan va ko'plab ochiq savollar hal qilinmagan.

O'sish darajasi

5 atrofida paydo bo'lmasligini hisobga olsak ${ displaystyle 10 ^ {10 ^ {23}}}$ , qo'pol kuch qidirish texnikasi hech qachon atamaning birinchi marta paydo bo'lishini 4 dan katta topa olmaydi. Ammo, ketma-ketlik har bir tabiiy sonni o'z ichiga olishi isbotlangan.^[2] O'sishning aniq darajasi ma'lum emas, lekin o'sish uchun taxmin qilinadi super-logaritmik tarzda, har qanday tabiiy birinchi paydo bo'lishi bilan ${ displaystyle n}$ yaqin joylashgan ${ displaystyle 2 ^ {2 ^ {3 ^ {4 ^ {5 ^ {. ^ {. ^ {. {n-1}}}}}}}}}}$ .^[3]

O'rtacha qiymat

Har bir tabiiy son ketma-ketlik ichida cheklangan holatda sodir bo'lishi ma'lum bo'lsa-da, ketma-ketlik chekli bo'lishi mumkin deb taxmin qilingan anglatadi. Shartlarni qayta tartibga solish muhim bo'lishi mumkin bo'lgan cheksiz ketma-ketlikda buni rasmiy ravishda aniqlash uchun taxmin quyidagicha:

{ displaystyle lim _ {n to infty} { frac {1} {n}} sum _ {i = 1} ^ {n} a (i) < infty}

Xuddi shunday, zichlik ketma-ketlikdagi har qanday tabiiy sonning ma'lum emas.^[1]

Rekursiv tuzilish

Ketma-ketlikni diskret "blok" va "yopishtiruvchi" ketma-ketliklarga ajratish mumkin, bu ketma-ketlikni rekursiv ravishda yaratish uchun ishlatilishi mumkin. Masalan, tayanch darajasida biz aniqlay olamiz ${ displaystyle B_ {1} = 1}$ va ${ displaystyle S_ {1} = 2}$ navbati bilan birinchi blok va elim ketma-ketligi sifatida. Birgalikda, ular qanday qilib ketma-ketlikning boshlanishini tashkil etishini ko'rishimiz mumkin:

{ displaystyle B_ {1} B_ {1} S_ {1} = 1,1,2}

Keyingi qadam ketma-ketlikni rekursiv ravishda yaratishdir. Aniqlang ${ displaystyle B_ {2} = B_ {1} B_ {1} S_ {1}}$ . Ketma-ketlik bilan boshlanganligini ta'kidlash ${ displaystyle B_ {1} B_ {1}}$ , biz elim ipini aniqlashimiz mumkin ${ displaystyle S_ {2} = 2,2,3}$ beradi:

{ displaystyle B_ {2} B_ {2} S_ {2} = 1,1,2,1,1,2,2,2,3}

Biz tayinladik ${ displaystyle S_ {2}}$ xususiyatini beradigan ma'lum bir ketma-ketlikka ${ displaystyle B_ {2} B_ {2} S_ {2} B_ {2} B_ {2} S_ {2}}$ ketma-ketlikning yuqori qismida ham uchraydi.

Ushbu jarayonni muddatsiz davom ettirish mumkin ${ displaystyle B_ {n + 1} = B_ {n} B_ {n} S_ {n}}$ . Ma'lum bo'lishicha, biz elim ipini kashf qilishimiz mumkin ${ displaystyle S_ {n}}$ buni ta'kidlab ${ displaystyle S_ {n}}$ hech qachon 1 ga ega bo'lmaydi va u birinchi 1-ga erishgandan so'ng to'xtaydi ${ displaystyle B_ {n} B_ {n}}$ .^[3] Shuningdek, Gijsvijtning ketma-ketligi shu tarzda abadiy tuzilishi mumkinligi isbotlangan - ya'ni ${ displaystyle B_ {n}}$ va ${ displaystyle S_ {n}}$ har qanday kishi uchun har doim cheklangan ${ displaystyle n}$ .^[2]

Ushbu rekursiv tuzilishdagi yopishtiruvchi ketma-ketliklarni mohirlik bilan manipulyatsiya qilish Gijsvijt ketma-ketligi ketma-ketlikning boshqa xususiyatlari qatorida barcha tabiiy sonlarni o'z ichiga olganligini namoyish qilish uchun ishlatilishi mumkin.

Shuningdek qarang

Adabiyotlar

^ ^a ^b ^v Sloan, N. J. A. (tahrir). "A090822 ketma-ketligi (Gijsvijtning ketma-ketligi: a (1) = 1; n> 1 uchun a (n) = eng katta butun k, chunki a (1) a (2) ... a (n-1)" so'zi x va y so'zlari uchun xy ^ k shakli (bu erda y ijobiy uzunlikka ega), ya'ni ketma-ketlikning oxiriga qadar takrorlanadigan bloklarning maksimal soni) ". The Butun sonlar ketma-ketligining on-layn ensiklopediyasi. OEIS Foundation.
^ ^a ^b Gijsvijt, DC (2006). "G'ayritabiiy takrorlanish bilan belgilanadigan sekin o'sib boruvchi ketma-ketlik". arXiv:matematik / 0602498.
^ ^a ^b Sloan, Nil. "Ettita hayratlanarli ketma-ketlik" (PDF). AT & T Shannon laboratoriyasi. p. 3.

Tashqi havolalar

Dastlabki 50 million shart
OEIS ketma-ketlik A091579 (A090822 bilan bog'liq bo'lgan qo'shimchalar bloklarining uzunligi) - (yopishtiruvchi ketma-ketliklarning uzunligi)

OEIS ketma-ketlik A090822 (Gijsvijt ketma-ketligi)

[OEIS-1] v Sloan, N. J. A. (tahrir). "A090822 ketma-ketligi (Gijsvijtning ketma-ketligi: a (1) = 1; n> 1 uchun a (n) = eng katta butun k, chunki a (1) a (2) ... a (n-1)" so'zi x va y so'zlari uchun xy ^ k shakli (bu erda y ijobiy uzunlikka ega), ya'ni ketma-ketlikning oxiriga qadar takrorlanadigan bloklarning maksimal soni) ". The Butun sonlar ketma-ketligining on-layn ensiklopediyasi. OEIS Foundation.

[arx-2] Gijsvijt, DC (2006). "G'ayritabiiy takrorlanish bilan belgilanadigan sekin o'sib boruvchi ketma-ketlik". arXiv:matematik / 0602498.

[sloane-3] Sloan, Nil. "Ettita hayratlanarli ketma-ketlik" (PDF). AT & T Shannon laboratoriyasi. p. 3.

[1]

[2]

[3]