Dugaan Collatz

Jika ditulis sebagai pemetaan, aturan dugaan Collatz adalah

Sebuah penerbangan berangkat dari $n$, melalui $f(n)$, $f(f(n))$, dan seterusnya, lalu berakhir saat mencapai 1. Setelah itu, ia hanya akan berputar dalam siklus 1 → 4 → 2 → 1. Dugaan ini menyatakan bahwa setiap bilangan bulat positif akan sampai di sana. Di sini kamu bisa menerbangkan bilangan bulat, bahkan yang panjangnya ratusan digit, sendirian atau dalam kelompok. Kamu bisa membandingkannya dengan argumen kasar yang membuat dugaan ini begitu masuk akal, lalu melihat mengapa argumen itu bukan bukti.

Sumbu mendatar menunjukkan jumlah langkah, sedangkan sumbu tegak menunjukkan nilai dalam skala logaritmik, kecuali jika kamu memilih Langsung untuk memperoleh gambar hujan es yang biasa dikenal. Setiap bilangan dalam kelompok adalah garis berwarna. Jadi, bagian yang dilalui banyak bilangan memiliki warna lebih kuat: lebih terang pada latar gelap, lebih gelap pada latar terang. Bilangan yang sedang dilihat disorot, dengan titik merah pada posisi saat ini. Penerbangan sulit ditebak: 27 naik hingga 9.232 dan membutuhkan 111 langkah untuk mencapai 1, sedangkan 28 membutuhkan 18.

Mengapa dugaan ini dipercaya? Langkah ganjil selalu menghasilkan bilangan genap, jadi gabungkan langkah itu dengan pembagian dua sesudahnya menjadi satu langkah ringkas. Sekarang anggap paritas langkah-langkah ini seperti lemparan koin seimbang yang saling independen. Separuh waktu, $n$ dikalikan kira-kira 3/2, dan separuhnya lagi dikalikan 1/2. Jadi, rata-rata satu langkah ringkas mengubah $\ln n$ sebesar

Bilangan seharusnya lalu menyusut, biasanya menjadi 3/4 dari nilai sebelumnya setiap dua langkah ringkas. Pada sumbu logaritmik, kecenderungan ini ditunjukkan oleh garis putus-putus, yang digambar untuk kelompok Sebesar ini berisi setidaknya 100 bilangan. Garis ini mengabaikan pendaratan: bilangan yang mencapai 1 tetap berada di dasar, sehingga menjelang akhir, tinggi rata-rata kelompok pada sumbu ini turun lebih lambat daripada garis tersebut.

Lemparan koin hanyalah model perilaku rata-rata bilangan. Dugaan ini berlaku untuk setiap bilangan bulat positif: satu saja penerbangan yang tidak pernah mencapai 1 akan membantahnya.

Bilangan negatif menunjukkan apa yang luput dari argumen itu. Aturan yang sama menghasilkan siklus pada bilangan negatif, dan tiga siklus telah diketahui, misalnya −5 → −14 → −7 → −20 → −10 → −5. Model koin juga memprediksi penyusutan di sana, tetapi satu putaran penuh pada siklus mana pun mengubah $\log|n|$ tepat sebesar 0. Kecenderungan turun secara rata-rata tidak dapat meniadakan kemungkinan siklus, termasuk pada bilangan positif.

Karang membalik penerbangan: jika ditumbuhkan mundur dari 1, lintasan satu kelompok membentuk pohon. Setiap sisi berbelok dari sisi sebelumnya sebesar $+\alpha$ jika bilangan baru genap dan $-\alpha \log_2 3$ jika ganjil, dengan α diatur melalui Belokan. Saat menelusuri mundur dari 1, langkah genap menggandakan bilangan dan menaikkan $\log_2$-nya sebesar 1; langkah ganjil menurunkannya sedikit lebih besar daripada $\log_2 3$. Jadi, sisi yang mencapai n telah berputar dari arah tegak ke atas sebesar $\alpha \log_2 n$ secara keseluruhan, ditambah sedikit untuk setiap langkah ganjil: putarannya mencatat besar n. Sepanjang sebuah cabang, arah naik turun mengikuti bilangan dalam satu penerbangan, sehingga setiap cabang adalah penerbangan yang dilengkungkan. Cabang bergabung di tempat penerbangan bertemu. Dalam gambaran ini, dugaan tersebut menyatakan bahwa pohon yang tumbuh dari 1 memuat setiap bilangan bulat positif.

Masalah ini umumnya dikaitkan dengan Lothar Collatz, yang mengajukan pertanyaan semacam ini pada 1930-an. Bentuk karang mengikuti “Collatz seaweed” karya Edmund Harriss (2016).