Faktorial yang dapat dibagi

Baru-baru ini, saya benar-benar bingung dengan tweet dari Farm Library ini:


"Itulah yang terjadi jika kamu tidak memperbanyak tetapi membagi dalam faktorial."

Ketika saya melihatnya, saya harus melepaskan bisnis saya, mengambil buku catatan dan memeriksa formulanya. Hasil rancangannya tampak logis. Karena versi multiplikatif $$$n!$ dengan meningkatnya $$$n$ cenderung tak terhingga, maka versi "membagi" harus cenderung ke nol. Dan $$$\ frac {n ^ 2} {n!}$ berperilaku seperti itu; fungsi polinomial $$$n ^ 2$ tumbuh lebih lambat dari fungsi daya $$$n!$ cukup besar $$$n$ :

$$

$$\ frac {1} {1}, \ frac {4} {2}, \ frac {9} {6}, \ frac {16} {24}, \ frac {25} {120}, \ frac {36 } {720}, \ frac {49} {5040}, \ frac {64} {40320}, \ frac {81} {362880}, \ frac {100} {3628800}$$

Tetapi mengapa hasil pembagian mengambil formulir $$$\ frac {n ^ 2} {n!}$ ? Dari mana asalnya $$$n ^ 2$ ?

Untuk menjawab pertanyaan ini, saya harus membongkar trauma lama yang terkait dengan studi pembagian fraksional, tetapi saya mengatasi rasa sakitnya. Bergerak dari rumus tweet dari kiri ke kanan, pertama-tama kita dapatkan $$$\ frac {n} {n-1}$ . Kemudian, bagi nilai ini dengan $$$n-2$ kita dapatkan

$$

$$\ cfrac {\ frac {n} {n-1}} {n-2} = \ frac {n} {(n-1) (n-2)}$$

Melanjutkan dengan cara ini, kita berakhir dengan:

$$

$$n \ mathbin {/} (n-1) \ mathbin {/} (n-2) \ mathbin {/} (n-3) \ mathbin {/} \ cdots \ mathbin {/} 1 = \ frac {n } {(n-1) (n-2) (n-3) \ cdots 1} = \ frac {n} {(n-1)!}$$

Untuk mendapatkan hasil yang ditampilkan di tweet $$$\ frac {n ^ 2} {n!}$ , kami hanya mengalikan pembilang dan penyebut dengan $$$n$ . (Meskipun untuk seleraku, ekspresinya $$$\ frac {n} {(n-1)!}$ lebih jelas.)

---

Saya seorang penggemar faktorial yang diakui secara resmi. Simpan urutan Fibonacci Anda bersama Anda; di sini adalah fitur favorit saya. Setiap kali saya belajar bahasa pemrograman baru, latihan pertama saya adalah menulis beberapa prosedur untuk menghitung faktorial. Selama bertahun-tahun, saya telah membuat beberapa variasi topik ini, misalnya, penggantian definisi $$$\ kali$ pada $$$+$ (yang memberi kita angka segitiga). Tapi sepertinya aku tidak pernah berpikir untuk mengganti sebelumnya $$$\ kali$ pada $$$\ mathbin {/}$ . Ternyata aneh. Karena perkalian bersifat komutatif dan asosiatif, kita dapat mendefinisikan $$$n!$ sama seperti produk dari semua bilangan bulat dari $$$1$ sebelumnya $$$n$ tanpa khawatir tentang urutan operasi. Tetapi ketika membagi, urutannya tidak bisa diabaikan. Dalam kasus umum $$$x \ mathbin {/} y \ ne y \ mathbin {/} x$ dan $$$(x \ mathbin {/} y) \ mathbin {/} z \ ne x \ mathbin {/} (y \ mathbin {/} z)$ .

Di Tweet Perpustakaan Farm, pembagi berada dalam urutan menurun: $$$n, n-1, n-2, \ ldots, 1$ . Paling jelas, ini akan digantikan oleh urutan naik: $$$1, 2, 3, \ ldots, n$ . Apa yang terjadi jika kita mendefinisikan faktor pembagian? $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ ? Kembali lagi ke algoritma pembagian fraksional sekolah memberi kita jawaban sederhana:

$$

$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n = \ frac {1} {2 \ kali 3 \ kali 4 \ kali \ cdots \ kali n} = \ frac {1} {n!}$$

