Month: July 2016

‘Perilaku’ Bilangan pada Problem 5n + 1 Versi Kedua

Pada Problem 3n + 1 dan Problem 5n + 1 versi pertama, kita telah menaksir besar perubahan dari xk := ln nk ke xk+1 := ln nk+1:

prob collatz

Untuk L = 5, besar perubahannya positif. Dari bilangan ganjil nk, kita cenderung mendapatkan bilangan ganjil nk+1 yang lebih besar. Karena itu tidak heran bila pada Problem 5n + 1 versi pertama kita peroleh suatu barisan bilangan yang divergen menuju tak terhingga.

Nah, problem untuk Anda sekarang adalah, taksirlah besar perubahan dari xk := ln nk ke xk+1 := ln nk+1, dengan nk menyatakan bilangan asli ke-k yang tak habis dibagi 2 atau 3 dalam barisan bilangan yang diperoleh pada Problem 5n + 1 versi kedua.

*

Bandung, 30-07-2016

Problem 5n + 1 Versi Kedua*

Problem 5n + 1 yang telah diperkenalkan sebelumnya mungkin memang bukan problem yang sekelas dengan Problem 3n + 1. Sebagaimana telah diungkap dalam artikel sebelumnya, Problem 5n + 1 memiliki karakteristik yang berbeda dari Problem 3n + 1. Namun, kita mungkin telah melewatkan sesuatu yang penting: mengapa kita hanya memeriksa apakah n genap (atau habis dibagi 2), sebelum kita menghitung 5n + 1.

Kita semua tahu bahwa 2, 3, dan 5, merupakan tiga bilangan prima pertama. Terkait dengan fakta ini, bagaimana bila kita menghitung 5n + 1 setelah kita memastikan bahwa n tidak habis 2 ataupun 3. Persisnya, mulai dengan suatu bilangan asli n, kita lakukan langkah-langkah berikut secara iteratif:

  • Jika n = 1, hentikan iterasi;
  • Jika n habis dibagi 2, bagilah n dengan 2;
  • Jika n kabis dibagi 3, bagilah n dengan 3;
  • Jika n tidak habis dibagi 2 ataupun 3, kalikan n dengan 5 dan tambahkan 1.
diagram-alir 5n+1

Diagram Alir 5n + 1 Versi Kedua

Berikut adalah beberapa contoh barisan bilangan yang diperoleh untuk beberapa bilangan n berbeda yang dipilih pada iterasi pertama. (Bilangan yang dicetak tebal merupakan bilangan prima, yang penting untuk diperhatikan.)

a. 5, 26, 13, 66, 33, 11, 56, 28, 14, 7, 36, 18, 9, 3, 1.

b. 17, 86, 43, 216, 108, 54, 27, 9, 3, 1.

c. 19, 96, 48, 24, 12, 6, 3, 1.

d. 23, 116, 58, 29, 146, 73, 366, 183, 61, 306, 153, 51, 17, …, 1 (seperti pada b).

e. 25, 126, 63, 21, 7, …, 1 (seperti pada a).

f. 31, 156, 78, 39, 13, …, 1 (seperti pada a).

g. 35, 176, 88, 44, 22, 11, …, 1 (seperti pada a).

h. 37, 186, 93, 31, …, 1 (seperti pada f).

i. 41, 206, 103, 516, 258, 129, 43, …, 1 (seperti pada b).

j. 47, 236, 118, 59, 296, 148, 74, 37, …, 1 (seperti pada h).

Saya belum tahu apakah setiap barisan bilangan yang diperoleh pada “Problem 5n + 1 versi kedua” ini akan berhenti di bilangan 1, seperti pada Problem 3n + 1, atau ada barisan bilangan yang siklik atau divergen, seperti pada Problem 5n + 1 versi pertama. Barangkali ada yang tertarik untuk menelitinya?

*

Bandung, 28-07-2016

Mengapa Problem 3n + 1 Berbeda dari Problem 5n + 1

