Pada pembentukan urutan dalam hipotesis Collatz (3n + 1)

Saya tertarik pada tugas-tugas seperti masalah Collatz. Mereka mudah untuk merumuskan dan melatih kepala Anda dengan sempurna, terutama pemikiran algoritmik, yang sangat berguna bagi programmer.

Tugas dirumuskan secara sederhana:

Ambil bilangan asli apa saja n. Jika itu genap, maka bagilah dengan 2, dan jika itu ganjil, maka kalikan dengan 3 dan tambahkan 1 (kita dapatkan 3n +1). Kami melakukan tindakan yang sama pada nomor yang dihasilkan, dan seterusnya.

Hipotesis Collatz adalah tidak peduli berapa pun angka awal yang kita ambil, cepat atau lambat kita akan mendapatkannya.

Secara algoritmik, tampilannya seperti ini:

while (number > 1) { if (number % 2 === 0) number = number / 2; else number = 3 * number +1; } 

Misalnya, ambil n = 5. Ini ganjil, yang berarti kita melakukan aksi pada yang ganjil, yaitu, 3n + 1 => 16. 16 genap, itu berarti kita melakukan aksi pada genap, yaitu, n / 2 => 8 => 4 => 2 => 1.
Urutan yang terbentuk pada n = 5: 16, 8, 4, 2, 1.

Saya meminta Anda untuk memaafkan matematika saya, beri tahu saya jika saya membuat kesalahan di suatu tempat.

Marilah kita memilih jumlah total informasi pada unit dan jumlah sebenarnya dari informasi pada unit. Nyatakan langkah-langkah ini.

Pertimbangkan urutan untuk n = 7:

22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Ada 16 langkah secara total, dan langkah - langkah sebenarnya yang benar-benar dilemparkan ke dalam himpunan angka lain adalah 5 di antaranya:

7, 11, 17, 13, 5.

Langkah sebenarnya Sa (n) adalah jumlah operasi 3n + 1 pada nomor yang diperlukan untuk mencapai kesatuan.

Idenya jelas ditunjukkan oleh contoh tabel:

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
2	5	3	17	11	7	9	25	33	43	57	39	105
4	10	6	34	22	14	18	49	65	86	59	78	203
8	20	12	35	23	15	19	50	66	87	114	79	209
16	21	13	68	44	28	36	51	67	89	115	153	210
32	40	24	69	45	Tanggal 29	37	98	130	182	118	156	211
64	42	26	70	46	30	38	99	131	173	119	157	406
128	80	48	75	88	56	72	100	132	174	228	158	407
256	84	52	136	90	58	74	101	133	177	229	305	409
512	85	53	138	92	60	77	102	134	178	230	306	418

Dalam tabel seperti itu, urutan, polanya sendiri, sudah terlihat.
Seperti yang Anda lihat, kekuatan dua tidak akan pernah menjadi aneh, sehingga turun ke pembagian sederhana.
Urutan dari Sa (0) dibentuk oleh hanya 1 rumus.

$$

$$P (0, k) = 2 * 2 ^ k.$$

Tidak ada langkah nyata yang perlu diambil, dengan pembagian sederhana semuanya akan direduksi menjadi satu.
Mengetahui hal ini, Anda dapat menjatuhkan dari tabel semua angka yang merupakan kelipatan dua.

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7)	Sn (8)	Sn (9)	Sn (10)	Sn (11)	Sn (12)
	5	3	17	11	7	9	25	33	43	57	39	105
	21	13	35	23	15	19	49	65	87	59	79	203
	85	53	69	45	Tanggal 29	37	51	67	89	115	153	209
	341	113	75	93	61	77	99	131	173	119	157	211
	1365	213	141	181	117	81	101	133	177	229	305	407

Sekarang lebih sulit untuk menangkap polanya, tetapi ada satu. Yang paling menarik saat ini adalah pembentukan urutan. Tidak hanya seperti itu, angka berikutnya setelah 5 adalah 21, dan setelah itu adalah 85.
Sebenarnya, Sa (1) adalah urutan A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381 ...). Itu dibentuk oleh rumus:

$$

$$P (k) = {4 ^ k- 1 \ lebih dari 3}.$$

Urutan yang sama dapat dijelaskan dengan rumus rekursif:

$$

$$P (k) = 4k_0 +1, dengan \ k_0 = 1.$$

