Menghitung angka nol dari bilangan faktorial dalam sistem bilangan apa pun

Bagaimana saya bisa menghitung jumlah nol jejak faktorial dari angka dalam sistem angka tertentu?

Mari kita lihat kasus ketika kita berada di sistem nomor 10, dan kemudian lihat bagaimana kita dapat menggeneralisasi ini menjadi solusi universal. Kita diberi nomor N dan untuk faktorialnya kita perlu menemukan jumlah nol yang tertinggal. Solusinya akan sangat sederhana - jumlahnya:

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ... 

Kami dapat menggeneralisasikannya ke dalam formula seperti itu:

$$

$$\ jumlah \ limit_ {i = 1} ^ \ infty {N \ lebih dari 5 ^ i}.$$

Mengapa 5? Sederhana saja. Nol akhir diperoleh hanya ketika angka memiliki 10 dalam faktorial. Dengan demikian, menghitung jumlah puluhan dalam faktorial, kita mengetahui jumlah nol hingga.

Mengapa dalam contoh di atas kita bagi dengan 5? Karena 10 dapat diperoleh dengan mengalikan 5 dengan 2. Oleh karena itu, solusi lengkap akan memiliki dua rumus:

$$

$$\ jumlah \ limit_ {i = 1} ^ \ infty {N \ lebih dari 5 ^ i}$$

dan

$$

$$\ jumlah \ limit_ {i = 1} ^ \ infty {N \ lebih dari 2 ^ i}.$$

Tetapi, dengan alasan yang logis, kita tahu bahwa jumlah pertama akan lebih sedikit, jadi kita hanya perlu menghitungnya (perincian lebih lanjut dapat ditemukan di sini ).

Solusi untuk masalah kita

Untuk menghitung nol terakhir dari faktorial angka dalam sistem angka tertentu, saya menyusun algoritma di bawah ini:

1. Faktor nomor B dari sistem angka.
2. Bagilah angka N dengan setiap faktor prima unik K, dengan mengalikan K dengan sendirinya sampai $$$N \ lebih dari K$akan lebih dari satu, sambil membulatkan setiap hasil ke integer yang lebih kecil.
3. Jika, ketika memperluas jumlah sistem bilangan, kita mendapatkan beberapa faktor utama identik K, maka kita harus membagi hasil di atas dengan jumlah K. yang identik
4. Dari semua divisi N oleh setiap faktor unik K, pilih hasil terkecil, yang akan menjadi jawaban kami.

Saya akan menunjukkannya dengan sebuah contoh.
Biarkan angka N = 5, sistem angka B = 12. Faktorial 5! = 120, dan 120 dalam sistem ke-12 adalah A0. Kita melihat bahwa dalam sistem bilangan terbatas faktorial dari bilangan asli memiliki satu nol. Jika kita mendekomposisi 12 menjadi faktor prima, kita mendapatkan 2, 2, 3. Kami memiliki dua angka unik: 2 dan 3. Dengan mengikuti algoritma kami, kami akan memenuhi poin 2 dengan angka 2.

$$

$${5 \ lebih dari 2} + {5 \ lebih dari 4} + {5 \ lebih dari 8} + ... = 2 + 1 + 0 + ... = 3.$$

Tetapi deuce bertemu dua kali dalam dekomposisi 12, jadi kami membagi hasil akhir dengan 2 dan bulat menjadi integer yang lebih kecil. Hasilnya, kita mendapat 1.

Kami melakukan hal yang sama dengan 3:

$$

$${5 \ lebih dari 3} + {5 \ lebih dari 9} + ... = 1 + 0 + ... = 1.$$

Dengan demikian, kami telah memperoleh dua quotients dari divisi nomor N dengan faktor prima dari jumlah sistem bilangan. Keduanya sama dengan 1, jadi kami tidak harus memilih yang lebih kecil dan kami hanya memberikan jawabannya - 1.

Pertimbangkan contoh lain.

Biarkan angka N = 16, sistem angka B = 16. Faktorial 16! = 20922789888000, dan 20922789888000 dalam sistem ke-16 - 130777758000. Kita melihat bahwa dalam sistem bilangan final faktorial dari bilangan asli memiliki tiga nol. Jika kita menguraikan 16 menjadi faktor prima, kita mendapatkan 2, 2, 2, 2. Di sini kita hanya memiliki satu nomor unik, oleh karena itu, item 2 dieksekusi hanya sekali:

$$

$${16 \ lebih dari 2} + {16 \ lebih dari 4} + {16 \ lebih dari 8} + {16 \ lebih dari 16} + {16 \ lebih dari 32} + ... = 8 + 4 + 2 + 1 + 0 + ... = 15.$$

Ketika kami dekomposisi, kami memiliki empat deuces, jadi kami membagi jumlah divisi dengan 4 dengan pembulatan ke integer yang lebih kecil: $$${15 \ lebih dari 4} = 3.$

PS Sebagian besar materi untuk posting diterjemahkan dari sini . Diposting oleh Aditya Ramesh .