Anda mungkin masih penasaran dengan Problem 3n + 1 dan Problem 5n + 1: mengapa mereka berbeda. Pada Problem 3n + 1, dimulai dari bilangan asli n berapapun, barisan bilangan yang diperoleh akan berakhir di bilangan 1. Pada Problem 5n + 1, ada barisan yang berakhir di bilangan 1, misalnya 3, 16, 8, 4, 2, 1; ada juga barisan yang siklik, misalnya 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13; dan banyak barisan yang divergen (menuju tak terhingga), misalnya 9, 46, 23, 116, 58, 29, 146, 73, 366, 183, … (sila teruskan sendiri).

Nah, walau belum ada yang bisa membuktikan secara rigor bahwa barisan bilangan yang dihasilkan pada Problem 3n + 1 selalu berakhir di bilangan 1, berikut adalah penjelasan heuristik dari David Speyer, yang sekaligus menjelaskan perilaku barisan bilangan pada Problem 5n + 1 — dan secara umum pada problem Ln + 1, dengan L bilangan ganjil.

Idenya adalah mengamati perubahan dari satu bilangan nk ke bilangan berikutnya nk+1: apakah cenderung membesar atau mengecil. Sebagai contoh, jika suatu bilangan n mempunyai peluang ½ untuk bertambah menjadi n + 3 dan peluang ½ untuk berkurang menjadi n − 1; maka — menurut teori peluang — bilangan tersebut cenderung bertambah menjadi n + 1, ya kan?

Pada problem Ln + 1, dengan L ganjil, setelah kita mendapatkan suatu bilangan ganjil, maka bilangan berikutnya pasti genap. Yang menjadi pertanyaan adalah bilangan berikutnya lagi, setelah bilangan genap itu. Untuk itu, mari kita amati pergerakan dari suatu bilangan ganjil ke bilangan ganjil berikutnya, melalui setidaknya satu bilangan genap (sebagai contoh, pada Problem 5n + 1, dari 9 ke 23 melalui 46, dan dari 23 ke 29 melalui 116 dan 58).

Secara heuristik, dari suatu bilangan ganjil nk, kita akan mendapatkan bilangan ganjil nk+1 = (Lnk + 1)/2 dengan peluang ½, atau nk+1 = (Lnk + 1)/4 dengan peluang ¼, atau nk+1 = (Lnk + 1)/8 dengan peluang 1/8, dan seterusnya. Untuk mengetahui apakah nk+1 lebih besar atau lebih kecil daripada nk, tinjau xk := ln nk. Maka, sebagai hampiran, kita mempunyai xk+1 ≈ xk + ln L − ln 2 dengan peluang ½, atau xk+1 ≈ xk + ln L − 2·ln 2 dengan peluang ¼, atau xk+1 ≈ xk + ln L − 3·ln 2 dengan peluang 1/8, dan seterusnya. Jadi, perkiraan besar perubahan dari xk ke xk+1 adalah:

prob collatz

Nah, sekarang terlihat bahwa untuk L = 3, perubahannya negatif, sedangkan untuk L = 5, perubahannya positif. Jadi kita tidak terkejut mendapati barisan bilangan yang divergen menuju tak terhingga pada Problem 5n + 1. Sebaliknya, kita juga bisa memahami mengapa barisan bilangan pada Problem 3n + 1 cenderung mengecil, dan pada akhirnya berhenti di bilangan 1. (Namun, hitung-hitungan di atas hanya merupakan argumen heuristik, bukan bukti formal. Hingga saat ini, bukti formal untuk Problem 3n + 1 belum ditemukan.)

*

Bandung, 25-07-2016

Problem 5n + 1

Anda telah diperkenalkan dengan Problem 3n + 1. Bagaimana bila sekarang kita bermain dengan bentuk 5n + 1?

Misalkan kita pilih suatu bilangan asli n. Untuk n > 1, kita lakukan operasi berikut secara iteratif:

  • Jika n ganjil, kalikan n dengan 5 dan tambahkan 1.
  • Jika n genap, bagilah n dengan 2.

Iterasi dihentikan bila kita peroleh bilangan 1.

Cobalah Anda bermain dengan beberapa bilangan n, dan amati apa yang terjadi.

Berbeda dengan Problem 3n + 1, barisan bilangan yang diperoleh pada “Problem 5n + 1” ini tidak akan selalu berakhir di bilangan 1. Khususnya, ada beberapa bilangan n yang akan menghasilkan suatu loop. Sebagai contoh, untuk n = 13, kita peroleh barisan bilangan 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13, … (berulang).

Nah, temukan bilangan n lainnya (sebanyak-banyaknya) yang juga menghasilkan loop.

*

Bandung, 23-07-2016

Problem 3n + 1*

Mari kita bermain dengan bilangan asli. Pilih suatu bilangan asli, sebutlah n. Bila n > 1, kita lakukan operasi berikut:

  • Jika n ganjil, kalikan n dengan 3 dan tambahkan 1;
  • Jika n genap, bagilah n dengan 2.

Lakukan operasi di atas secara iteratif terhadap bilangan yang dihasilkan. Iterasi dihentikan bila kita peroleh bilangan 1.

diagram-alir 3n+1

Diagram Alir 3n + 1

Sebagai contoh, misalkan saya memilih n = 3 pada awalnya. Maka, bilangan-bilangan yang akan saya peroleh berikutnya adalah: 10, 5, 16, 8, 4, 2, 1, dan iterasi pun berhenti. Contoh lainnya, bila saya memilih n = 7 pada awalnya, maka bilangan-bilangan berikutnya adalah: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, dan iterasi pun berhenti.

Sila Anda bermain dengan beberapa bilangan n lainnya, dan amati apa yang terjadi. Barisan bilangan yang Anda peroleh pada akhirnya berhenti di 1, ya kan?

Menurut Lothar Collatz (1910-1990), berapa pun bilangan asli n yang kita pilih pada awalnya, barisan bilangan yang diperoleh pada akhirnya akan berhenti di 1.

Tetapi, pernyataan di atas hanya merupakan suatu konjektur, yang dikenal sebagai Konjektur Collatz atau Konjektur 3n + 1, dan problem pembuktiannya (atau penyangkalannya) dikenal sebagai Problem 3n + 1. Hingga saat ini, belum ada orang yang berhasil memecahkan Problem 3n + 1. Mungkin Anda mau mencobanya?

*

Bandung, 21-07-2016

Bukti bahwa e Irasional

Bilangan Euler e yang didefinisikan sebagai jumlah deret

Bukti bahwa e Irasional - 1

merupakan bilangan irasional. Buktinya dapat ditemukan di banyak sumber, termasuk di dunia maya. Bila Anda pernah berkunjung ke blog ariaturns.com yang dikelola oleh Nursatria Vidya Adikrisna, Anda dapat menemukan buktinya di sana.

Sebagai blog matematika, rasanya tak lengkap bila Bermatematika.net tidak membahas irasionalitas bilangan e. So, baiklah, kita akan membahas buktinya di sini. Siapa tahu banyak yang belum pernah mengetahuinya.

Untuk membuktikan bahwa bilangan e irasional, kita gunakan metode reductio ad absurdum, yaitu dengan mengandaikan bahwa e rasional. Dengan pengandaian ini, dan mengingat bahwa e adalah suatu bilangan positif di antara 2 dan 3, bilangan e dapat dituliskan sebagai p/q dengan p dan q bilangan bulat positif, dan q > 1. Jadi, kita mempunyai

Bukti bahwa e Irasional - 2

Nah, sekarang kalikan masing-masing ruas dengan q!, sehingga kita peroleh

Bukti bahwa e Irasional - 3

Perhatikan bahwa q!e = p(q – 1)! dan q!(1 + 1/1! + 1/2! + … + 1/q!) merupakan bilangan bulat positif, sehingga selisihnya seharusnya merupakan suatu bilangan bulat. Namun, kita amati bahwa

