Project Euler 5: En Küçük Çarpım

Soru: 1 ile 10 arasından tüm sayılara tam olarak bölünebilen en küçük sayı 2520'dir. 1 ile 20 arasındaki tüm sayılara tam olarak bölünebilen en küçük sayı kaçtır?

Project Euler'in bazı sorularını matematiksel olarak çözmek, kod yazarak çözmekten daha kolay olabiliyor. Bu soru da kağıt kalem kullanarak çözmeyi tercih ettiğim sorulardan. Fakat aynı mantığı algoritmaya dökerek kodlayarak da çözebilirsiniz. Özellikle sayının büyük olup işlerin karmaşıklaştığı noktalarda bu gerekiyor. Fakat bu soruyu çözmek için gereken mantık, kağıt kalem üzerinde oldukça pratik bir iş görüyor.
Sayımızı tersten giderek elde edeceğiz. Sakın ciddi manada büyük sayıların tek tek bölünüp bölünmediğini kontrol etmeye kalkmak gibi bir işe kalkışmayın! Bölmeyle işimiz yok, biz çarparak bu sayıyı elde edeceğiz. İhtiyacımız olan şey sayımızın aşağıdaki çarpanlara sahip olması.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Aralarından asal olanları ayıralım.
2, 3, 5, 7, 11, 13, 17, 19
Şimdi yapmamız gereken bu sayıları çarpmak. Böylece çarpanları bu asal sayılar olan bir sayı elde edeceğiz. Sonra eksik olan diğer çarpanları da ekleyerek aradığımız sayıya ulaşacağız. Doğrudan 1'den 20'ye kadar olan tüm sayıları çarpmadığımıza dikkat edin. Çünkü 20 ile bölünen bir sayı 10 ile zaten bölünüyordur, onu bir daha 10 ile çarparsanız en küçük sayıyı elde edemezsiniz. Elde edeceğiniz sayı kesinlikle hepsine tam bölünüyor olacaktır, fakat en küçük çarpım olmayacaktır.
2*3*5*7*11*13*17*19 = 9699690
Asal çarpanlarımızla elde ettiğimiz bu sayı, aslında asal çarpanlardan başka aradığımız diğer sayılara da tam olarak bölünüyor. Örneğin sayımız içerisinde 2*3 yani 6 çarpanı da var. Aynı şekilde 2*5 yani 10 çarpanı da var. Bu sayıları da denetleyip listemize eklersek toplamda aşağıdaki çarpanları elde etmiş oluyoruz.
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19
Liste neredeyse tamamlanmış görünüyor. Eksik olan sayılar 4, 8, 9, 12, 16, 18. İhtiyacımız olan 4 çarpanı için elde ettiğimiz 9699690 sayısını 2 ile çarpmamız yeterlidir. Çünkü içerisinde zaten hali hazırda bir 2 çarpanı barındırıyor. Öyleyse sayımız 9699690*2 = 19399380 oldu. Listemize 4 çarpanının girmesiyle yeni çarpanlar da eklendi. Çünkü hali hazırda bulunan 3 sayısını 4 ile çarptığımızda 12 çarpanını da barındırmış olacak. Listemizi yeniden düzenlersek;
1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 19, 20
Eksik kalan sayılarımız 8, 9, 16 ve 18. Bunları elde etmek için sayımızı iki kere 2 ile ve bir kere de 3 ile çarpmamız yeterli olacaktır.
Böylelikle sonuç: 19399380 x 12=232792560 olarak bulunur.
Ögetay Kayalı