$$$P (1) = 4 * 1 + 1 = 5;$
$$$P (5) = 4 * 5 + 1 = 21;$
$$$P (21) = 4 * 21 + 1 = 85;$
Dan seterusnya ...

Serangkaian langkah pertama dibangun, meskipun dapat terus tanpa batas. Mari kita lanjutkan ke langkah kedua. Formula transisi ke langkah 2 dapat diekspresikan dari rumus ganjil.
Mengetahui bahwa kami akan membagikan hasilnya $$$3n + 1$ beberapa kali, dapat ditulis sebagai $$$2 ^ {2 \ alpha}$ dimana $$$\ alpha$ - jumlah divisi.

$$

$$P (k) = {3n + 1 \ over2 ^ {2 \ alpha}}; \\ 2 ^ {2 \ alpha} P (k) = 3n + 1; \\ 3n = 2 ^ {2 \ alpha} P (k) -1;$$

Rumus akhir berupa:

$$

$$n (P (k), \ alpha) = {2 ^ {2 \ alpha} P (k) -1 \ over3};$$

Kami juga memperkenalkan penyesuaian untuk $$$\ beta$ seperti $$$2 ^ {2 \ alpha + \ beta}$ sehingga opsi untuk membagi angka bukan kelipatan 3 oleh 3 terjadi.

$$

$$n (P (k), \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3};$$

Mari kita periksa rumusnya, karena alpha tidak diketahui, periksa 5 alpha berturut-turut:

$$

$$n (5, \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} * 5-1 \ over3};$$

$$$n (5,0,1) = (2 ^ {0 + 1} * 5-1) /3=3.$
$$$n (5,1,1) = (2 ^ {2 + 1} * 5-1) /3=13.$
$$$n (5,2,1) = (2 ^ 5 * 5-1) /3=53.$
$$$n (5,3,1) = (2 ^ 7 * 5-1) /3=213.$
$$$n (5,4,1) = (2 ^ 9 * 5-1) /3=853.$

Dengan demikian, urutan langkah kedua mulai terbentuk. Namun, dapat dicatat bahwa 113 tidak berurutan, penting untuk diingat bahwa rumus dihitung dari 5 .

n = 113 sebenarnya:
$$$n (85,0,2) = (2 ^ {0 + 2} * 85-1) /3=113.$

Untuk meringkas:

Banyak dari $$$Sa (n + 1)$ dihasilkan oleh fungsi $$$n (P (k), \ alpha, \ beta)$ dari setiap elemen himpunan dari $$$Sa (n)$ .

Kemudian mengetahui ini, Anda masih bisa mempersingkat tabel dengan menghapus semua kelipatan alfa.

Sn (0)	Sn (1)	Sn (2)	Sn (3)	Sn (4)	Sn (5)	Sn (6)	Sn (7) ...
	5	3	17	11	7	9	...
		113	75	201	267	715	...
		227	151	401	1073	1425	...

Untuk memperjelasnya, berikut adalah contoh bagaimana elemen dari suatu himpunan $$$Sa (2)$ menghasilkan elemen set dari $$$Sa (3)$ untuk alpha dari 0 hingga 4.

P (k) = 3	P (k) = 113	P (k) = 227
3 dari α = 0 menghasilkan: Tidak ada 13 dari α = 1 menghasilkan: 17 69 277 1109 4437 53 dari α = 2 menghasilkan: 35 141 565 2261 9045 213 dari α = 3 menghasilkan: Tidak ada 853 dari α = 4 menghasilkan: 1137 4549 18197 72789 291157	113 dari α = 0 menghasilkan: 75 301 1205 4821 19285 453 dari α = 1 menghasilkan: Tidak ada 1813 dari α = 2 menghasilkan: 2417 9669 38677 154709 618837 7253 dari α = 3 menghasilkan: 4835 19341 77365 309461 1237845 29013 dari α = 4 menghasilkan: Tidak ada	227 dari α = 0 menghasilkan: 151 605 2421 9685 38741 909 dari α = 1 menghasilkan: Tidak ada 3637 dari α = 2 menghasilkan: 4849 19397 77589 310357 1241429 14549 dari α = 3 menghasilkan: 9699 38797 155189 620757 2483029 58197 dari α = 4 menghasilkan: Tidak ada

Menggabungkan set ini, kita mendapatkan set dari Sa (3):

17, 35, 69, 75, 141, 151, 277, 301, 565, 605, 1109, 1137, 1205, 2261, 2275, 2417, 2437, 4437, 4549, 4821, 4835, 4849, 9045, 9101, 9669, 9685, 9699, 17749, 18197, 19285, 19341, 19397, 19417 ...

