Aradığımız en küçük tam sayı 50. Bu problem, iki ayrı kısıtın aynı anda sağlandığı bir minimizasyon sürecidir.
Süreci belirleyen kısıtlar ve darboğaz analizi şu şekildedir:
- Bölünebilirlik kısıtı: Sayının kendisi 10 ile kalansız bölünmelidir. Dolayısıyla aradığımız girdi 10, 20, 30, 40, 50 gibi 10 sayısının pozitif tam katları arasından seçilmelidir. Faktöriyel işlemi negatif tam sayılarda tanımlı değildir, 0 faktöriyel ise 1 değerini ürettiği için 10¹² ile bölünemez.
- Darboğaz analizi: Bir faktöriyelin 10¹² ile tam bölünebilmesi için asal çarpan ayrışımında en az 12 adet 2 ve en az 12 adet 5 çarpanı bulunmalıdır. Faktöriyel hesaplarında 2 çarpanının kümülatif artış hızı 5 çarpanından her zaman çok daha yüksektir. Dolayısıyla sistemdeki darboğaz 5 çarpanıdır. Hedefimiz faktöriyel içinde en az 12 adet 5 çarpanına ulaşmaktır.
- Legendre formülü: Bir n faktöriyel içindeki toplam 5 çarpanı sayısı, n değerinin 5, 25, 125 gibi 5 sayısının ardışık kuvvetlerine bölünmesi ve elde edilen tam kısımların toplanmasıyla bulunur.
10 sayısının katları üzerinden kapasite kontrolü yaptığımızda:
- n = 10 için: 10/5 = 2 adet 5 çarpanı bulunur, kapasite hedefin çok altındadır.
- n = 20 için: 20/5 = 4 adet 5 çarpanı elde edilir.
- n = 30 için: 30/5 + 30/25 = 6 + 1 = 7 adet 5 çarpanı üretilir.
- n = 40 için: 40/5 + 40/25 = 8 + 1 = 9 adet 5 çarpanı sağlar.
- n = 50 için: 50/5 + 50/25 = 10 + 2 = 12 adet 5 çarpanı tam olarak sağlanır.
50 faktöriyel, içerdiği 12 adet 5 çarpanı ve fazlasıyla yeterli olan 47 adet 2 çarpanı sayesinde 10¹² ile kalansız bölünür. Üstelik 49 faktöriyelde yalnızca 10 adet 5 çarpanı bulunduğu için 12 adet 5 çarpanına ulaşabilen en küçük tam sayı zaten 50 sayısıdır. Böylece her iki kısıt da minimum değer olan 50 noktasında karşılanmış olur.
Kaynaklar
-
Eric W. Weisstein. Legendre's Formula. Alındığı Yer:
| Arşiv Bağlantısı