Problem 5 - Smallest Multiple

Soru

1 ile 10 arasındaki tüm sayılara kalansız bölünen en küçük sayı 2520'dir.

Peki 1 ile 20 arasındaki tüm sayılara kalansız bölünen en küçük sayı nedir?


Yaklaşım

Bu soruyu matematik bilgisi ile elle çözmeyi tercih ettim. Nasıl çözebileceğimize bakalım.

Öncelikle 0<i<21 aralığındaki tüm i değerlerine bölünebilmesi için hangi sayılar çarpanları olmalıdır? 8'e bölünüyorsa 4'e ve 2'ye de bölünüyordur. Dolayısıyla 8'e bölünen bir sayıyı tekrar 2 ile çarpmaya gerek yok, yani bu sayı 20! değil, daha küçük çıkacak.

Fakat temel olarak bu aralıktaki tüm asal sayılar çarpanları olmalı.

2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 = 9699690 sonucunu elde ediyoruz.

Bu arada sayı da baya ilginç bir görünüme sahipmiş. Her neyse, ilk dikkatimizi çeken 10'a, 5'e ve 2'ye bölünebildiği oluyor. Zaten içerisinde 2 ve 5 asal çarpanlarını barındırdığı için bu çok normal.

Hangi sayılara şuanda tam bölündüğünü bulmak için çarpanları kendi arasında çarpabiliriz.
2 x 3 = 6
2 x 5 = 10
2 x 7 = 14
2 x 11 = 22 ( aralık dışı )
3 x 5 = 15

Bu aralıkta tam bölünen şuana kadar bulduklarımızı sıralarsak

1, 2, 3, 5, 6, 7, 10, 14, 15

Bölünmesi gereken sıradaki sayı 4. Fakat bu sayı şuanda 4 ile tam bölünmeyecektir. Çünkü içerisinde 1 adet 2 barındırıyor, oysa 4 için 2 adet 2 çarpanı olmalıydı. 

Öyleyse sayımızı 2 ile çarpıyoruz.

9699690 x 2 = 19399380 şimdi sayımız 4 ile de bölünüyor.

Şimdi yeni tablomuza bakalım

2 x 2 = 4
3 x 4 = 12
5 x 4 = 20

1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 20 sayılarına bölünür hale geldi.

8' e bölünmesi için tekrar 2 ile çarpıyoruz.

19399380 x 2 = 38798760 sonucunu elde ettik.

16'ya bölünmesi için bir kez daha 2, 9'a bölünmesi için bir kez daha 3 ile bölüyoruz. Sonuçta görüyoruz ki tüm çarpanlar elde edilmiş oluyor.


Cevap : 232792560 bulunuyor.