Apalagi menghapus gelar $$$\ alpha> 0$ kami mendapatkan:

17, 75, 151 ...

Artinya, turun ke:

$$

$$n (P (k), \ beta) = {2 ^ \ beta P (k) -1 \ over3};$$

Kenapa di suatu tempat $$$\ beta = 2$ dan di suatu tempat $$$\ beta = 1$ ?

Kembali ke urutan A002450. Ada ketergantungan yang menarik:

$$$P (m) = (4 ^ 3m- 1) / 3$ - tidak menghasilkan urutan anak.
$$$P (m) = (4 ^ {3m + 1} - 1) / 3$ - Menghasilkan urutan anak ketika $$$\ beta = 2$ .
$$$P (m) = (4 ^ {3m + 2} - 1) / 3$ - Menghasilkan urutan anak ketika $$$\ beta = 1$ .

Hanya ada 3 array anak potensial untuk suatu nomor.
Jika diterapkan pada rumus rekursif, maka:

Fungsi $$$n (\ gamma, \ alpha, \ beta)$ dimana $$$\ gamma$ - sembarang nomor kelipatan dari 3 membentuk himpunan kosong ⨂.

$$

$$A (n (\ gamma), \ alpha, \ beta) = ⨂.$$

Fungsi $$$n (\ lambda, \ alpha, \ beta)$ dimana $$$\ lambda$ - nomor apa pun yang dihasilkan $$$\ gamma$ di $$$\ beta = 2$ membentuk himpunan bilangan K milik himpunan bilangan N.

$$

$$K (n (P (\ gamma), \ alpha, 2)) ⊆ N.$$

Fungsi $$$n (P (\ lambda), \ alpha, \ beta)$ di $$$\ beta = 1$ membentuk himpunan bilangan L milik himpunan bilangan asli N.

$$

$$L (n (P (\ lambda), \ alpha, 1)) ⊆ N.$$

Jelas, ini entah bagaimana dapat direduksi menjadi formulasi yang lebih ketat dan berbasis bukti.

Sebenarnya, ini adalah bagaimana urutan terbentuk dalam hipotesis Collatz.
Masih ada satu detail lagi. Kita perlu mengembalikan set lengkap dari langkah absolut dari set yang telah kita peroleh.

Formula untuk Ganjil:

$$

$$n (P (k), \ alpha, \ beta) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3};$$

Selain yang aneh, Anda perlu memulihkan banyak yang genap. Untuk melakukan ini, ingat formula:

$$

$$P (0, k) = 2 * 2 ^ k.$$

Tinggal mengkorelasikan semuanya:

$$

$$n (P (k), \ alpha, \ beta, \ epsilon) = {2 ^ {2 \ alpha + \ beta} P (k) -1 \ over3} * 2 ^ \ epsilon.$$

Versi terakhir:

$$

$$n (k, \ alpha, \ beta, \ epsilon) = 2 ^ \ epsilon {2 ^ {2 \ alpha + \ beta} (4k + 1) -1 \ over3};$$

Dengan demikian, setiap k dapat menghasilkan urutan.

Apakah sebaliknya benar bahwa salah satu bilangan asli pasti milik urutan apa pun dari $$$n (k)$ ?

Jika demikian, maka sangat mungkin bahwa Collatz benar.

Untuk contoh akhir implementasi fungsi javascript:

 function collatsSequence( number, sequenceLength, alpha, epsilon ) { //     , //  number let set = []; //    while (number % 2 === 0) number /= 2; //    , //   number,  sequenceLength for (let k = 0; k < sequenceLength; k++) { //    alpha for (let a = 0; a < alpha; a++) { //  ,  if (number % 3 === 0) break; //   beta = 1 let numWithBeta = (number * 2 ** (2 * a + 1) - 1) / 3; //      3  beta === 1 //     3  beta === 2 if (Math.floor(numWithBeta) !== numWithBeta) //   beta = 2 numWithBeta = (number * 2 ** (2 * a + 2) - 1) / 3; //      epsilon for (let e = 0; e < epsilon; e++) set.push(numWithBeta * 2 ** e); } //      number = number * 4 + 1; } return set; } console.log( collatsSequence(5, 5, 2, 2) ); // [ 3, 6, 13, 26, 113, 226, 453, 906, 227, 454, 909, 1818 ]