📎 🧑‍🤝‍🧑 👪 حول تشكيل التسلسلات في فرضية Collatz (3n + 1) 🎌 🤾🏼 🍧

لقد انجذبت إلى مهام مثل مشكلة Collatz. من السهل صياغة وتدريب رأسك بشكل مثالي ، وخاصة التفكير الخوارزمي ، وهو أمر مفيد جدًا للمبرمج.

تتم صياغة المهمة ببساطة شديدة:

خذ أي رقم طبيعي ن. إذا كان زوجيًا ، فقم بتقسيمه على 2 ، وإذا كان غريبًا ، فاضربه في 3 وأضف 1 (نحصل على 3n + 1). نقوم بتنفيذ نفس الإجراءات على الرقم الناتج ، وهكذا.

فرضية كولاتز هي أنه بغض النظر عن الرقم الأولي الذي نأخذه ، فسوف نحصل عليه عاجلاً أم آجلاً.

خوارزميات ، يبدو هذا:

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

كمثال ، خذ ن = 5. إنه أمر غريب ، مما يعني أننا نؤدي الإجراء على الفردي ، أي 3n + 1 => 16. 16 حتى ، وهذا يعني أننا نؤدي الإجراء على الزوج ، أي n / 2 => 8 => 4 => 2 => 1.
التسلسل المتكون من n = 5: 16 ، 8 ، 4 ، 2 ، 1.

أطلب منك أن تسامحني على حسابي ، أعلمني إذا أخطأت في مكان ما.

دعونا نفرز العدد الإجمالي للمعلومات عن الوحدة والعدد الحقيقي للمعلومات عن الوحدة. تشير إلى هذه الخطوات.

خذ بعين الاعتبار تسلسل n = 7:

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

هناك 16 خطوة في المجموع ، والخطوات الحقيقية التي تم طرحها بالفعل في مجموعة أرقام أخرى هي 5 منها:

7 ، 11 ، 17 ، 13 ، 5.

الخطوة الحقيقية Sa (n) هي عدد العمليات 3n + 1 على العدد الضروري للوصول إلى الوحدة.

يتم توضيح الفكرة بوضوح من خلال مثال الجدول:

