Mükemmel Sayıları bulan program ve algoritması

Dünyanın çözülememiş 7 matematik probleminden birisi, mükemmel sayılarla ilgili.

Bu sayfada 7 soru bulunuyor: http://www.biltek.tubitak.gov.tr/gelisim/matematik/problemler.htm

Aşağıdaki soru dikkatimi çekti:

Mükemmel Sayı Sorusu

Mükemmel sayı kendisi haricindeki tüm çarpanlarının toplamı kendisini veren sayıdır. Örneğin 6 bir mükemmel sayıdır çünkü kendisi haricindeki çarpanları yani 1, 2 ve 3 toplanınca kendisini verir: 1 + 2 + 3 = 6. Diğer örneklerse 28, 496, 8128 şeklinde gidiyor. Şimdiye kadar hiç tek mükemmel bir sayıya rastlanmamış. Merak edilen böyle bir sayının varolup olmadığı. Eğer vardır diyorsanız bu sayıyı, saklandığı yerden bulup çıkarmalı, ya da olmadığını iddia ediyorsanız bunu ispatlamalısınız.

Bu sayıları sonsuza kadar(gittiği yere kadar) hesaplayan bir program yapalım “tek sayı” bulabilecekmiyiz bakalım dedim kendi kendime. Sonra düşündüm ki bu çarpanların içinde 2 var ise sonuç mutlaka çift olacaktır. Boşuna hesaplamayalım. Ama sevdiğim bir söz vardır: “Bir işe başlamak bitirmenin yarısıdır; ancak bir işi yarım bırakmışsak, hiç başlamamışız sayılır…” Ben de dedimki şimdi o kadar link verdik yazı yazdık boşa mı gitti yani diye sordum kendime. Madem başladık o programı yazalım hep beraber. Öncelikle bir sayının çarpanlarını bulmamız gerekmektedir.

Ek olarak şu bilgileride yazalım, dursun kenarda…

*Tek bir sayı ile tek sayının çarpımı tek sayıdır. (3 x 5 = 15 )
*Çift bir sayı ile çift bir sayının çarpımı çift sayıdır. (6 x 8 = 48 )
*Tek bir sayı ile çift sayının çarpımı çift sayıdır. ( 5 x 4 = 20 )

Verilen sayının tam olarak bölünebildiği bütün sayıları bulan C++ programını yazalım:

#include <iostream>

using namespace std;

int main()
{
    int sayi=0,i=0;

      cout << "Sayiyi giriniz : ";   

      cin >> sayi;

      for(i=1;i<sayi;i++)
      {        
        if(sayi%i==0) //eğer sonuç tam çıkmayacaksa hiç bölmesin bile
        {
            cout << i << ".bolen : "<<i<<endl;  
        }     
      }

    return 0;
}

Şimdi de bu programı değiştirerek, sonuçları birbiriyle çarpıp sonucun kendisini verip vermediğini hesaplayan, yani mükemmel sayıları bulan programı yazalım:

#include <iostream>

#define kaca_kadar 1000
using namespace std;

int main()
{
	int sayi=0,i=0; 
	int sonuclar[500];
	int kac_kere=0;
	int bolenlerin_toplami=0;

  	cout << kaca_kadar << " sayisina kadar olan mukemmel sayilar : " << endl;
  	for(sayi=1;sayi<kaca_kadar;sayi++)//sayi değişkenini sonsuz(integerin sınırları kadar) saydıralım
	{		
		//cout << "hesaplanan sayi : " << sayi;  
		//cout << "(" ;
		for(i=1;i<sayi;i++)
		{					
			if(sayi%i==0) //eğer sonuç tam çıkmayacaksa hiç bölmesin bile
			{
				kac_kere++;
				sonuclar[kac_kere]=i;
				//cout << i << ",";  //sonucu direkt yazdırabiliriz ancak değişkene atadığımız için daha sonra değişkenden yazdıracağız
			} 							
		}
		//cout << ")" << endl;

		//cout << "(" ;
		for(i=1;i<=kac_kere;i++)
		{		
			//cout << sonuclar[i] << " " ; //bu satırı aktif edersek mükemmel olmayan sayıların bolenlerini de görebiliriz
			bolenlerin_toplami+=sonuclar[i];
		}

		//cout << ")" << endl;

		if(bolenlerin_toplami==sayi)
		{
			cout << sayi << " sayisi bir mukemmel sayidir";
			cout << "(" ;
			for(i=1;i<=kac_kere;i++)
			{		
				cout << sonuclar[i] << " " ;				
			}
			cout << ")" << endl;
		}

		kac_kere=0;
		bolenlerin_toplami=0;

	}

  	cout << "islem tamamlanmistir" << endl;

	return 0;
}

#define kaca_kadar 1000 kodu ile 1000’e kadar olan sayıları kontrol ettik bu sayıyı artırarak istediğiniz sayıya kadar hesaplayabilirsiniz, ben 9999999 yaptım ilk başta ancak uzun sürdü hesaplaması o yüzden 1000 ile değiştirdim.

Programın ekran görüntüsü şu şekildedir:

 

Bu yazdığımız program elbette işe yarıyor ancak biraz hamallık yapmış olduk. Biraz matematik bilgimizi kullanırsak daha işlevsel ve daha kısa program yazabiliriz.

[(2^k)-1] bir asal sayı ise, [2^(k-1)] * [(2^k)-1] bir mükemmel sayıdır.
örneğin:
2^2-1=3 asal olduğu için 2*3=6 ,
2^3-1=7 asal olduğu için 4*7=28,
2^5-1=31 asal olduğu için 16*31=496,
2^7-1=127 asal olduğu için 64*127=8128 hep mükemmel sayılardır.

beşinci mükemmel sayı:
[(2^13)-1] * 2^12 = 33550336

altıncı mükemmel sayı:
[(2^17)-1] * 2^16 = 8589869056

yedinci mükemmel sayı:
[(2^19)-1] * 2^18 = 137438691328

sekizinci mükemmel sayı:
[(2^31)-1] * 2^30 = 2305843008139952128

dokuzuncu mükemmel sayı:
[(2^61)-1] * 2^60 = 2658455991569831744654692615953842176

onuncu mükemmel sayı:
[(2^89)-1] * 2^88 = 191561942608236107294793378084303638130997321548169216

 

İlk 10 mükemmel sayıyı bulan programı yapalım. “k” sabitini 89’a kadar deneyerek, [(2^k)-1] sayısının asal olup olmadığını deneyeceğiz eğer asal ise [(2^k)-1] sayısını [2^(k-1)] ile çarpacağız.

2^k demek 2 üzeri k demektir, yani 2 nin k’ıncı kuvveti demektir.

c dilinde kuvvet almak için pow() fonksiyonunu kullanırız

2^k işlemini pow(2,k); yazarak yapabiliriz.

Aşağıdaki kodlarla manuel olarak bilinen mükemmel sayıları hesaplayabiliriz:

	a=2; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //6
	a=3; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //28	
	a=5; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //496
	a=7; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl;	//8128
	a=13; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //33550336
	a=17; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //8589869056
	a=19; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //137438691328
	a=31; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //2305843008139952128
	a=61; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //2658455991569831744654692615953842176
	a=89; cout << (pow(2,a)-1)*(pow(2,a-1)) << endl; //191561942608236107294793378084303638130997321548169216

Ancak biz otomatik olarak yapsın istiyoruz ki gerekirse sonsuza kadar hesaplayabilelim.

#include <iostream>
#include <math.h>       /* pow */

using namespace std;

int main()
{
	for(int k=2; k <=89; k++)
	{
		asal=(pow(2,k)-1); 
		for (i = 2; i < asal; i ++)
                {   
			//sayinin tam olarak bölünüp bölünmedigi kontrol
    		        if (asal % i == 0) 
			{
				say++; 
			}			
                }
        
		if(say==0) 
		{			
			kacinci_mukemmel_sayi++;
			// eger say sıfıra esit ise sayi kendinden baska hicbir sayiya kalansiz bolunmemistir yani asal sayidir.
		        cout << kacinci_mukemmel_sayi << ". Mukemmel sayi : " << (pow(2,k)-1)*(pow(2,k-1)) << endl;		    
		}
		say=0;
	}
	
	return 0;
}

 

 

Sonuç olarak şu linki de paylaşmak istiyorum: http://tr.wikipedia.org/wiki/M%C3%BCkemmel_say%C4%B1

 

İlk 10 mükemmel sayı

  • 6
  • 28
  • 496
  • 8128
  • 33550336
  •  8589869056
  • 137438691328
  •  2305843008139952128
  • 2658455991569831744654692615953842176,
  • 91561942608236107294793378084303638130997321548169216

Ayrıca ilgilenen arkadaşlara  ilk 4 mükemmel sayı için şu özelliği verelim.

 

M. Gökhan BEKEN

3 thoughts on “Mükemmel Sayıları bulan program ve algoritması

Bir Cevap Yazın