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

Soru: 1 ile 10 arasından tüm sayılara eksiksiz olarak bölünebilen en küçük sayı 2520'dir. 1 ile 20 arasındaki tüm sayılara eksiksiz 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ı.

\begin{equation}
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
\end{equation}

Aralarından asal olanları ayıralım.

\begin{equation}
2, 3, 5, 7, 11, 13, 17, 19
\end{equation}

Ş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 'den 'ye kadar olan tüm sayıları çarpmadığımıza dikkat edin. Çünkü ile bölünen bir sayı ile zaten bölünüyordur, onu bir daha 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.

\begin{equation}
2*3*5*7*11*13*17*19 = 9699690
\end{equation}

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 yani çarpanı da var. Aynı şekilde yani çarpanı da var. Bu sayıları da denetleyip listemize eklersek toplamda aşağıdaki çarpanları elde etmiş oluyoruz.

\begin{equation}
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19
\end{equation}

Liste neredeyse tamamlanmış görünüyor. Eksik olan sayılar . İhtiyacımız olan çarpanı için elde ettiğimiz sayısını ile çarpmamız yeterlidir. Çünkü içerisinde zaten hali hazırda bir çarpanı barındırıyor. Öyleyse sayımız oldu. Listemize çarpanının girmesiyle yeni çarpanlar da eklendi. Çünkü hali hazırda bulunan sayısını ile çarptığımızda çarpanını da barındırmış olacak. Listemizi yeniden düzenlersek;

\begin{equation}
1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 19, 20
\end{equation}

Eksik kalan sayılarımız ve . Bunları elde etmek için sayımızı iki kere ile ve bir kere de ile çarpmamız yeterli olacaktır.

Böylelikle sonuç: olarak bulunur.

Ögetay Kayalı

Ögetay Kayalı

Astronom. Özel ilgi alanı teorik kozmoloji, özellikle Einstein'ın görelilik kuramının modifiye edilmesi (modified gravity) üzerine uğraşıyor. Bunların yanında ender bulduğu zaman aralıklarında kafasına esince programlama, 3B modelleme, makineler, tasarım, fotoğrafçılık, resim ve satranç ile de ilgileniyor.

Ögetay Kayalı 120 makale yazdıÖgetay Kayalı tarafından yazılan tüm makaleleri gör