Dengan kata lain, ketika kita melakukan pembagian berkali-kali, lakukan penghitungan dari $$$1$ sebelumnya $$$n$ , hasil akhirnya akan sama dengan timbal balik $$$n!$ . (Saya ingin memberi tanda seru di akhir kalimat ini, tapi sayang!) Jika Anda mencari jawaban kanonik untuk pertanyaan, “Apa yang kita dapatkan saat membagi bukannya mengalikan dalam $$$n!$ ? ", Maka saya akan mengatakan itu $$$\ frac {1} {n!}$ Adalah kandidat yang lebih baik daripada $$$\ frac {n} {(n - 1)!}$ . Mengapa kita tidak menerima simetri di antara keduanya $$$n!$ dan nilai kebalikannya?

Tentu saja, ada banyak cara lain untuk menempatkan n nilai integer di set $$$\ {1 \ ldots n \}$ . Tapi seberapa tepatnya? Ternyata, tepatnya $$$n!$ ! Karena itu, sepertinya ada $$$n!$ cara unik untuk mendefinisikan fungsi divisi $$$n!$ . Namun, mempelajari jawaban dari dua permutasi yang ditunjukkan di atas membuat kita mengerti bahwa pola yang lebih sederhana bekerja di sini. Apapun elemen dari urutan muncul pertama kali, ia muncul di pembilang dari sebagian besar, dan produk dari semua elemen lain adalah penyebutnya. Karena itu, pada akhirnya hanya ada $$$n$ hasil yang berbeda (dengan asumsi kami selalu melakukan operasi divisi dengan ketat dari kiri ke kanan). Untuk bilangan bulat apa pun $$$k$ dalam kisaran dari $$$1$ sebelumnya $$$n$ dengan pengaturan $$$k$ di awal baris, kami membuat pembagian $$$n!$ sama dengan $$$k$ dibagi dengan semua faktor lain. Anda dapat menulis ini sebagai berikut:

$$

$$\ cfrac {k} {\ frac {n!} {k}}, \ text {yang dapat dikonversi menjadi} \ frac {k ^ 2} {n!}$$

Jadi kami memecahkan sedikit teka-teki tentang bagaimana caranya dalam tweet ini $$$\ frac {n} {(n-1)!}$ berubah menjadi $$$\ frac {n ^ 2} {n!}$ .
Perlu dicatat bahwa semua fungsi ini konvergen ke nol saat $$$n$ hingga tak terbatas. Dari sudut pandang asimptotik, $$$\ frac {1 ^ 2} {n!}, \ frac {2 ^ 2} {n!}, \ ldots, \ frac {n ^ 2} {n!}$ identik.

---

Ya! Misi tercapai. Masalahnya terpecahkan. Pekerjaan sudah selesai. Sekarang kita tahu semua yang kita butuhkan tentang membagi faktorial, kan?

Yah, mungkin ada satu pertanyaan lagi. Apa yang akan dikatakan komputer? Jika kita mengambil algoritma faktorial favorit kita, dan melakukan apa yang diusulkan dalam tweet, ganti semua kemunculan operator $$$\ kali$ (atau * ) pada / , apa yang akan terjadi? Yang mana dari $$$n$ opsi pembagian $$$n!$ akankah program memberi kita?

Berikut ini adalah algoritma favorit saya untuk menghitung faktorial sebagai program di Julia :

 function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end end 

Algoritma ini memperkenalkan seluruh generasi kutu buku pada konsep rekursi. Dalam bentuk teks, terbaca: jika $$$n$ sama dengan $$$1$ lalu $$$mul! (n)$ sama dengan $$$1$ . Jika tidak, Anda harus menghitung fungsinya $$$mul! (n-1)$ dan kemudian gandakan hasilnya dengan $$$n$ .

_{Anda mungkin bertanya apa yang terjadi jika} $$_{$n$ akan menjadi nol atau negatif. Anda bisa bertanya, tetapi lebih baik tidak melakukannya. Untuk tujuan kita saat ini} $$_{$n \ in \ mathbb {N}$ .}

Dimulai dengan positif $$$n$ , urutan panggilan rekursif cepat atau lambat akan turun ke $$$n = 1$ .

Fungsi dapat ditulis lebih ringkas menggunakan gaya definisi Julia garis tunggal:

 mul!(n) = n == 1 ? 1 : n * mul!(n - 1) 

Apakah bagian kanan operator penugasan ekspresi kondisional, atau operator ternary dari formulir a ? b : c a ? b : c . Di sini a adalah kondisi tes Boolean, yang harus mengembalikan true atau false . Jika a true , maka ekspresi b dievaluasi, dan hasilnya menjadi nilai seluruh ekspresi. Kalau tidak, c dihitung.

Hanya untuk memastikan bahwa saya melakukan semuanya dengan benar, berikut adalah 10 faktor pertama yang dihitung oleh program ini:

 [mul!(n) for n in 1:10] 10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 

Sekarang, mari kita ubah definisi ini dan ubah satu-satunya kejadian * di / , biarkan semuanya tidak berubah (kecuali untuk nama fungsi).

 div!(n) = n == 1 ? 1 : n / div!(n - 1) 

Dan inilah yang akan dikembalikan oleh program jika kita menjalankannya untuk nilainya $$$n$ dari $$$1$ sebelumnya $$$20$ :

 [div!(n) for n in 1:20] 20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418 

Apa? Ini jelas tidak suka konvergen ke nol, sama seperti $$$\ frac {1} {n!}$ atau $$$\ frac {n} {n - 1}$ . Bahkan, nilainya tidak terlihat seperti ini, karena tidak akan menyatu. Dilihat oleh grafik di bawah ini, urutan terdiri dari dua komponen intermiten, yang masing-masing tampaknya tumbuh perlahan menuju infinity, dan juga menyimpang dari yang lain.


Memahami apa yang kita amati di sini, akan berguna untuk mengubah tipe output dari fungsi div! . Alih-alih menggunakan operator pembagian / , yang mengembalikan nilai sebagai angka titik-mengambang, kita dapat menggantinya dengan operator // , yang mengembalikan nilai rasional yang tepat, dibulatkan ke istilah terendah.

 div!(n) = n == 1 ? 1 : n // div!(n - 1) 

Berikut adalah urutan nilai untuk n 1:20 :

 20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189 

Daftar ini penuh dengan pola yang menarik. Ini adalah heliks ganda di mana bilangan genap dan ganjil dalam zig-zag bergerak dalam utas yang saling melengkapi. Bahkan angka bukan hanya genap, semuanya adalah derajat $$$2$ . Selain itu, mereka muncul berpasangan - pertama dalam pembilang, kemudian dalam penyebut - dan urutannya tidak menurun. Tetapi ada celah; tidak semua derajat hadir $$$2$ . Thread aneh terlihat lebih kompleks, koefisien kecil sederhana yang berbeda muncul dan menghilang dalam angka. (Bilangan prima harus kecil, setidaknya kurang $$$n$ .)

Hasil ini mengejutkan saya. Saya berharap untuk melihat urutan yang jauh lebih lembut, seperti yang saya hitung di atas kertas. Semua lompatan naik dan turun ini tidak masuk akal. Tren umum menuju pertumbuhan tak terbatas dalam rasio juga tidak masuk akal. Bagaimana kita bisa terus-menerus membagi, sambil menerima semua angka yang lebih besar dan lebih besar?

Pada titik ini, Anda dapat berhenti membaca dan mencoba untuk menemukan teori Anda sendiri tentang dari mana angka-angka zigzag ini berasal. Jika Anda memerlukan petunjuk, maka Anda memilikinya, dan yang sangat kuat, hampir spoiler: cari urutan pembilang atau urutan penyebut dalam Ensiklopedia Online Urutan Integer .

---

Ini petunjuk lain. Perubahan kecil dalam program div! sepenuhnya mengkonversi output. Ubah saja ekspresi terakhir dengan mengganti n // div!(n - 1) dengan div!(n - 1) // n .

 div!(n) = n == 1 ? 1 : div!(n - 1) // n 

Sekarang hasilnya terlihat seperti ini:

 10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800 

Ini adalah fungsi kebalikan dari faktorial yang telah kita lihat, serangkaian nilai yang dihasilkan dengan pergi dari kiri ke kanan dalam urutan pembagi yang semakin meningkat. $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ .

Tidak mengherankan, mengubah ekspresi terakhir dalam prosedur mengubah hasilnya. Pada akhirnya, kita tahu bahwa pembagian bukanlah komutatif atau asosiatif. Tetapi sulit untuk memahami mengapa urutan nilai yang dihasilkan oleh program asli memberikan bentuk zigzag yang aneh. Mekanisme apa yang memunculkan dua kekuatan berpasangan dan nilai ganjil dan genap seperti itu?