سن (0)	سن (1)	سن (2)	سن (3)	سن (4)	سن (5)	سن (6)	سن (7)	سن (8)	سن (9)	سن (10)	سن (11)	سن (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	التاسع والعشرون	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

في مثل هذا الجدول ، يكون الترتيب ونمطه مرئيًا بالفعل.
كما ترون ، فإن قوة الاثنين لن تصبح غريبة أبدًا ، لذلك يتعلق الأمر بتقسيم بسيط.
يتكون تسلسل Sa (0) من صيغة واحدة فقط.

P (0 ، k) = 2 * 2^{k} .

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

لا يلزم اتخاذ خطوات حقيقية ؛ فبالتقسيم البسيط ، سيتم اختزال كل شيء إلى الوحدة.
بمعرفة هذا ، يمكنك أن تسقط من الجدول جميع الأرقام التي هي مضاعفات اثنين.

سن (1)	سن (2)	سن (3)	سن (4)	سن (5)	سن (6)	سن (7)	سن (8)	سن (9)	سن (10)	سن (11)	سن (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	التاسع والعشرون	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

الآن أصبح التقاط النمط أكثر صعوبة ، ولكن هناك نمط. الشيء الأكثر إثارة للاهتمام الآن هو تشكيل التسلسل. ليس هذا فقط ، الرقم التالي بعد 5 هو 21 ، وبعد 85.
في الواقع ، Sa (1) هو التسلسل A002450 (0 ، 1 ، 5 ، 21 ، 85 ، 341 ، 1365 ، 5461 ، 21845 ، 87381 ...). يتكون من الصيغة:

P (k) = 4^{k} - 1 o v e r 3 .

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

يمكن وصف نفس التسلسل بواسطة صيغة تعاودية:

P (k) = 4 k_{0} + 1 ، م ع k_{0} = 1.

$P (k) = 4k_0 + 1 ، مع \ k_0 = 1.$

P (1) = 4 * 1 + 1 = 5 ؛

$P (1) = 4 * 1 + 1 = 5 ؛$

P (5) = 4 * 5 + 1 = 21 ؛

$P (5) = 4 * 5 + 1 = 21 ؛$

P (21) = 4 * 21 + 1 = 85 ؛

$P (21) = 4 * 21 + 1 = 85 ؛$
وهكذا ...

تم بناء سلسلة من الخطوة الأولى ، على الرغم من أنها يمكن أن تستمر إلى أجل غير مسمى. دعنا ننتقل إلى الخطوة الثانية. يمكن التعبير عن صيغة الانتقال إلى الخطوة 2 من صيغة فردية.
مع العلم أننا سوف نشارك النتيجة

3 n + 1

$3n + 1$ عدة مرات يمكن كتابتها

2^{2 a l p h a}

$2 ^ {2 \ alpha}$ أين

a l p h a

$\ alpha$ - عدد الأقسام.

P (k) = 3 n + 1 o v e r 2^{2 a l p h a} ؛ 2^{2 a l p h a} P (k) = 3 n + 1 ؛ 3 n = 2^{2 a l p h a} P (ك) - 1 ؛

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

تأخذ الصيغة النهائية الشكل التالي:

n (P (k) ، a l p h a) = 2^{2 a l p h a} P (k) - 1 o v e r 3 ؛

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

نقدم أيضا تعديل

ب ي ت ا

$\ بيتا$ مثل

2^{2 a l p h a + b e t a}

$2 ^ {2 \ alpha + \ beta}$ بحيث يحدث خيار قسمة الرقم ليس مضاعف 3 في 3.

n (P (k) ، a l p h a ، b e t a) = 2^{2 a l p h a + b e t a} P (k) - 1 o v e r 3 ؛

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

دعونا نتحقق من الصيغة ، نظرًا لأن ألفا غير معروفة ، تحقق من 5 ألفا متتالية:

n (5 ، a l p h a ، b e t a) = 2^{2 a l p h a + b e t a} * 5 - 1 o v e r 3 ؛

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

n (5 ، 0 ، 1) = (2^{0 + 1} * 5 - 1) / 3 = 3.

$n (5،0،1) = (2 ^ {0 + 1} * 5-1) /3=3.$

n (5 ، 1 ، 1) = (2^{2 + 1} * 5 - 1) / 3 = 13.

$n (5،1،1) = (2 ^ {2 + 1} * 5-1) /3=13.$

n (5 ، 2 ، 1) = (2^{5} * 5 - 1) / 3 = 53.

$n (5،2،1) = (2 ^ 5 * 5-1) /3=53.$

n (5 ، 3 ، 1) = (2^{7} * 5 - 1) / 3 = 213.

$n (5،3،1) = (2 ^ 7 * 5-1) /3=213.$

n (5 ، 4 ، 1) = (2^{9} * 5 - 1) / 3 = 853.

$n (5،4،1) = (2 ^ 9 * 5-1) /3=853.$

وهكذا ، يبدأ تسلسل الخطوة الثانية في التكوين. ومع ذلك ، يمكن ملاحظة أن 113 ليس في تسلسل ، من المهم أن نتذكر أن الصيغة قد تم حسابها من 5 .

ن = 113 في الواقع:

n (85 ، 0 ، 2) = (2^{0 + 2} * 85 - 1) / 3 = 113.

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

لتلخيص:

الكثير من $Sa (n + 1)$ ولدت عن طريق الوظيفة $n (P (k)، \ alpha، \ beta)$ من كل عنصر في المجموعة $Sa (n)$ .

بعد معرفة ذلك ، لا يزال بإمكانك تقصير الجدول عن طريق إزالة جميع مضاعفات ألفا.

سن (1)	سن (2)	سن (3)	سن (4)	سن (5)	سن (6)	سنيور (7) ...
5	3	17	11	7	9	...
	113	75	201	267	715	...
	227	151	401	1073	1425	...

لتوضيح الأمر ، إليك مثال لكيفية عناصر من مجموعة

S a (2)

$Sa (2)$ توليد عناصر المجموعة من

S a (3)

$Sa (3)$ لألفا من 0 إلى 4.

ع (ك) = 3	ع (ك) = 113	ع (ك) = 227
3 من α = 0 يولد: لا شيء 13 من α = 1 ينتج: 17 69 277 1109 4437 53 من α = 2 يولد: 35 141 565 2261 9045 213 من α = 3 ينتج: لا شيء 853 من α = 4 ينتج: 1137 4549 18197 72789 291157	113 من α = 0 يولد: 75 301 1205 4821 19285 453 من α = 1 ينتج: لا شيء 1813 من α = 2 يولد: 2417 9669 38677 154709 618837 7253 من α = 3 ينتج: 4835 19341 77365 309461 1237845 29013 من α = 4 ينتج: لا شيء	227 من α = 0 يولد: 151 605 2421 9685 38741 909 من α = 1 ينتج: لا شيء 3637 من α = 2 ينتج: 4849 19397 77589 310357 1241429 14549 من α = 3 ينتج: 9699 38797 155189 620757 2483029 58197 من α = 4 يولد: لا شيء

من خلال الجمع بين هذه المجموعات ، نحصل على المجموعة من Sa (3):

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

علاوة على ذلك ، إزالة الدرجة

a l p h a > 0

$\ alpha> 0$ نحصل على:

17 ، 75 ، 151 ...

أي أن الأمر يتعلق بما يلي:

n (P (k) ، b e t a) = 2^{} b e t a P (k) - 1 o v e r 3 ؛

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

لماذا في مكان ما

$\ بيتا = 2$ وفي مكان ما

$\ بيتا = 1$ ؟؟؟

الرجوع إلى التسلسل A002450. هناك تبعية مثيرة للاهتمام:

P (m) = (4^{3} m - 1) / 3

$P (m) = (4 ^ 3m- 1) / 3$ - لا ينتج تسلسل فرعي.

P (m) = (4^{3 m + 1} - 1) / 3

$P (m) = (4 ^ {3m + 1} - 1) / 3$ - ينتج تسلسل تابع عندما

ب ي ت ا = 2

$\ بيتا = 2$ .

P (m) = (4^{3 m + 2} - 1) / 3

$P (m) = (4 ^ {3m + 2} - 1) / 3$ - ينتج تسلسل تابع عندما

ب ي ت ا = 1

$\ بيتا = 1$ .

هناك 3 صفائف طفل محتملة فقط لرقم.
إذا تم تطبيقه على صيغة تعاودية ، فعندئذٍ:

الوظيفة $n (\ gamma، \ alpha، \ beta)$ أين $\ gamma$ - أي عدد مضاعف لـ 3 يشكل مجموعة فارغة ⨂.
$A (n (g a m m a) ، a l p h a ، b e t a) = ⨂ .$
$A (n (\ gamma)، \ alpha، \ beta) = ⨂.$

الوظيفة $n (\ lambda، \ alpha، \ beta)$ أين $\ lambda$ - أي رقم تم إنشاؤه $\ gamma$ في $\ بيتا = 2$ تشكل مجموعة الأعداد K التي تنتمي إلى مجموعة الأعداد الطبيعية N.
$K (n (P (g a m m a) ، a l p h a ، 2)) \subseteq N .$
$K (n (P (\ gamma)، \ alpha، 2)) ⊆ N.$

الوظيفة $n (P (\ lambda)، \ alpha، \ beta)$ في $\ بيتا = 1$ تشكل مجموعة الأعداد L التي تنتمي إلى مجموعة الأعداد الطبيعية N.
$L (n (P (l a m b d a) ، a l p h a ، 1)) \subseteq N .$
$L (n (P (\ lambda)، \ alpha، 1)) ⊆ N.$

من الواضح أنه يمكن اختزال هذا بطريقة أو بأخرى إلى صيغة أكثر صرامة وقائمة على الأدلة.

في الواقع ، هذه هي الطريقة التي تتشكل بها التسلسلات في فرضية Collatz.
هناك تفاصيل واحدة متبقية. من الضروري استعادة مجموعات كاملة من الخطوات المطلقة من المجموعات التي حصلنا عليها.

صيغة الغريب:

n (P (k) ، a l p h a ، b e t a) = 2^{2 a l p h a + b e t a} P (k) - 1 o v e r 3 ؛

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

بالإضافة إلى تلك الفردية ، تحتاج إلى استعادة الكثير منها. للقيام بذلك ، تذكر الصيغة:

P (0 ، k) = 2 * 2^{k} .

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

يبقى فقط لربط كل شيء معًا:

n (P (k) ، a l p h a ، b e t a ، e p s i l o n) = 2^{2 a l p h a + b e t a} P (k) - 1 o v e r 3 * 2^{} e p s i l o n .

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

النسخة النهائية:

n (k ، a l p h a ، b e t a ، e p s i l o n) = 2^{} e p s i l o n 2^{2 a l p h a + b e t a} (4 k + 1) - 1 o v e r 3 ؛

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

وبالتالي ، يمكن لأي k توليد تسلسل.

هل العكس صحيح أن أيًا من الأعداد الطبيعية ينتمي بالتأكيد إلى أي تسلسل من $n (k)$ ؟؟؟

إذا كان الأمر كذلك ، فمن المحتمل تمامًا أن Collatz كان على حق.

للحصول على المثال الأخير لتنفيذ وظيفة جافا سكريبت:

 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 ]

حول تشكيل التسلسلات في فرضية Collatz (3n + 1)

More articles: