Ok, pada postingan kali ini saya akan membahas pembuktian Legendre Conjecture dengan teknik komputasi. Legendre Conjecture simpelnya seperti ini (menurut status FB teman saya) :

Selalu ada, paling tidak, 1 buah bilangan prima diantara kuadrat dua bilangan bulat positif yang berurutan

Nah, sesuai definisi Conjecture, yaitu pernyataan yang masih belum terbukti, kita memang akan sangat sulit membuktikannya secara analitik (menggunakan ilmu-ilmu pure mathematics), dan memang sampai saat ini belum ada manusia yang bisa membuktikannya. Tapi, setidaknya kita bisa membuktikan conjecture ini berlaku sampai suatu batasan bilangan bulat positif tertentu tentunya dengan dibantu komputer. :)

Dalam percobaan ini batasan bilangan bulat positif yang bisa dicapai adalah 2^32-1 =  4,294,967,295. Ini adalah batasan variabel integer di C++ yang hanya mempunyai 32 bit. Untuk improvement, sebenarnya bisa kita gunakan Integer yang 64 bit atau class integer khusus yang punya digit tak terbatas. Tapi mungkin akan memerlukan kemampuan CPU yang besar dan waktu yang sangat lama untuk mengecek bilangan bulat positif lebih dari 4,2 milyar tsb. Padahal, untuk percobaan ini saja, pengecekan sampai 1 milyar perlu waktu sekitar 1 menit.

Ini adalah kode programnya yang saya potong menjadi beberapa bagian yang berurutan, tujuannya untuk memudahkan penjelasan, Anda dapat menggabungkan potongan2 kode ini menjadi 1 file main.cpp untuk ikut melakukan pengetesan sesuai penjelasan2 saya disini. :)

#include <iostream>
#include "math.h"
#include <fstream>
#include <string>

using std::cout;