Saya menemukan bahwa menjelaskan apa yang terjadi dalam urutan zigzag lebih mudah pada versi iteratif prosedur, daripada yang rekursif. (Pernyataan ini mungkin tampak menjengkelkan bagi mereka yang menemukan definisi rekursif lebih sederhana, tetapi hal itu baru saja terjadi.) Berikut ini tampilannya seperti:

 function div!_iter(n) q = 1 for i in 1:n q = i // q end return q end 

Saya menyatakan bahwa prosedur ini dengan siklus fungsional identik dengan fungsi rekursif, dalam arti bahwa jika div!(n) dan div!_iter(n) mengembalikan hasil untuk beberapa bilangan bulat positif n , maka itu akan selalu sama. Ini buktiku:

 [div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189 

Untuk memahami proses yang menghasilkan angka-angka ini, pertimbangkan nilai sekuensial variabel $$$i$ dan $$$q$ setiap kali Anda menjalankan loop. Awalnya $$$i$ dan $$$q$ sama $$$1$ ; oleh karena itu, setelah lintasan pertama dari siklus, ekspresi q = i // q memberi $$$q$ nilai $$$\ frac {1} {1}$ . Lalu $$$i = 2$ , dan $$$q = \ frac {1} {1}$ , yaitu makna baru $$$q$ sama dengan $$$\ frac {2} {1}$ . Di iterasi ketiga $$$i = 3$ , dan $$$q = \ frac {2} {1}$ itu memberi kita $$$\ frac {i} {q} \ rightarrow \ frac {3} {2}$ . Jika ini masih membingungkan, maka bayangkan $$$\ frac {i} {q}$ bagaimana $$$i \ times \ frac {1} {q}$ . Pengamatan penting di sini adalah dengan setiap siklus loop $$$q$ mendapat nilai sebaliknya, menjadi $$$\ frac {1} {q}$ .

Jika Anda memperluas operasi ini dan melihat penggandaan dan pembagian yang termasuk dalam setiap elemen seri, maka muncul pola:

$$

$$\ frac {1} {1}, \ quad \ frac {2} {1}, \ quad \ frac {1 \ cdot 3} {2}, \ quad \ frac {2 \ cdot 4} {1 \ cdot 3 }, \ quad \ frac {1 \ cdot 3 \ cdot 5} {2 \ cdot 4} \ quad \ frac {2 \ cdot 4 \ cdot 6} {1 \ cdot 3 \ cdot 5}$$

Secara umum:

$$

$$\ frac {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n} {2 \ cdot 4 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {odd} n) \ qquad \ frac {2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n} {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {even} n)$$

---

Fungsi $$$1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n$ untuk aneh $$$n$ dan $$$2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n$ bahkan untuk $$$n$ punya nama sendiri! Mereka disebut faktorial ganda, dan ditulis sebagai $$$n !!$ .

_{Terminologi yang mengerikan, kan? Akan lebih baik jika mereka disebut "semi-faktorial." Dan jika saya tidak tahu, saya akan membaca} $$_{$n !!$ sebagai faktorial faktorial.}

Faktorial ganda n didefinisikan sebagai produk dari n dan semua bilangan bulat positif lebih kecil dari paritas yang sama. Jadi urutan nilai zigzag kami yang aneh itu adil $$$\ frac {n !!} {(n-1) !!}$ .

Sebuah artikel 2012 oleh Henry W. Gould dan Jocelyn Quentens (sayangnya, di belakang paywall) mengeksplorasi penggunaan faktorial ganda. Mereka jauh lebih umum daripada yang mungkin Anda pikirkan. Pada pertengahan abad ke-17, John Wallis memperoleh identitas berikut:

$$

$$\ frac {\ pi} {2} = \ frac {2 \ cdot 2 \ cdot 4 \ cdot 4 \ cdot 6 \ cdot 6 \ cdots} {1 \ cdot 3 \ cdot 3 \ cdot 5 \ cdot 5 \ cdot 7 \ cdots} = \ lim_ {n \ rightarrow \ infty} \ frac {((2n) !!) ^ 2} {(2n + 1) !! (2n - 1) !!}$$

Serangkaian lebih aneh melibatkan kubus nilai faktorial ganda diringkas dalam $$$\ frac {2} {\ pi}$ . Dia ditemukan oleh Srinivasa Ramanujan.

Gould dan Kientens juga dianggap setara faktorial ganda untuk koefisien binomial. Koefisien binomial standar didefinisikan sebagai:

$$

$$\ binom {n} {k} = \ frac {n!} {k! (n-k)!}$$

Versi dual terlihat seperti ini:

$$

$$\ left (\! \ binom {n} {k} \! \ right) = \ frac {n !!} {k !! (n-k) !!}$$

Perhatikan bahwa angka zigzag kami sesuai dengan deskripsi ini, dan karenanya dapat dianggap sebagai koefisien binomial faktorial ganda. Lebih khusus lagi, mereka adalah angka-angka tersebut:

$$

$$\ kiri (\! \ binom {n} {1} \! \ kanan) = \ kiri (\! \ binom {n} {n - 1} \! \ kanan) = \ frac {n !!} {1 !! (n-1) !!}$$

Kacang polos $$$\ binom {n} {1}$ tidak terlalu menarik; dia sama saja $$$n$ . Namun versi ganda $$$\ left (\! \ binom {n} {1} \! \ right)$ seperti yang kita lihat, tarian yang lebih hidup adalah menari. Dan tidak seperti binomial biasa, itu tidak selalu bilangan bulat. (Satu-satunya nilai integer adalah $$$1$ dan $$$2$ .)

Pandangan pada angka zigzag sebagai hasil bagi faktorial ganda menjelaskan beberapa sifat mereka, dimulai dengan nilai genap dan ganjil. Kita juga bisa melihat mengapa semua angka genap dalam urutan adalah kekuatan 2. Pertimbangkan contoh dengan $$$n = 6$ . Pembilang dari fraksi ini adalah $$$2 \ cdot 4 \ cdot 6 = 48$ menerima dari $$$6$ pengganda $$$3$ . Tapi penyebutnya $$$1 \ cdot 3 \ cdot 5 = $ 1$ . Kembar tiga di atas dan di bawah menyusut, meninggalkan kita $$$\ frac {16} {5}$ . Pengurangan seperti itu terjadi di setiap kasus. Setiap kali faktor ganjil muncul dalam urutan bilangan genap $$$m$ , itu tentu memiliki bentuk $$$2 \ cdot m$ tetapi pada saat ini sendiri $$$m$ seharusnya sudah muncul dalam urutan angka ganjil.

---

Adalah urutan angka zig-zag jawaban yang masuk akal untuk pertanyaan: "Apa yang terjadi jika kita membagi, daripada mengalikan dalam $$$n!$ ? " Atau apakah program komputer menghasilkan mereka hanya berubah menjadi algoritma yang salah? Menurut pendapat pribadi saya, $$$\ frac {1} {n!}$ - jawaban yang lebih intuitif, tetapi $$$\ frac {n !!} {(n - 1) !!}$ - lebih menarik.

Selain itu, keberadaan urutan zig-zag memperluas wawasan kita. Seperti yang dinyatakan di atas, jika Anda bersikeras bahwa algoritma pembagian harus selalu berurutan melalui daftar pembilang $$$n$ , pada setiap langkah membagi angka di sebelah kiri dengan angka di sebelah kanan, ada total $$$n$ hasil yang mungkin, dan mereka semua terlihat sangat mirip. Tetapi solusi zigzag memberikan kemungkinan yang jauh lebih luas. Kami dapat merumuskan masalah sebagai berikut: mengambil set pembilang $$$\ {1 \ dots n \}$ , pilih subsetnya dan balikkan semua elemen dari subset ini; Sekarang kita mengalikan semua pembilang, baik terbalik dan langsung. Jika subset terbalik kosong, maka hasilnya akan menjadi faktorial reguler $$$n!$ . Jika semua pembilang menjadi kebalikan dari nilainya, maka kita akan mendapatkan sebaliknya $$$\ frac {1} {n!}$ . Dan jika setiap pembilang kedua dikonversi, dimulai dengan $$$n - 1$ , maka hasilnya akan menjadi elemen dari urutan zigzag.

Ini hanya beberapa dari banyak opsi yang tersedia; total ada $$$2 ^ n$ himpunan bagian dari $$$n$ elemen. Misalnya, Anda dapat mengambil kebalikan dari setiap angka yang utama atau kekuatan utama $$$(2, 3, 4, 5, 7, 8, 9, 11, \ dots)$ . Paling tidak $$$n$ hasilnya melonjak, tetapi terus-menerus tetap kurang $$$1$ :


Namun, jika saya melanjutkan grafik ini untuk lebih $$$n$ , dia akan pergi ke stratosfer. Derajat bilangan prima menjadi sangat jarang pada garis bilangan.

---

Sekarang saya akan mengajukan pertanyaan. Kami melihat variasi faktorial mendekati nol sebagai $$$n$ hingga tak terbatas misalnya $$$1 / n!$ . Kami telah melihat variasi lain tumbuh dengan meningkatnya $$$n$ tidak terbatas, termasuk saya sendiri $$$n!$ dan nomor zig-zag. Apakah ada varietas dari proses faktorial yang konvergen ke batas terbatas yang tidak nol?

Pertama-tama, algoritma berikut terjadi pada saya:

 function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q end 

Kami loop melalui nilai integer dari $$$n$ ke bawah $$$1$ menghitung produk / hasil bagi saat ini dalam proses $$$q$ . Pada setiap langkah, jika nilai saat ini $$$q$ lebih lanjut $$$1$ , kami membaginya dengan pembilang berikutnya, jika tidak, kami melakukan perkalian. Skema ini mengimplementasikan beberapa jenis manajemen umpan balik atau perilaku pencarian target. Jika $$$q$ terlalu besar, kita menguranginya; jika terlalu kecil, kami meningkatkannya. Saya menyarankan itu sambil berjuang $$$n$ hingga tak terbatas $$$q$ akan menyatu ke rentang nilai yang terus menyempit di sebelah $$$1$ .

Tetapi percobaan itu mengejutkan saya:


Gelombang gigi gergaji seperti itu tidak seperti yang saya harapkan. Anehnya, kurva tidak simetris $$$1$ ; penyimpangan dari atas memiliki amplitudo yang lebih besar daripada dari bawah. Tetapi distorsi ini lebih visual daripada matematika. Sejak $$$q$ bersifat pribadi, jarak dari $$$1$ sebelumnya $$$10$ sama seperti jarak dari $$$1$ sebelumnya $$$\ frac {1} {10}$ tetapi pada skala linier tidak terlihat seperti itu. Anda dapat memperbaikinya dengan menyusun grafik logaritmik dari hasil bagi:


Sekarang grafiknya simetris, atau setidaknya kira-kira sama, dan terpusat relatif terhadap nilainya $$$0$ yang merupakan logaritma $$$1$ . Namun masih ada rahasia yang lebih serius. Gelombang gigi gergaji sangat teratur dan memiliki periode $$$4$ , sementara tidak menunjukkan tanda-tanda kompresi ke arah nilai batas yang diharapkan $$$\ log q = 0$ . Nilai numerik menunjukkan bahwa kapan $$$n$ hingga tak terbatas, puncak kurva konvergen ke nilai yang sedikit lebih tinggi $$$q = \ frac {5} {3}$ , dan posisi terendah mendekati nilai yang sedikit lebih rendah $$$q = \ frac {3} {5}$ . (Logaritma dasar yang sesuai $$$10$ kira-kira sama $$$\ pm0.222$ ) Saya tidak tahu mengapa ini terjadi. Mungkin seseorang bisa menjelaskan.

Kegagalan dengan algoritma serakah ini tidak berarti bahwa kita tidak dapat membagi konversi faktorial menjadi $$$q = 1$ .

_{Jika kita bekerja dengan logaritma pembilang, maka prosedur ini menjadi kasus masalah komputasi yang terkenal yang disebut "masalah memecah satu set angka". Kita diberi banyak bilangan real, dan kita harus membaginya menjadi dua set, yang jumlahnya sama, atau sedekat mungkin dengan persamaan. Ini adalah tugas yang terbukti sulit, tetapi juga disebut ( PDF ) "tugas paling sederhana yang kompleks."}

Untuk apapun $$$n$ kita dapat menemukan bahwa ketika menggunakan nilai invers dari beberapa subset pembilang lainnya memberi kita perkiraan yang lebih baik $$$n! = 1$ . Untuk kecil $$$n$ kita bisa menyelesaikan masalah ini dengan kekerasan: pertimbangkan saja semuanya $$$2 ^ n$ himpunan bagian dan pilih yang terbaik.

Saya menghitung partisi optimal hingga $$$n = 30$ ketika Anda perlu memilih dari satu miliar opsi.


Jelas, grafik semakin datar. Anda bisa menggunakan metode yang sama untuk memaksa konvergensi ke nilai lain di rentang dari $$$0$ sebelumnya $$$n!$ .

Maka kami mendapat jawaban lain untuk pertanyaan yang diajukan oleh tweet dan memulai perjalanan kami. Apa yang terjadi jika kita membelah dan tidak memperbanyak $$$n!$ ? Apapun yang kita inginkan.