Nedir bu (3n + 1) problemi?

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.

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)²(n + c) - c, ...} dizisi oluşturulur; burada dizinin diğer her elemanı (3/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:

• 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)ⁱ'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.

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: S₀ = N ve S_i = (S_{i - 1})/2 eğer S_{i - 1} çiftse... Bu, 3n + 1 dizisinin matematiksel literatürde genellikle nasıl tanımlandığı şeklidir ve bu, diziyi tanımlamanın "doğal" yoludur. S₀'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 = (X_a - cZ)/Y

Burada:

• a dizinin sonraki öğesidir,
• X, doğal bir sayı olup 2'nin bir kuvvetidir (X = 2^l 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 = 3^m 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 = 223₃ + 233₂ + 253₁ + 263₀ = 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.

​