Bukti bahwa e Irasional - 4

yang ternyata merupakan bilangan di antara 0 dan 1, bukan suatu bilangan bulat. Jadi kita peroleh suatu kontradiksi, yang bersumber dari pengandaian bahwa e rasional. Karena itu, e mestilah irasional.

*

Bandung, 18-07-2016

Deret Kebalikan Bilangan Prima

Misalkan p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, … adalah bilangan-bilangan prima yang terurut (membesar). Untuk setiap bilangan asli N, kita mempunyai

Deret Kebalikan Bilangan Prima_1

dengan SN adalah himpunan semua bilangan asli yang habis dibagi oleh p1, p2, …, atau pN, tetapi tidak habis dibagi oleh pi, i > N. Karena hasil kali di ruas kiri terhingga, jumlah di ruas kanan pun terhingga. Namun, semakin besar bilangan N, semakin besar himpunan SN dan sehubungan dengan itu semakin besar pula jumlah di ruas kanan. Karena deret harmonik 1 + ½ + ⅓ + ¼ + … divergen, jumlah di ruas kanan membesar ‘tak terbatas’ seiring dengan semakin besarnya N. Jadi hasil kali di ruas kiri pun membesar tak terbatas seiring dengan semakin besarnya N.

Nah, dengan bantuan fakta di atas, Leonhard Euler (1707-1783) membuktikan bahwa deret kebalikan bilangan prima, yaitu

Deret Kebalikan Bilangan Prima_2

merupakan deret yang divergen. Buktinya adalah sebagai berikut. Untuk setiap bilangan asli N, ambil nilai logaritma natural dari kedua ruas kesamaan di atas, dan gunakan sifat logaritma serta uraian deret Maclaurin untuk -ln(1 – x):

Deret Kebalikan Bilangan Prima_3

Andaikan deret kebalikan bilangan prima konvergen, maka deret di ruas kanan konvergen — karena deret jumlah suku-suku lainnya konvergen:

Deret Kebalikan Bilangan Prima-4

Akibatnya himpunan bilangan logaritma di ruas kiri ‘terbatas’. Tetapi ini mustahil, karena hasil kali

Deret Kebalikan Bilangan Prima_5

membesar tak terbatas seiring dengan semakin besarnya N. Karena itu kita simpulkan bahwa deret kebalikan bilangan prima mestilah divergen.

*

Bandung, 14-07-2016

Menghitung ln 3 sebagai Deret

Kita tidak dapat menghitung nilai ln 3 dengan menggunakan deret Maclaurin untuk ln(1 − x) ATAU ln(1 + x) karena kedua deret tersebut hanya berlaku untuk -1 < x < 1 (dengan salah satu titik ujungnya). Namun, kita dapat menghitung ln 3 dengan menggunakan deret untuk ln(1 − x) DAN ln(1 + x). Bagaimanakah caranya?

Deret untuk LN

Catatan. Bahkan, dengan deret untuk ln(1 − x) DAN ln(1 + x), kita dapat pula menghitung nilai ln x untuk sembarang x > 0.

*

Bandung, 11-07-2016

Visualisasi Deret 1/4 + 2/8 + 3/16 + …

Anda tentunya masih ingat deret bilangan 1/4 + 2/8 + 3/16 + … + n/2n+1 + … . Deret ini konvergen ke 1. Nah, pertanyaannya adalah: bila kita menafsirkan suku ke-n dalam deret ini sebagai luas n persegi atau persegi panjang, bagaimana kita dapat menyusun semua persegi atau persegi panjang tersebut sehingga membentuk sebuah persegi yang luasnya 1 satuan luas?

Gambar berikut merupakan salah satu jawabannya (yang sekaligus menjadi bukti tanpa kata-kata untuk kekonvergenan deret di atas).

deret dgn jumlah 1

Visualisasi Deret 1/4 + 2/8 + 3/16 +…

Perhatikan pola dan simetri dalam susunan persegi dan persegi panjang di atas. Cantik kan?

*

Bandung, 02-07-2016