Collatz परिकल्पना में अनुक्रम के गठन पर (3n + 1)

मैं Collatz समस्या जैसे कार्यों से आकर्षित हूं। वे आपके सिर को पूरी तरह से तैयार और प्रशिक्षित करना आसान हैं, विशेष रूप से एल्गोरिथम सोच, जो प्रोग्रामर के लिए बहुत उपयोगी है।

कार्य काफी सरल रूप में तैयार किया गया है:

कोई भी प्राकृतिक संख्या n लें। यदि यह सम है, तो इसे 2 से विभाजित करें, और यदि यह विषम है, तो 3 से गुणा करें और 1 जोड़ें (हमें 3n + 1 मिलता है)। हम परिणामी संख्या पर समान कार्य करते हैं, और इसी तरह।

Collatz की परिकल्पना यह है कि कोई भी प्रारंभिक संख्या n नहीं लेता है, हम जितनी जल्दी या बाद में लेंगे, उतना ही हमें मिलेगा।

एल्गोरिथम, ऐसा दिखता है:

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

उदाहरण के लिए, n = 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।

सही चरण सा (n) एकता तक पहुंचने के लिए आवश्यक संख्या पर ऑपरेशन 3n + 1 की संख्या है।

विचार स्पष्ट रूप से एक तालिका के उदाहरण से प्रदर्शित होता है:

Sn (0)	एसएन (1)	एसएन (2)	एसएन (3)	एसएन (4)	एसएन (5)	एसएन (6)	एसएन (7)	एसएन (8)	Sn (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	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

ऐसी तालिका में, आदेश, इसका अपना पैटर्न, पहले से ही दिखाई दे रहा है।
जैसा कि आप देख सकते हैं, दो की शक्ति कभी भी विषम नहीं होगी, इसलिए यह सरल विभाजन की ओर आती है।
Sa (0) से एक अनुक्रम सिर्फ 1 सूत्र द्वारा बनता है।

$$

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

किसी भी सच्चे कदम को उठाने की आवश्यकता नहीं है, सरल विभाजन से सब कुछ एकता में कम हो जाएगा।
यह जानकर, आप तालिका से उन सभी नंबरों को छोड़ सकते हैं जो दो के गुणक हैं।

Sn (0)	एसएन (1)	एसएन (2)	एसएन (3)	एसएन (4)	एसएन (5)	एसएन (6)	एसएन (7)	एसएन (8)	Sn (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	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

अब पैटर्न को पकड़ना अधिक कठिन है, लेकिन एक है सबसे दिलचस्प बात अब अनुक्रमों का गठन है। सिर्फ इतना ही नहीं, 5 के बाद अगला अंक 21 है, और उसके बाद 85 है।
दरअसल, सा (1) क्रम A002450 (0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381 ...) है। यह सूत्र द्वारा बनाया गया है:

$$

$$P (k) = {4 ^ k- 1 \ 3 से अधिक}$$

उसी क्रम को पुनरावर्ती सूत्र द्वारा वर्णित किया जा सकता है:

$$

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

$$$P (1) = 4 * 1 + 1 = 5;$
$$$P (5) = 4 * 5 + 1 = 21;$
$$$P (21) = 4 * 21 + 1 = 85;$
और इसी तरह…

पहले चरण की एक श्रृंखला बनाई गई है, हालांकि यह अनिश्चित काल तक चल सकती है। चलो दो कदम पर चलते हैं। चरण 2 में संक्रमण सूत्र एक विषम सूत्र से व्यक्त किया जा सकता है।
यह जानते हुए कि हम परिणाम साझा करने जा रहे हैं $$$3n + 1$ कई बार, इसे लिखा जा सकता है $$$2 ^ {2 \ अल्फा}$ जहाँ $$$\ अल्फा$ - डिवीजनों की संख्या।

$$

$$P (k) = {3n + 1 \ ओवर 2 ^ {2 \ अल्फा}}; \\ 2 ^ {2 \ अल्फा} पी (के) = 3 एन + 1; \\ 3 एन = 2 ^ {2 \ अल्फा} पी; (k) -1;$$

अंतिम सूत्र रूप लेता है:

$$

$$n (पी (के), \ अल्फा) = {2 ^ {2 \ अल्फा} पी (के) -1 \ ओवर 3} $$$

हम इसके लिए एक समायोजन भी पेश करते हैं $$$\ बीटा$ कैसे $$$2 ^ {2 \ अल्फा + \ बीटा}$ ताकि संख्या को 3 से 3 की संख्या से विभाजित करने का विकल्प न हो।

$$

$$n (पी (के), \ अल्फा, \ बीटा) = {2 ^ {2 \ अल्फा + \ बीटा} पी (के) -1 \ ओवर ३};$$

आइए सूत्र की जांच करें, क्योंकि अल्फा अज्ञात है, लगातार 5 अल्फा के लिए जांचें:

$$

$$n (5, \ अल्फा, \ बीटा) = {2 ^ {2 \ अल्फा + \ बीटा} * 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.$

इस प्रकार, दूसरे चरण का क्रम बनने लगता है। हालांकि, यह ध्यान दिया जा सकता है कि 113 क्रम में नहीं है, यह याद रखना महत्वपूर्ण है कि सूत्र 5 से गणना की गई थी।

n = 113 वास्तव में:
$$$n (85,0,2) = (2 ^ {0 + 2} * 85-1) / 3=113.$

संक्षेप में:

से बहुत $$$सा (n + 1)$ कार्य द्वारा उत्पन्न $$$n (पी (के), \ अल्फा, \ बीटा)$ सेट के प्रत्येक तत्व से $$$सा (n)$ ।

फिर यह जानकर, आप अभी भी अल्फा के सभी गुणकों को हटाकर तालिका को छोटा कर सकते हैं।

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

यह स्पष्ट करने के लिए, यहां एक उदाहरण दिया गया है कि सेट के तत्व कैसे हैं $$$सा (2)$ से सेट के तत्व उत्पन्न करते हैं $$$सा (3)$ अल्फा के लिए 0 से 4 तक।

पी (के) = 3	पी (के) = 113	पी (के) = 227
3 से α = 0 उत्पन्न होता है: कुछ नहीं 13 से α = 1 उत्पन्न होता है: 17 69 277 1109 4437 53 से α = 2 उत्पन्न होता है: 35 141 565 2261 9045 Α = 3 से 213 उत्पन्न होता है: कुछ नहीं Α = 4 से 853 उत्पन्न होता है: 1137 4549 18,197 72,789 291,157	113 α = 0 से उत्पन्न होता है: 75 301 1205 4821 19,285 Α = 1 से 453 उत्पन्न होता है: कुछ नहीं Α = 2 से 1813 उत्पन्न होता है: 2417 9669 38,677 154,709 618,837 Α = 3 से 7253 उत्पन्न होता है: 4835 19341 77365 309,461 1237845 Α = 4 से 29013 उत्पन्न होता है: कुछ नहीं	Α = 0 से 227 उत्पन्न होता है: 151 605 2421 9685 38,741 Α = 1 से 909 उत्पन्न होता है: कुछ नहीं Α = 2 से 3637 उत्पन्न होता है: 4849 19,397 77,589 310,357 1241429 Α = 3 से 14549 उत्पन्न होता है: 9699 38,797 155,189 620,757 2483029 Α = 4 से 58197 उत्पन्न होता है: कुछ नहीं

इन सेटों को मिलाकर, हमें Sa (3) से सेट मिलता है:

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

इसके अलावा, डिग्री को हटाने $$$\ अल्फा> 0$ हमें मिलता है:

17, 75, 151 ...

अर्थात्, यह नीचे आता है:

$$

$$n (पी (के), \ बीटा) = {2 ^ \ बीटा पी (के) -1 \ ओवर 3};$$

कहीं क्यों? $$$\ बीटा = 2$ और कहीं $$$\ बीटा = 1$ ?

A002450 अनुक्रम में वापस। एक दिलचस्प निर्भरता है:

$$$P (m) = (4 ^ 3m- 1) / 3$ - बाल दृश्यों का उत्पादन नहीं करता है।
$$$P (m) = (4 ^ {3m + 1} - 1) / 3$ - जब बच्चे दृश्यों का उत्पादन करता है $$$\ बीटा = 2$ ।
$$$P (m) = (4 ^ {3m + 2} - 1) / 3$ - जब बच्चे दृश्यों का उत्पादन करता है $$$\ बीटा = 1$ ।

एक संख्या के लिए केवल 3 संभावित बाल सरणियाँ हैं।
यदि एक पुनरावर्ती सूत्र पर लागू किया जाता है, तो:

समारोह $$$एन (\ गामा, \ अल्फा, \ बीटा)$ जहाँ $$$गामा$ - 3 के किसी भी संख्या एकाधिक एक खाली सेट 3 बनाता है।

$$

$$ए (एन (गामा), \ अल्फा, \ बीटा) = \ $$

समारोह $$$n (\ lambda, \ Alpha, \ Beta)$ जहाँ $$$\ lambda$ - कोई भी संख्या उत्पन्न $$$गामा$ जब $$$\ बीटा = 2$ प्राकृतिक संख्याओं के समुच्चय से संबंधित संख्याओं के समुच्चय का निर्माण करता है N।

$$

$$K (n (पी (गामा)), \ अल्फा, 2)) n एन$$

समारोह $$$n (पी (लैम्ब्डा), \ अल्फा, \ बीटा)$ जब $$$\ बीटा = 1$ प्राकृतिक संख्या एन के सेट से संबंधित संख्या L का सेट बनाता है।

$$

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

जाहिर है, यह किसी भी तरह अधिक कठोर और साक्ष्य-आधारित सूत्रीकरण के लिए कम किया जा सकता है।

वास्तव में, यह है कि Collatz परिकल्पना में अनुक्रम कैसे बनते हैं।
एक विस्तार बाकी है। हमारे द्वारा प्राप्त किए गए सेट से पूर्ण चरणों से पूर्ण सेट को पुनर्स्थापित करना आवश्यक है।

विषम के लिए सूत्र:

$$

$$n (पी (के), \ अल्फा, \ बीटा) = {2 ^ {2 \ अल्फा + \ बीटा} पी (के) -1 \ ओवर ३};$$

विषम के अलावा, आपको बहुत से लोगों को भी पुनर्स्थापित करने की आवश्यकता है। ऐसा करने के लिए, सूत्र को याद करें:

$$

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

यह केवल सभी को एक साथ सहसंबंधित करने के लिए रहता है:

$$

$$n (पी (के), \ अल्फा, \ बीटा, \ एप्सिलॉन) = {2 ^ {2 \ अल्फा + \ बीटा} पी (के) -1 \ ओवर 3} * 2 ^ \ epsilon। $$$

अंतिम संस्करण:

$$

$$n (के, \ अल्फा, \ बीटा, \ epsilon) = 2 ^ \ epsilon {2 ^ {2 \ अल्फा + \ बीटा} (4k + 1) -1 \ over3};$$

इस प्रकार, कोई भी कश्मीर एक अनुक्रम उत्पन्न कर सकता है।

क्या यह बात सच है कि कोई भी प्राकृतिक संख्या निश्चित रूप से किसी भी क्रम से संबंधित है $$$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 ]