Problem 12 - Highly divisible triangular number

Soru

Üçgensel sayılar, kendi ve kendinden önceki doğal sayıların toplamı olan sayılardır. 7. üçgensel sayı 1+2+3+4+5+6+7 = 28'dir.

İlk 10 üçgensel sayı

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Bu sayıların bölenleri

1 : 1
3 : 1, 3
6 : 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

Görüyoruz ki 28 üçgensel sayısının 5'in üzerinde böleni var. Peki 500 üzerinde böleni olan ilk üçgensel sayı nedir?

Çözüm

Bu soruyu kaba kuvvet(brute force) ile çözmeye çalışmak gerçekten baya zaman alıyor. Bu yüzden bir yaklaşım belirlememiz gerek. Çünkü 10 milyonun üzerindeki bir sayının bölenlerini tek tek sayılara bölerek denemek, bunu 100 milyon sayıya uygulamak ciddi bir işlem zamanı istiyor.

Asal Çarpanlara Ayırma

Asal çarpanlara ayırma, bölen sayısını bulmak için ideal bir yöntem. Dikkatlice düşünürseniz, asal bölenleri bulmanın tüm bölenleri bulmanızı sağladığını fark edeceksiniz. 3 ve 5 asal sayılarıyla bölünen bir sayı asal olmayan 15 ile bölünecektir. Bunu daha önceki sorularda ele almıştık.

Asal çarpana ayırma yöntemiyle daha kolay bulunsa da ben farklı bir yaklaşım ele alacağım. 

2, 3, 5, 7, 11, 13, 17 asal sayılarını tahmini olarak seçtim. Muhtemelen bunlarla 500'ün üzerinde bölen elde edilebilir diyerek düşündüm, bu tamamen tahmini bir yaklaşım. Bu asalların ortak katı 510510. Ben eğer 510510'a tam bölünen üçgensel sayılara bakarsam, muhtemelen 500'ün üzerinde bölen vereceklerdir diye düşündüm. Nitekim öyle de oldu.

Üçgensel Sayılar Formülleme

Üçgensel sayıları bize veren formül

n(n+1)/2

Esasında bu Gauss Teoremi'nden geliyor. Üçgensel sayılar da toplamı ifade ettiği için, onları da bu formülle ifade edebiliyoruz.

Bu formülden elde edilen sayılardan, 510510 ile tam bölünenleri bir listeye aktardım.

Kodlama

private static ArrayList SecilmisUcgenseller(int Limit)
{
   ArrayList Secilmisler = new ArrayList();
   int n = 1;

   while (n * (n + 1) / 2 < Limit)
   {
      if ((n * (n + 1) / 2) % 510510 == 0)
         Secilmisler.Add(n * (n + 1) / 2);
      n++;
   }

   return Secilmisler;
}

Main bloğundaki kod

ArrayList Secilmisler = SecilmisUcgenseller(100000000);
long ucgensel = 0, bolenler = 0;

foreach (object nesne in Secilmisler)
{
   ucgensel = Convert.ToInt64(item);

   for (int i = 1; i <= triang; i++)
   {
      if (triang % i == 0)
         bolenler++;
   }

}

Biraz fazla kaba kuvvet kullanmış oluyoruz burada. Asal bölenlere ayrılabilir. Hatta asal bölenlere bölerken oluşturulacak asal listesi, her asal tek tek oluşturularak daha da zamandan kazandıracak şekilde yapılabilir. Fakat zaten tek bir sayı verdiği için(0ms içinde cevabı veriyor 510510'a tam bölünen tek sayı var bu aralıkta) bu yönteme gitmedim.

Denetlediğinizde ise 760ms gibi bir sürede 576 adet bölen olduğunu söyleyerek cevabı doğruluyor.

Cevap : 76576500 üçgensel sayısının 576 adet böleni var.
Sayının bulunması 0ms
Kontrol edilmesi 760ms