Catatan si Jay

September 20, 2010

Algoritma Pembagian 2 : Pembahasan FakPos

Filed under: Algoritma, Matematika, Puzzle, Teori Bilangan — Hendra Jaya @ 6:53 am

Obat ngantuk 1

Jika dituliskan ke dalam bentuk perkalian faktor (a . b), 24 dapat dituliskan sebagai :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&24\\2&|&2&.&12\\3&|&3&.&8\\4&|&4&.&6\end{array}

Perhatikan bahwa dalam bentuk perkalian di atas (a . b),  terdapat beberapa pola :

  1. a\leq b
  2. a_1<a_2<a_3<a_4 ...
  3. b_1>b_2>b_3>b_4 ...

Dan jika dihitung, maka pada data di atas terdapat 4 buah baris dan 2 buah kolom. Sehingga siapapun dapat menghitung dengan cepat banyaknya elemen dalam “tabel”. Tinggal kalikan jumlah baris dan jumlah kolom maka akan diperoleh banyaknya elemen, yaitu 8.

Dengan cara yang sama, 84 juga dapat dituliskan ke dalam bentuk perkalian faktor (a . b) :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&84\\2&|&2&.&42\\3&|&3&.&28\\4&|&4&.&21\\5&|&6&.&14\\6&|&7&.&12\end{array}

Sehingga banyaknya elemen dalam “tabel” juga dapat diperoleh dengan mengalikan jumlah baris dan jumlah kolom. Untuk 84, terdapat 6 baris dan “so pasti” 2 kolom. Sehingga banyaknya elemen yang ada di dalam “tabel” adalah 12.

Karena “2 kolom” adalah suatu keterjadian (hal yang mutlak), maka – jika direpresentasikan ke dalam bentuk tabel perkalian faktor semua bilangan pasti memiliki jumlah elemen dalam bentuk 2 . baris, yaitu suatu bilangan genap. Sayangnya, jumlah elemen di dalam tabel tidak merepresentasikan jumlah faktor yang sebenarnya. Karena, tabel “perkalian faktor” ini tidak menjamin keunikan/uniqueness dari elemen-elemen yang ada.

“Mengapa setiap faktor harus unik?”
Untuk memahaminya, silahkan bayangkan jika anda diperbolehkan untuk menuliskan faktor secara tidak unik. Untuk angka 24, anda dapat menuliskan faktornya sebagai 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, …. 24. Totalnya ada tidak terhingga banyaknya faktor.

Setelah memahami sifat “unik” dari setiap faktor dengan faktor lainnya, sebuah pertanyaan kritis akan muncul.

“Apakah mungkin elemen-elemen pada tabel perkalian faktor tidak unik?”
Mungkin saja, yaitu ketika a=b. Sebagai contoh, angka 25, jika direpresentasikan ke dalam tabel perkalian faktor adalah sebagai berikut :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&25\\2&|&5&.&5\end{array}

Jumlah elemen pada tabel perkalian faktor adalah 4 (genap dan akan selalu genap) sementara jumlah faktor yang sebenarnya adalah 3, yaitu 1, 5, dan 25.

Pertanyaan berikutnya yang mungkin muncul adalah “Berapa kali kasus a = b muncul?”
Konstrain a_1<a_2<a_3<a_4<... secara implisit mengatakan bahwa b_1>b_2>b_3>b_4...  Sekarang, misalkan kasus a=b pertama kali terjadi di baris ke-lima, yaitu pada a_5=b_5 .

Apakah mungkin di baris-baris berikutnya kasus a=b terulang kembali?
Setelah baris ke-lima kita tentu menemui baris ke-enam. Di baris ke-enam akan muncul a_6 yang lebih besar dari a_5, yakni a_6>a_5. Dan akan muncul pula b_6 yang lebih kecil dari b_5, yakni b_5>b_6.

Karena a_5=b_5=m , maka a_6>m>b_6. Suatu hal yang tidak boleh kita lakukan karena di setiap baris kita sudah menyepakati bahwa a\leq b. Dengan demikian, jika kasus a=b terjadi di baris ke-lima dapat dipastikan tidak akan ada baris lagi di bawah baris ke-lima. Atau secara umum dapat kita katakan kasus a=b hanya bisa terjadi maksimal satu kali, dan jika hal itu terjadi di baris ke-n maka pasti n adalah baris terbawah.

Dengan demikian, dapat disimpulkan bahwa kasus ketidak-unikan elemen yang menyebabkan keganjilan jumlah faktor hanya akan muncul di saat baris terbawah dari tabel perkalian faktor-nya dalam bentuk a=b.

