Sıra sıra sayılar — çözüm

Sıra sıra sayılar” bulmacasına katkıda bulunan, ilgilenen herkese teşekkürler. Doğrusu bu problem benim de başta tahmin ettiğimden daha ilginçmiş. İlgilenenler için teorisine dair bazı notları aşağıda aktarıyorum.

Genel kural şöyle: İlk satırda 1 ile başlarız. Satırda “bir tane 1” vardır, o yüzden ikinci satıra “1 1” yazarız. İkinci satırda “iki tane 1” olduğu için üçüncü satıra “2 1” yazarız. Sonraki satırlar:
“bir 2 bir 1” = “1 2 1 1”
“bir 1 bir 2 iki 1″ = 1 1 1 2 2 1”
“üç 1 iki 2 bir 1” = “3 1 2 2 1 1”
şeklinde gider.

Elbette rastgele bir sayı dizisiyle de başlayıp aynı kuralla evirtebiliriz.

Program

def f(row):
    """Verilen bir satirdan sonraki satiri verir.""" 
    if len(row)==1:
        return "1"+row[0]

    nextrow=""
    i=0
    while i<=len(row)-2:
        counter = 1
        while i<=len(row)-2 and row[i+1]==row[i]:
            counter += 1
            i += 1
        nextrow += str(counter)+row[i]
        i += 1

    if row[-1]!=row[-2]:
        nextrow += "1"+row[-1]

    return nextrow

row="1"
# ilk 10 satiri bas
for i in range(10):
    print "%d\t%s" % (i, row)
    row = f(row)
# 50. satirda kac basamak var?
row="1"
for i in range(50):
    row = f(row)

print "50. satirda %d basamak var." % (len(row))

Meraklısı için

Bu problemi Clifford Pickover’in “Wonders of Numbers” kitabının “Audioactive Decay” başlıklı 55. bölümünden aldım. Wikipedia’da “Bak ve söyle dizisi” olarak tarif ediliyor. “Tamsayı Dizileri Ansiklopedisi” A005150 maddesinde çeşitli bilgiler ve değişik programlama dillerinde yazılmış üreteç programlar mevcut.

Bu problemi J. H. Conway (Hayat Oyunu‘nun mucidi) “The Weird and Wonderful Chemistry of Audioactive Decay” başlıklı çok eğlenceli bir makalede inceledi. Özel bir uzmanlık gerektirmiyor, temel matematik bilmeye bile lüzum yok. Yeni satır oluşturma ile bir süre oynayıp bir sezgi kazandıktan sonra, mantıki adımları takip ederek makaleyi anlayabilirsiniz. Ne yazık ki bu makaleye korsanlık yapmadan ulaşmak kolay değil.

Bu dizinin ilginç bir özelliği, ikinci adımdan sonra 4 ve üstü sayıların asla ortaya çıkmaması. İlk satırda 4 varsa o kalıyor. İlk satırda mesela “1 1 1 1” varsa o “4 1” haline geliyor, ama sonra yeni 4 ortaya çıkmıyor.

[ ] (boş satır) ve [22] oldukları gibi kalırlar. Bunlardan başka her satır gitgide büyür. İlk birkaç satırdan sonra, her satır bir önceki satırdan %30 daha uzun oluyor. Daha iyi bir ifadeyle, t adımındaki uzunluk L_t ise, asimptotik olarak \lim_{t\rightarrow\infty} \frac{L_{t+1}}{L_t} = 1.303577269\ldots (Conway sabiti) bulunuyor.

Bazen bir satır, birbirinden bağımsız şekilde evrilen iki ayrı satıra bölünebiliyor. Sözgelişi
4.1
14.11
1114.21
3114.1211
132114.111221

Aradaki nokta, bağımsız gelişen alt kısımların arasındaki sınırı gösteriyor. Conway’in “Bölünme Teoremi” bunun gerek ve yeter şartlarını sıralıyor.

Conway, bölünemeyen alt kısımlara “element” adını vermiş. Sonsuz sayıda element var, bazıları çok özel başlangıç satırlarında ortaya çıkıyor, bazıları ise hangi satırla başlatırsanız başlatın, bir süre sonra yeni satırların elementleri olarak görülüyorlar. Conway bunların tam 92 tane olduğunu tespit etmiş — doğal olarak bulunan elementlerle aynı sayıda — ve bunlara periyodik tablodaki elementlerin isimlerini vermiş. Bunların tam listesini Conway’in makalesinde görebilirsiniz.

Conway’in “Kimya Teoremi”ne göre, bu elementleri yeterince uzun zaman evirtirsek, bir süre sonra alt birimlerinde bu 92 elementin hepsini aynı anda bir satırda buluruz. Ayrıca, bir elementle değil, herhangi bir satırla başlarsak ([ ] ve [22] hariç), bir zaman sonra 92 “element”in hepsi aynı anda bir satırda bulunur.

Daha da güzeli, “Kozmolojik Teorem”: Nasıl bir satırla başlarsanız başlayın, yeterince zaman geçtikten sonra elinize geçen satır sadece 92 “element”in ve iki tane “özel izotopun” bileşimi olarak ortaya çıkar. (Başlangıçta 4 ve üstü sayılar yoksa “izotop”lara lüzum kalmaz.) Sözgelişi:
1
11
21
1211
111221
312211
13112221
11132.13211 = Hf.Sn
yani “1”in yedinci göbek torunu, birbirinden bağımsız gelişen iki parça olarak ifade edilebilir. Conway’in “Periyodik Tablo”sunda bu parçalar Hafniyum ve Çinko’dur.

Conway’in ifadesiyle Kozmolojik Teorem, Büyük Patlama’dan sonra olağandışı “element”lerin hızlıca “bozunup” doğal elementlerin bileşimine dönüştüğünü ifade eder.

Dâhiler basit bir problemden başlı başına bir evren oluşturabiliyorlar.

Reklamlar

Kaan Öztürk hakkında

Kaan Öztürk İstanbul’da doğdu. İstanbul Lisesi ve Boğaziçi Fizik mezunu. Rice Üniversitesi‘nde uzay fiziği alanında doktora yaptı. Işık ve Yeditepe üniversitelerinde ders verdi. 2015-2016 döneminde Rice'da ziyaretçi araştırmacı olarak çalıştı. Bugünlerde Sabancı Üniversitesi'nde optimizasyon ve yapay öğrenme konularında doktoraüstü araştırmacı olarak çalışıyor.

28 Mart 2012 tarihinde İlginç Şeyler içinde yayınlandı ve , , , , olarak etiketlendi. Kalıcı bağlantıyı yer imlerinize ekleyin. Yorum yapın.

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Connecting to %s

%d blogcu bunu beğendi: