Nedir bu (3n + 1) problemi?

Collatz Conjecture

5dk
Nedir bu (3n + 1) problemi?
  • Blog Yazısı

3n + 1 problemi, ilk kez Collatz tarafından 1937'de ortaya atılmıştır. Bu problemde, başlangıçta bir doğal sayı "n" ile bir dizi oluşturulur. Dizinin bir sonraki doğal sayısını oluşturma kuralı şu şekildedir: Eğer "n" çiftse, dizideki bir sonraki sayı n/2 olur; eğer "n" tekse, dizideki bir sonraki sayı 3n + 1 olur. Örneğin, başlangıç değeri "n = 17" olduğunda, oluşturulan dizi şu şekilde olur: {17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...} Eğer dizide 4 sayısıyla karşılaşırsak, dizi tekrar etmeye başlar ({4, 2, 1} sürekli olarak döngüde kalır).

Bu durumda üç olasılık vardır:

  1. Dizide 4 sayısıyla karşılaşırız,
  2. Dizi tekrar etmeye başlar ancak {4, 2, 1} döngüsünden farklı bir döngü oluşur,
  3. Dizi tekrar etmez (bu durumda dizideki doğal sayılar giderek büyümeye devam eder).

3n + 1 varsayımı, yalnızca birinci olasılığın gerçekleşebileceğini öne sürer. Daha genel bir durumda, c - 1 veya daha büyük ve 3'e bölünmeyen bir tek sayı olarak alındığında, 3n + c dizisinde bir sonraki sayı, n tekse 3n + c, çiftse n/2 olarak tanımlanır (yani dizinin bir sonraki sayısı her zaman bir doğal sayıdır). Bu dizide, c > -1 için {4c, 2c, c} döngüsü, c = -1 için ise {2, 1} döngüsü tekrar eder. Daha genel durumda, genellikle {4c, 2c, c} dışında başka döngüler de bulunur. 3n + 1 ve 3n -1 dizileri bazı benzersiz özelliklere sahip olsa da, 3n + c problemi, tüm c değerleri için temelde aynıdır. Her ne kadar 3n + 1 problemi "eğlenceli" matematik olarak sınıflandırılabilir gibi görünse de, bu konu hakkında önemli bir ana akım matematik literatürü bulunmaktadır.

Tüm Reklamları Kapat

3n + 1 Dizisinin Sınırlı Olduğuna Dair Olasılık

Olasılık, Collatz grafiğinin yeniden yapılandırılmasını ve 3n + 1 dizisinin alternatif bir tanımını içerir. Collatz grafiği, farklı başlangıç "n" değerlerinden başlayarak 1 dizisinin elemanına nasıl ulaşıldığını gösteren ağaç benzeri bir yapıdır. Elbette, bu grafik ancak 3n + 1 varsayımı doğru kabul edilirse inşa edilebilir. Eğer "n" çiftse ve "n - 1" 3'e bölünebiliyorsa, grafikte, dizinin önceki elemanları 2n ve (n - 1)/3 olan bir düğüm bulunur. Örneğin, Collatz grafiğinde 32 ve 5 ile biten iki dal, 16'dan başlayan bir dala bağlanır. Yeniden yapılandırılmış Collatz grafiğinde, 5 ve 16 ile başlayan dal segmentinin devamı olarak kabul edilir. Yeniden yapılandırılmış Collatz grafiğindeki dallar şu şekilde olur:

  • {4, 2, 1}
  • {..., 24, 12, 6, 3, 10, 5, 16, 8}
  • {..., 72, 36, 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20}
  • {..., 120, 60, 30, 15, 46, 23, 70, 35, 106, 53, 160, 80}
  • {..., 168, 84, 42, 21, 64, 32}
  • ve devam eder...

Bu yapı, 3n + 1 dizisinin gelişimini ve dalın nasıl birbirine bağlandığını gösterir. Bu yeniden yapılandırılma, dizinin olasılıksal davranışını incelemeye yardımcı olur.

Her {4, 2, 1} dışında kalan dal, tam olarak bir tane 3'e bölünebilen tek sayıya sahiptir. Burada, 3'e bölünebilen bu tek doğal sayıyı "j" olarak tanımlayalım. "j"nin sağındaki doğal sayılar, 3'e bölünemez (çünkü 3, 3j + 1, (3j + 1)/2, vb. sayılara bölünemez). j'nin solundaki doğal sayılar ise 2i.j formunda olmalıdır; burada "i" doğal bir sayıdır (bu kısma ait herhangi bir doğal sayı yoktur çünkü 3, 2j - 1, 4j - 1, 8j - 1, vb. sayılara bölünemez). Yukarıda listelenen dallar (ikinci daldan başlayarak) sırasıyla 3, 9, 15 ve 21 içerir. İkinci dal, ilk dala bağlanır; üçüncü ve beşinci dallar, ikinci dala bağlanır; ve dördüncü dal, üçüncü dala bağlanır. Diğer önemli gözlem, {4, 2, 1} dışındaki her dalda, daldaki sondan bir önceki elemanın 8'e bölünebilir olmasıdır. Ayrıca, 3'e bölünebilen tek sayının sağındaki ve sondan bir önceki sayıya kadar olan sayılar 8'e bölünemez. Bu, "1-2 dizisi vektörü" olarak bilinir, çünkü ardışık tek sayı elemanları arasındaki çift sayı elemanları ya bir ya da iki tanedir.

3n + c dizisi, [(3/2)h(n + c) - c ]/2 → n, 2h'nin n + c'yi böldüğü, 2h + 1'in n + c'yi bölmediği tekrarlama işlemiyle tanımlanabilir. Tek bir öğe ile başlanan her bir tekrarlama işlemi bir "atlama" olarak adlandırılacaktır. Eğer n tekse ve 22, n + c'yi bölemiyorsa, {n, 3n + c, (3n + c)/2 = (3/2)(n + c) - c, ...} dizisi oluşturulur; burada dizinin diğer elemanı (3/2)(n + c) - c'ye kadar tek olur. Benzer şekilde, eğer n tekse ve 22, n + c'yi bölerse, fakat 23 n + c'yi bölmüyorsa, {n, 3n + c, (3n + c)/2, 3[(3n + c)/2] + c, [(3[(3n + c)/2] + c)/2] = (3/2)2(n + c) - c, ...} dizisi oluşturulur; burada dizinin diğer her elemanı (3/2)2(n + c) - c'ye kadar tek olur. Genel olarak, eğer 2h, n + c'yi bölerse ve 2h + 1, n + c'yi bölmezse, dizideki ilk 4'e bölünebilen eleman, (3/2)h(n+ c) - c'den hemen önce olacaktır. Eğer [(3/2)h(n + c) - c]/2 çiftse, dizideki ilk 8'e bölünebilen eleman bulunmuş demektir. Yeniden yapılandırılmış Collatz grafiğindeki her dal, {4, 2, 1} dışındaki her dal, bir dizi atlamadan oluşur; son atlama çift bir doğal sayıya ulaşır ve bu sayı dalı ağacın geri kalan kısmına bağlar. 3n + 1 dizisinin (veya 3n + c dizisinin) sınırlı olup olmadığı sorusu, bir atlamanın çift bir doğal sayıya ulaşıp ulaşmadığı sorusuna indirgenir. 3, 9, 15, ..., 5999997 ile başlayan 1000000 dizisi için atlamaların dağılımı şu şekildedir:

Tüm Reklamları Kapat
  • i = 1: 500,002
  • i = 2: 250,004
  • i = 3: 124,998
  • i = 4: 62,498
  • i = 5: 31,211
  • i = 6: 15,683
  • i = 7: 7,782
  • i = 8: 3,897
  • i = 9: 2,000
  • i = 10: 972
  • i = 11: 497
  • i = 12: 230
  • i = 13: 109
  • i = 14: 58
  • i = 15: 23
  • i = 16: 13
  • i = 17: 15
  • i = 18: 3
  • i = 19: 3
  • i = 20: 0
  • i = 21: 1
  • i = 22: 0
  • i = 23: 0
  • i = 24: 1

Şimdi ise, 3n + 1 dizisinin, belirli bir sayıda atlama gerektiren olasılıkları ve bununla ilgili bazı matematiksel gözlemleri ele alalım. İlk olarak, "i" iterasyonunun gerekli olma olasılığı yaklaşık olarak (1/2)i'ye eşittir. Yani, her bir artış için olasılık yarıya düşer. Bu, 3n + 1 dizisinin sınırsız olup olmaması olasılığının neredeyse sıfır olduğu anlamına gelir, ancak bunun kanıtlanmasının pek olası olmadığını belirtelim. Veriler, 3n + 1 dizilerini oluşturan süreçlerin (1-2 dizisi vektörlerine sahip) rastgele olduğunu gösteriyor. Matematiksel literatürde bu tür süreçler genellikle "pseudo-rastgele" olarak adlandırılır, ancak "rastgele" kelimesinin kesin bir tanımı olmadığından, bu tür bir sürecin rastgele olduğunu söylemek kabul edilebilir. Probabilistik açıdan, h = 1 olma olasılığı yaklaşık 1/2, h = 2 olma olasılığı yaklaşık 1/4, h = 3 olma olasılığı ise yaklaşık 1/8'dir. Bu, beklenen olasılıklardır. Ancak, bu tür bir dal (1-2 dizisi vektörüyle başlayan ve 3'e bölünebilen bir tek doğal sayı içeren) başka bir dala bağlansa ve o dal da bir başkasına bağlansa bile, {4, 2, 1} dalının başına ulaşılacağının bir garantisi yoktur. Bu durumda, 3n + 1 dizisi sınırsız olabilir. Verilere göre, bir dala bağlı olan 3'e bölünebilen tek doğal sayı, bu dalda bulunan 3'e bölünebilen tek doğal sayıdan daha büyük olma eğilimindedir. Bu, yaklaşık olarak %90 oranında gerçekleşir. İlk 10, 100, 1000, 10000, 100000, 1000000 ve 10000000 tek doğal sayı için oranlar sırasıyla 0.9, 0.91, 0.905, 0.9022, 0.90333, 0.903506 ve 0.903254'tür. Yani, bu tür dalların sonunda {4, 2, 1} dalına bağlanma eğilimi oldukça güçlüdür. Eğer c = 1 ve negatif n değerlerine izin verilirse, 3'e bölünebilen tek sayının mutlak değeri, ona bağlı olan dalda bulunan 3'e bölünebilen tek sayının mutlak değerinden %90 oranında daha büyük olacaktır. Eğer c > 1 ve negatif n değerlerine izin verilirse, aynı olasılıklar geçerlidir. Örneğin, c = 5 için, t'nin 3'e bölünebilen tek sayı olduğu durumda, -10k ≤ (t - 3)/6 ≤ 10k ve k = 1, 2, 3, ..., 7 için oranlar sırasıyla şunlardır: 0.941176, 0.913043, 0.906933, 0.903944, 0.903457, 0.903540, 0.903280. Bu oranlar, sayıların dağılımını gösteren histogramlarla temsil edilebilir.

c = 1 ve k = 4 için, t değerlerinin mutlak değerlerindeki farkların 1536'ya bölünmesiyle elde edilen histogram;
c = 1 ve k = 4 için, t değerlerinin mutlak değerlerindeki farkların 1536'ya bölünmesiyle elde edilen histogram;
5'e bölünebilen t değerleri hariç tutulduğundan c = 5 için daha az değer vardır.  Genel olarak, 8/9 bu oranların alt sınırı gibi görünmektedir.
5'e bölünebilen t değerleri hariç tutulduğundan c = 5 için daha az değer vardır.
Genel olarak, 8/9 bu oranların alt sınırı gibi görünmektedir.

1972 yılında John H. Conway, 3n + 1 problemine benzer daha genel bir fonksiyon iterasyon problemi ortaya koyarak bunun hesaplanabilirlik açısından çözülmesi mümkün olmayan bir sorun olduğunu göstermiştir. Bu, 3n + 1 probleminin en azından bu kısmının kanıtlanamayacağına dair inancı güçlendirmektedir. Ancak bu alanda bazı ilerlemeler kaydedilmiştir; 1976'da Riho Terras, neredeyse tüm sayıların sonlu "durdurma zamanı"na sahip olduğunu göstermiştir. Şu şekilde tanımlanır: S0 = N ve Si = (Si - 1)/2 eğer Si - 1 çiftse... Bu, 3n + 1 dizisinin matematiksel literatürde genellikle nasıl tanımlandığı şeklidir ve bu, diziyi tanımlamanın "doğal" yoludur. S0'dan küçük olan ilk "i" değeri, N sayısının durdurma zamanı olarak tanımlanır.

3n + c Dizisindeki Döngülerin Varlığı İçin Gerekli Koşullar

Bir s değeri için, 3n + c dizisinde şöyle ifade edilebilir: s = (Xa - cZ)/Y

Burada:

  • a dizinin sonraki öğesidir,
  • X, doğal bir sayı olup 2'nin bir kuvvetidir (X = 2l burada "l" dizinin uzunluğudur; yani, tek bir öğenin ardından gelen öğe (3i + c)/2 olarak tanımlanır.)
  • Y, doğal bir sayı olup 3'ün bir kuvvetidir (Y = 3m burada "m" dizideki tek öğelerin sayısını belirtir),
  • Z, doğal bir sayı olup 3-adik bir sayıdır ve 2'nin kuvvetleriyle çarpanları vardır.

Örneğin, Z şöyle olabilir: Z = 2233 + 2332 + 2531 + 2630 = 340

Eğer s = a ise, o zaman: s = (cZ)/X - Y

Bunun dışında, cZ/(X - Y) bir tam sayı olduğunda X, Y, Z'yi bulmak için bilinen bir yöntem yoktur. Bu nedenle döngüler için diğer gereksinimler araştırılmaya devam ediyor.

Rastgele Yazıya Git
4
Alt Başlıklar
Bu Blog Yazısı Sana Ne Hissettirdi?
  • Muhteşem!
    Muhteşem!
    0
  • Tebrikler!
    Tebrikler!
    0
  • Bilim Budur!
    Bilim Budur!
    0
  • Mmm... Çok sapyoseksüel!
    Mmm... Çok sapyoseksüel!
    0
  • Güldürdü
    Güldürdü
    0
  • İnanılmaz
    İnanılmaz
    0
  • Umut Verici!
    Umut Verici!
    0
  • Merak Uyandırıcı!
    Merak Uyandırıcı!
    0
  • Üzücü!
    Üzücü!
    0
  • Grrr... *@$#
    Grrr... *@$#
    0
  • İğrenç!
    İğrenç!
    0
  • Korkutucu!
    Korkutucu!
    0

Yorumlar 0

Evrim Ağacı'na her ay sadece 1 kahve ısmarlayarak destek olmak ister misin?

Şu iki siteden biriyle hemen destek olabilirsin:

kreosus.com/evrimagaci | patreon.com/evrimagaci

Çıktı Bilgisi: Bu sayfa, Evrim Ağacı yazdırma aracıyla 20.11.2026 21:29:11 tarihinde oluşturuldu. Evrim Ağacı'ndaki içerikleri birden fazla editör sürekli gözden geçiriyor, güncelliyor ve geliştiriyor. Bu çıktıdan sonraki güncellemeleri görmek ve içeriğin en güncel hâlini okumak için şu adrese git: evrimagaci.org/s/19527

İçerik Kullanım İzinleri: Evrim Ağacı'ndaki yazılı içerikler orijinallerine hiçbir şekilde dokunulmadığı sürece izin alınmaksızın paylaşılabilir, kopyalanabilir, yapıştırılabilir, çoğaltılabilir, basılabilir, dağıtılabilir, yayılabilir, alıntılanabilir. Ancak bu içeriklerin hiçbiri izin alınmaksızın değiştirilemez ve değiştirilmiş hâlleri Evrim Ağacı'na aitmiş gibi sunulamaz. Benzer şekilde, içeriklerin hiçbiri, söz konusu içeriğin açıkça belirtilmiş yazarlarından ve Evrim Ağacı'ndan başkasına aitmiş gibi sunulamaz.

Hemen Paylaş
Bu blog yazısını sevdin mi?
Paylaşarak başkalarına da ilham ol.
Keşfetmeye Devam Et