int main(){

// n adalah nilai maksimum bilangan bulat yang akan kita cek
// Untuk pengetesan awal, kita coba n yang kecil
// Nanti, kita dapat ubah n jadi sangat besar (misal : 1,000,000,000)
// limit ini adalah batas pengecekan pada algoritma Sieve di bawah

int n = 120;
int limit = static_cast<int>(sqrt(static_cast<double>(n)));
int i=0, j=0, ik = 0 ;

// c (count)  hanya sebagai info berapa jumlah prima total yang didapatkan
// pc digunakan sebagai info jumlah array P yang akan digunakan di bawah

int c = n-1;
int pc = n/8;

P adalah array dari unsigned byte (8 bit). Setiap bit-nya akan kita gunakan sebagai info apakah suatu bilangan yang sudah kita cek merupakan prima atau bukan. Disini saya memilih menggunakan byte/char dibandingkan hanya menggunakan boolean karena ini akan menghemat memori menjadi 1/8 nya saja daripada menggunakan boolean. Boolean akan tetap menggunakan 1 byte padahal hanya akan menyimpan info true/false. Contoh penggunaannya, bit ke-2 dari P[0] adalah info apakah 2 itu prima? bit ke-3 dari P[0] adalah info apakah 3 itu prima? dst.. bit ke-1 dari P[0] tentunya
adalah info apakah 9 itu prima?

Disini digunakan dynamic variable, karena kita baru tahu size dari array yang akan diperlukan saat runtime. Inisialisasi array ch[] untuk menyimpan 8 tipe byte yang diperlukan untuk proses pengecekan pada array P[]. Byte-byte tersebut : 00000001, 00000010, … , 10000000. Kemudian, Array P[] di-inisialisasi dengan nilai true semua, jadi nilainya 11111111 = 255

unsigned char* P=0;
P = new unsigned char[pc+1];
unsigned char ch[8];

for (i=0; i<=7; i++)
     ch[i] = 1 << i;

for (i=0; i<=pc; i++)
     P[i] = 255;

Sekarang kita akan mencari daftar bilangan prima dari 2 sampai n. Disini digunakan algoritma Sieve of Eratosthenes, simpelnya algoritma ini bekerja dengan mencoret semua bilangan yang merupakan kelipatan bilangan prima. Kita mulai dengan bilangan prima 2, maka kita akan berjalan dari j = ik = 2^2 = 4 untuk mencoret bilangan 4, kemudian 6, 8, 10, dst.. sampai 120. Kemudian akan dilanjutkan dengan bilangan prima berikutnya yaitu i = 3, dan akan dilakukan yang sama. Sampai pada limit, yaitu akar dari n dibulatkan ke bawah. Pada saat berjalan dari i = 2 sampai limit, tentunya akan ada pengecekan apakah i itu prima, pengecekan dilakukan dengan operasi AND : P[i/8] & ch[i%8]. Ini akan mengecek tempat bit disimpannya info apakah i itu prima pada array P[]. Tentang operasi XOR : P[j/8] ^= ch[j%8], adalah untuk mengeset info bit apakah j itu prima, sehingga bit ke j%8 dari P[j/8] menjadi 0 (false) dan bilangan j sudah tercoret dari list bil. prima. Detail tentang algoritma Sieve of Eratosthenes ini bisa didapatkan infonya di wikipedia.

for (i = 2; i <= limit; i++)
{
  if (P[i/8] & ch[i%8]) {
    ik = i*i;
    for (j = ik; j<=n; j+=i)
       if (P[j/8] & ch[j%8]) {
          P[j/8] ^= ch[j%8];
          c--;
       }
   }
}

Nah, sekarang sudah didapatkan info pada P[] tentang bilangan apa saja dari 2 sampai n yang prima. Sekarang kita tinggal menghitung banyaknya bilangan prima yang berada di antara dua bilangan kuadrat. Caranya cukup simple, yaitu dengan berjalan dari angka 2 sampai n, jika kita cek bit info dari 2 adalah prima maka kita akan menambahkannya (increment) ke variabel penghitung (nsqr) banyaknya bilangan prima antara 1^2 & 2^2, kemudian cek bit info 3, sekarang nsqr = 2, cek bit info 4 maka isqr akan di-increment karena kita sudah melewati batas 2^2-1, jadi jumlahnya 2 untuk 1^2 & 2^2. Sekarang cek untuk 2^2 & 3^2, dimulai dengan bit info 5 yang adalah prima sehingga nsqr=1, bit info 6 bukan prima, bit info 7 prima sehingga nsqr=2, bit info 8 bukan prima, dan kita stop saat pengecekan i=9 karena itu adalah 3^2. Jadi banyaknya kembali hanya 2.

int isqr = 2;
int isqr2 = isqr*isqr;
int nsqr = 0;

for (i=2; i<=n; i++)
	  if (P[i/8] & ch[i%8]) {
		  if (i < isqr2) {
			   cout << i << "\n";
				nsqr++;
		  } else {
			   i--;
				cout << nsqr << " up to " << isqr2 << "\n";
				nsqr = 0;
				isqr++;
				isqr2 = isqr*isqr;
		  }
	  }
cout << nsqr << " up to " << isqr2 << "\n";

// Kita hapus dynamic allocation variable yang sudah dibuat pada awal program
delete [] P;

}

 

Sehingga pada akhirnya di dapatkan daftar seperti ini pada output :

 

Jika n diubah menjadi 1 milyar atau lebih, kita dapat menyimpan hasilnya dalam format text atau file binary, yang kemudian dapat kita analisis hasilnya pada software lain (misalnya : Excel). Dari hasil analisis saya sampai bilangan 100,000,000, terbukti bahwa selalu ada bilangan prima di antara 2 bilangan bulat positif yang berurutan. Dan, info yang paling penting adala semakin besar 2 bilangan bulat positif berurutan, semakin banyak jumlah bilangan prima yang berada diantara kuadrat 2 bilangan tersebut. Tapi ini belum bisa membuktikan secara general conjecture tsb, karena pada bilangan bulat yang sangat besar sekali yang tidak mungkin dicek oleh komputasi, mungkin saja conjecture ini salah.  Demikian artikel singkat saya, ditunggu komentarnya :)

One Response to “Pembuktian Legendre’s Conjecture dengan Teknik Komputasi”
  1. Itu pakai Borland C++ ya? Masalahnya saya sekarang menggunakan windows 64 bit, sehingga tidak bisa membuka Borland C, harus melalui virtual komputer dulu :(

    Ada aplikasi atau emulator gak untuk membuka di 64 bit windows?

  2.  
Leave a Reply