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 dibagi 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

Advertisements

6 comments

  1. Fajar Yuliawan (via FB): Definisikan f:N->N dengan cara f(1)=1, f(n)=n/2 jika n genap, f(n)=n/3 jika n ganjil dan habis dibagi 3 dan f(n)=5n+1 jika n ganjil dan tidak habis dibagi 3.

    Misalkan k>1 bilangan asli, kita formulasikan dua konjektur terkait k:

    Konjektur 1(k). Untuk setiap bilangan asli n<=k, terdapat m sehingga f(f(…f(n)…))=1 (komposisi m kali).

    Konjektur 2(k). Untuk setiap bilangan asli n dengan 1<n<=k, terdapat m sehingga f(f(…f(n)…))1, Konjektur 1(k) dan 2(k) ekuivalen.

    Sekarang kita analisa konjektur 2. Untuk bilangan asli n>1 dengan n=0,1,2,3,4 (mod 6) berlaku f(f(f(f(n))))1, definisikan h(n) sebagai bilangan asli terkecil sehingga f(f(…f(n)…))<n (komposisi sebanyak h(n) kali). Sebagai contoh h(2)=h(3)=1, h(4)=h(6)=h(9)=2, dan h(5)=13:
    barisan f(5), f(f(5)), f(f(f(5))),… adalah sebagai berikut 26, 13, 66, 33, 11, 56, 28, 14, 7, 36, 18, 9, 3, 1, 1, 1, …
    Tentu saja definisi di atas bukan defini yang baik karena kita belum tahu apakah konjektur 2 berlaku, namun kita abaikan hal ini karena kita hanya tertarik dengan masalah komputasi. Dengan menggunakan program komputer, diperoleh

    h(n) < 13 untuk n < 5 dan h(5) = 13
    h(n) < 28 untuk n < 95 dan h(95) = 28
    h(n) < 29 untuk n < 317 dan h(317) = 29
    h(n) < 73 untuk n < 383 dan h(383) = 73
    h(n) < 96 untuk n < 10463 dan h(10463) = 96
    h(n) < 116 untuk n < 44183 dan h(44183) = 116
    h(n) < 140 untuk n < 986231 dan h(986231) = 140
    h(n) < 166 untuk n < 12447533 dan h(12447533) = 166
    h(n) < 166 untuk n < 10^8

    Dengan demikian, konjektur 2 (10^8) berlaku sehingga konjektur 1 (10^8) juga berlaku.

    Liked by 1 person

  2. Fajar Yuliawan (via FB): utk mengecek sampai 10^9 misalnya, perlu > 10 kali waktu utk 10^8. Malas menunggu selesai eksekusi programnya. Kalau ada yg mau utak-atik utk optimasi, saya bisa share. Saya pakai bhs python 3.

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s