Collatz Conjucture

Yazının orjinali için

The Collatz conjecture is the greatest math trick of all time

On the Internet and in non-fiction literature, you can often find various mathematical tricks: you are asked to think of a number, then perform a series of arithmetic operations with it. After that,...

https://habr.com/en/articles/723830/

İnternette ve kurgusal olmayan literatürde sık sık çeşitli matematiksel hileler bulabilirsiniz: Bir sayı düşünmeniz istenir, ardından onunla bir dizi aritmetik işlem gerçekleştirirsiniz. Bundan sonra, konuşma partneriniz elde ettiğiniz sayıyı doğru bir şekilde tahmin eder. Bu hilelerin çoğu, orijinal sayının dönüşümler sırasında fark edilmeden başka bir sayı ile değiştirilmesi ve ardından birkaç adımda bilinen bir cevaba indirgenmesi gerçeğine dayanır. Örneğin bu tür hileler Yakov Perelman'ın kitaplarında bulunabilir.

Collatz varsayımı tüm bu hileleri geride bırakır. İlk bakışta, bunun da bir tür hileli numara olduğu düşünülebilir. Ancak, daha yakından incelendiğinde, herhangi bir hile olmadığı ortaya çıkmaktadır. Bir sayı düşünürsünüz ve bu sayı için iki aritmetik işlemden birini birkaç kez tekrarlarsınız. Şaşırtıcı bir şekilde, bu işlemlerin sonucu her zaman aynı olacaktır. Ya da her zaman olmayabilir mi? Kimse kesin olarak bilmiyor, ancak şimdiye kadar hiç kimse başka bir şey elde edemedi.

Hadi deneyelim. Herhangi bir pozitif tamsayı düşünün. Sonra basit bir algoritma izleyin:

1- Eğer sayı çift ise, 2'ye bölün.

Aksi takdirde, 3 ile çarpın ve 1 ekleyin.

2- Ortaya çıkan sayı ile 1. adımı tekrarlayın.

Adım 1 ve 2'yi birçok kez tekrarlarsak sonuç olarak ne elde edeceğimizi düşünüyorsunuz?

Alman matematikçi Lothar Kollatz, herhangi bir pozitif tamsayı için er ya da geç önce 4, sonra doğal olarak: 2 ve sonra 1 elde edeceğimize inanıyor. Ve bundan sonra bir daire içinde yürüyeceğiz, tekrar tekrar 4-2-1 zincirini elde edeceğiz. En şaşırtıcı şey ise, hangi sayıyla başlarsak başlayalım böyle bir sonuca ulaşacak olmamızdır.

İnanması zor mu? Bunu doğrulamak zor değil, özellikle de problemin koşulları çok basit olduğu için. Belki de şu anda bu, çözülmemiş bir matematik probleminin en basit formülasyonudur-herkes çarpabilir ve toplayabilir. Adil olmak gerekirse, bazı başlangıç sayıları için saymanın uzun zaman alacağını belirtmek gerekir. Dolayısıyla, bir arkadaş grubunda tahmin yapmak için bu "numara" yalnızca küçük başlangıç sayıları için uygundur.


function* calc(n) {
  while (n > 1) {
    if (n % 2 === 0) {
      n = n / 2;
    } else {
      n = 3 * n + 1;
    }
    yield n;
  }
}

let n = Math.floor(Math.random() * 1000) + 1;
let steps = [n, ...calc(n)];
console.log(`Number: ${steps[0]}. Steps: ${steps.length}. Maximum: ${Math.max(...steps)}.`);
console.log(steps);

Burda python kodunu js’e çevirdim çünkü js <3

Bu hipotezi kendiniz denemekten çekinmeyin. Bu arada, web üzerinde farklı başlangıç verileri için çözümlerin ve adımların dağılımını gösteren birçok ilginç görselleştirme bulabilirsiniz. Ayrıca birçok programlama dili için bu görevi uygulamak için seçenekler içeren bir site de var.

İlginç olan başka ne biliyor musunuz? Kollatz'ın ifadesi boşuna hipotez olarak adlandırılmıyor - şimdiye kadar hiç kimse mantıksal kanıtını ortaya koyamadı. Lothar Kollatz hipotezini 20. yüzyılın 30'lu yıllarında formüle etti ve o zamandan beri bu ifadeyi katı matematiksel mantık kullanarak kanıtlamak veya çürütmek için çok sayıda girişimde bulunuldu. Ancak matematikçilerin başarabildiği tek şey hipotezi deneysel olarak test etmek oldu. Bu problemde, programın çözüm arayışı esasen hesaplama gücü dışında hiçbir şeyle sınırlı değildir. Hipotez çürütülememiş olsa da, büyük başlangıç sayıları için bile algoritma er ya da geç 1'e ulaşmaktadır. Bu sorunu çözmek için gönüllü dağıtık hesaplama projesi bile düzenlenmiştir. Ancak bu klasik matematik için yeterli değildir. Sayılar bazen çok aldatıcıdır. İnanılmaz derecede büyük başlangıç sayıları arasında bir yerlerde, hipotezin doğrulanmadığı böyle bir başlangıç sayısı olabilir.

Bu arada, Collatz varsayımının daha az ünlü birkaç ismi vardır:

3n+1 problemi, tek sayılar için olan adımın bir çeşididir;

hailstone hypothesis : dizi grafikleri bir şekilde atmosferdeki dolu yörüngelerini anımsatmaktadır;

Ulam varsayımı, adını Polonyalı matematikçi Stanislaw Ulam'dan alır;

Kakutani problemi, adını Japon matematikçi Shizuo Kakutani'den alır;

Thwaites varsayımı, adını İngiliz matematikçi Brian Thwaites'ten alır;

adını Alman matematikçi Helmut Hasse'den alan Hasse algoritması;

Syracuse sorunu

Farklı isimlerin sayısına bakılırsa, matematikçilerin bu problemle ciddi bir şekilde ilgilendikleri açıktır. Ancak, bunun formüle edilmesi çok kolay, ancak çözülmesi son derece zor olan "zor" görevlerden biri olduğu ortaya çıktı. Tıpkı Fermat'nın Son Teoremi gibi.

Bu problemdeki sayılar çok garip davranmaktadır: bazı durumlarda hesaplamalar çok hızlı bir şekilde 1'e ulaşmakta, bazen de alt toplam oldukça büyük bir sayıya ulaşmakta ve ardından hızlı bir şekilde birime "inmektedir". Örneğin, başlangıçtaki 27 sayısı için alt toplam 9232'ye ulaşır ve ardından birkaç adımda hızla 1'e iner. Sonuç olarak, 27 için adım sayısı 111'dir. Ve bu, 26 için 10 (maksimum ara sayı 40) ve 28 için: 18 (maksimum ara sayı 52) olmasına rağmen.

Matematikçiler hipotezi mantıksal olarak tam olarak doğrulayamamış veya çürütememiş olsalar da, yine de bir şeyler başardılar. Çoğu zaman olduğu gibi, bilim insanları çözüme kademeli olarak yaklaşıyor. Yakın zamanda, 8 Eylül 2019'da, Kaliforniya Üniversitesi matematikçisi Terence Tao, Collatz varsayımının "neredeyse" tüm sayılar için en azından "neredeyse" doğru olduğunu gösteren bir kanıt yayınladı. Matematikçilerin bu probleme nasıl saldırdığının ve Terence Tao'nun neyi başardığının hikayesi burada ayrıntılı olarak anlatılmaktadır.