Sekarang, apa makna dari a=b? Makna dari a=b adalah bilangan yang dimaksud (c) dapat dituliskan ke dalam bentuk c=a.b=a.a=b.b=a^2=b^2 . Yaitu sebuah bilangan kuadrat. Dengan demikian, kasus keganjilan jumlah faktor hanya akan muncul pada saat c adalah sebuah bilangan kuadrat.

Tour Accounting

Obat Ngantuk 2

Faktor-faktor untuk 1 dapat dituliskan sebagai :

1 = 1

Faktor-faktor untuk 2, yakni 2^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\end{array}

Faktor-faktor untuk 4, yakni {2}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\end{array}

Faktor-faktor untuk 8, yakni {2}^{3}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\end{array}

Faktor-faktor untuk 24, yakni 2^3.3^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\end{array}

Faktor-faktor untuk 72, yakni {2}^{3}.{3}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\\9&=&1.3^2\\18&=&1.2^1.3^2\\36&=&1.2^2.3^2\\72&=&1.2^3.3^2\end{array}

Catatan : Penulisan faktor di atas dilakukan terurut berdasarkan “kedatangan” faktor prima dan pangkatnya.

Apakah ada pola-nya?
Ada, yaitu :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1 ataupun 2^2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3^1
  • dst..

Tanpa mengurangi kebenarannya, kita modifikasi sedikit menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan bilangan yang mengandung 3
  • dst..

Sekarang, kita tambahkan sedikit logika.

Ketika 2^1 datang (step 2), belum ada bilangan yang mengandung 2. Begitu juga ketika 3^1 datang (step 4), belum ada bilangan yang mengandung 3. Sehingga, tanpa mengurangi kebenarannya, pola yang terbentuk dapat kita tulis ulang lagi menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • dst..

Nah akhirnya terbentuk satu pola yang sangat mudah dibaca. Ketika 2^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 2. Begitu juga ketika 3^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 3.

Sehingga, secara umum, ketika p^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung p.

Sekarang kita tulis lagi pola kita :

  • Tentukan 1 sebagai awalan.
  • Ketika 2 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2.
  • Ketika 3 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 3.
  • dst..

Misalkan “anggota keluarga” 2 ada k buah, maka :

  • Ketika 1 ditentukan sebagai awalan, jumlah faktor = 1
  • Ketika 2^1 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^2 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^3 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^k datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1

Mengapa semua “anggota keluarga” 2 hanya mau dikalikan dengan satu buah faktor, yaitu 1? Karena mereka takut terjadi “incest”, yaitu perkawinan dengan bilangan “sedarah”, yaitu bilangan yang mengandung angka 2. Hanya ada 1 faktor yang pasti tidak “sedarah” dengan mereka, yaitu 1. Karena perkawinan ini terjadi sebanyak k kali, maka total faktor sekarang ada k+1.

Misalkan “anggota keluarga” 3 ada l buah. Serupa dengan 2, semua bilangan “berdarah” 3 mengharamkan “incest” dan dengan demikian :

  • Ketika 3^1 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^2 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^3 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^l datang, dia hanya mau dikawinkan dengan k+1 buah bilangan

Karena terjadi l kali perkawinan, maka total bilangan baru adalah l.(k+1). Dan jika ditambahkan dengan yang sebelumnya, yaitu k+1. Maka total bilangan (faktor) sekarang adalah l.(k+1)+(k+1)=(l+1).(k+1)

Jika dituliskan ulang polanya menjadi :

  • 1 (awalan)
  • k.1+1=(k+1)
  • l.(k+1)+(k+1)=(l+1).(k+1)
  • m.(l+1).(k+1)+(l+1).(k+1)=(m+1).(l+1).(k+1)
  • dst..

Kesimpulan :

  1. Banyaknya faktor dapat dihitung dengan tepat tanpa harus mengetahui faktor-faktornya.
  2. Banyaknya faktor tidak tergantung kepada faktor prima-nya. Alih-alih, tergantung kepada “pangkat” dari faktor prima-nya.

Technical Jibba-Jabba :

Pseudo-Code :

function FakPos([exp], lower, upper)
  result = 1
  for each i in lower to upper exclusive
    result = result * (1 + exp[i])
  return result

Implementasi Java : Ideone
Implementasi C++ : Sabar subur

Validitas algoritma ini cocok dengan fungsi d(n) seperti dijelaskan pada divisor function.

Secara matematis, FakPos(n) atau d(n) dirumuskan sebagai : d(n)=\prod_{i=1}^{r}(e_i + 1) dimana e_i adalah pangkat/eksponen dari faktor prima ke-i dari n.

Number Order

Tinggalkan sebuah Komentar »

Belum ada komentar.

RSS feed for comments on this post. TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Blog di WordPress.com.

%d blogger menyukai ini: