الفصائل القابلة للقسمة

في الآونة الأخيرة ، شعرت بالحيرة تجاه هذه التغريدة من Farm Library:


"هذا ما يحدث إذا كنت لا تتكاثر ولكن تنقسم إلى العامل".

عندما رأيته ، اضطررت إلى التخلي عن أعمالي ، والاستيلاء على جهاز كمبيوتر محمول والتحقق من الصيغة. مشروع النتيجة بدا منطقيا. منذ النسخة المضاعفة $$$n!$ مع زيادة $$$ن$ يميل إلى ما لا نهاية ، ثم النسخة "تقسيم" يجب أن تميل إلى الصفر. و $$$\ frac {n ^ 2} {n!}$ يتصرف بهذه الطريقة وظيفة متعددة الحدود $$$n ^ 2$ ينمو أبطأ من وظيفة السلطة $$$n!$ كبيرة بما يكفي $$$ن$ :

$$

$$\ frac {1} {1} ، \ frac {4} {2} ، \ frac {9} {6} ، \ frac {16} {24} ، \ frac {25} {120} ، \ frac {36 } {720} ، \ frac {49} {5040} ، \ frac {64} {40320} ، \ frac {81} {362880} ، \ frac {100} {3628800}$$

ولكن لماذا تأخذ نتيجة التقسيم النموذج $$$\ frac {n ^ 2} {n!}$ ؟ من أين تأتي؟ $$$n ^ 2$ ؟

للإجابة على هذا السؤال ، اضطررت إلى تفكيك الصدمة القديمة المرتبطة بدراسة الانقسام الكسري ، لكنني تعاملت مع الألم. بالانتقال من صيغة tweet من اليسار إلى اليمين ، سنحصل أولاً $$$\ frac {n} {n-1}$ . ثم ، قسمة هذه القيمة على $$$ن -2 دولا$ نحن نحصل عليها

$$

$$\ cfrac {\ frac {n} {n-1}} {n-2} = \ frac {n} {(n-1) (n-2)}$$

استمرارًا بهذه الطريقة ، ينتهي بنا الأمر بـ:

$$

$$n \ mathbin {/} (n-1) \ mathbin {/} (n-2) \ mathbin {/} (n-3) \ mathbin {/} \ cdots \ mathbin {/} 1 = \ frac {n } {(n-1) (n-2) (n-3) \ cdots 1} = \ frac {n} {(n-1)!}$$

للحصول على النتيجة المبينة في تغريدة $$$\ frac {n ^ 2} {n!}$ ، نحن نضرب البسط والمقام ب $$$ن$ . (على الرغم من ذوقي ، التعبير $$$\ frac {n} {(n-1)!}$ أكثر وضوحا.)

---

أنا معجب بحزب فصيل معترف به رسميًا. حافظ على تسلسلات فيبوناتشي معك ؛ هنا هو ميزة بلدي المفضل. في كل مرة أتعلم فيها لغة برمجة جديدة ، أول تمرين لي هو كتابة العديد من الإجراءات لحساب المصانع. على مر السنين ، توصلت إلى العديد من الأشكال المختلفة لهذا الموضوع ، على سبيل المثال ، بديل في التعريف $$$\ مرات$ على $$$+$ (والذي يعطينا أرقام ثلاثية). ولكن يبدو أنني لم أفكر في استبدال من قبل $$$\ مرات$ على $$$\ mathbin {/}$ . اتضح غريب. نظرًا لأن الضرب التبادلي والنقابي ، يمكننا تحديد $$$n!$ تماما مثل المنتج من جميع الأعداد الصحيحة من $$$1$ قبل $$$ن$ دون الحاجة إلى القلق بشأن ترتيب العمليات. ولكن عند القسمة ، لا يمكن تجاهل الأمر. في الحالة العامة $$$x \ mathbin {/} y \ ne y \ mathbin {/} x$ و $$$(x \ mathbin {/} y) \ mathbin {/} z \ ne x \ mathbin {/} (y \ mathbin {/} z)$ .

في تغريدة مكتبة المزرعة ، يتم تقسيم الفواصل بترتيب تنازلي: $$$n ، n-1 ، n-2 ، \ ldots ، $$ . من الواضح أنه سيتم استبدال ذلك بترتيب تصاعدي: $$$1 ، 2 ، 3 ، \ ldots ، n$ . ماذا يحدث إذا عرفنا عامل التقسيم بأنه $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ ؟ عودة أخرى إلى خوارزمية تقسيم كسور المدرسة يعطينا إجابة بسيطة:

$$

$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n = \ frac {1} {2 \ times 3 \ times 4 \ times \ cdots \ times n} = \ \ frac {1} {n!}$$

بعبارة أخرى ، عندما نقوم بالتقسيم عدة مرات ، نقوم بالعد من $$$1$ قبل $$$ن$ ، والنتيجة النهائية ستكون مساوية للمثل $$$n!$ . (أرغب في وضع علامة تعجب في نهاية هذه الجملة ، ولكن للأسف!) إذا كنت تبحث عن إجابة قانونية عن السؤال "ما الذي نحصل عليه عند القسمة بدلاً من الضرب في $$$n!$ ؟ "، ثم أود أن أقول ذلك $$$\ frac {1} {n!}$ هو مرشح أفضل من $$$\ frac {n} {(n - 1)!}$ . لماذا لا نقبل التماثل بينهما $$$n!$ وقيمتها معكوسة؟

بالطبع ، هناك العديد من الطرق الأخرى لوضع قيم عدد صحيح في المجموعة $$$\ {1 \ ldots n \}$ . لكن كم بالضبط؟ كما اتضح ، بالضبط $$$n!$ ! لذلك ، قد يبدو أن هناك $$$n!$ طرق فريدة لتحديد وظيفة التقسيم $$$n!$ . ومع ذلك ، فإن دراسة إجابات التباديلين الموضحين أعلاه تجعلنا نفهم أن نمطًا أبسط يعمل هنا. أيًا كان عنصر التسلسل يظهر أولاً ، يظهر في البسط لكسر كبير ، ويكون ناتج جميع العناصر الأخرى هو المقام. لذلك ، في النهاية ، هناك فقط $$$ن$ نتائج مختلفة (على افتراض أننا نقوم دائمًا بإجراء عمليات التقسيم بدقة من اليسار إلى اليمين). لأي عدد صحيح $$$ك$ في النطاق من $$$1$ قبل $$$ن$ عن طريق الإعداد $$$ك$ في بداية السطر ، نقوم بإنشاء تقسيم $$$n!$ يساوي $$$ك$ مقسوما على جميع العوامل الأخرى. يمكنك كتابة هذا على النحو التالي:

$$

$$\ cfrac {k} {\ frac {n!} {k}} ، \ text {والتي يمكن تحويلها إلى} \ frac {k ^ 2} {n!}$$

ولذا فقد حللنا بعض الألغاز حول كيفية استخدام هذه التغريدة $$$\ frac {n} {(n-1)!}$ تحولت إلى $$$\ frac {n ^ 2} {n!}$ .
تجدر الإشارة إلى أن كل هذه الوظائف تتقارب إلى الصفر عند $$$ن$ إلى ما لا نهاية. من وجهة نظر تقارب ، $$$\ frac {1 ^ 2} {n!} ، \ frac {2 ^ 2} {n!} ، \ ldots ، \ frac {n ^ 2} {n!}$ متطابقة.

---

نعم المهمة أنجزت. تم حل المشكلة. تم الانتهاء من المهمة. الآن نحن نعرف كل ما نحتاجه حول تقسيم الفصائل ، أليس كذلك؟

حسنًا ، ربما يوجد سؤال آخر. ماذا سيقول الكمبيوتر؟ إذا أخذنا خوارزمية مفضلة لدينا ، وقمنا بما هو مقترح في تغريدة ، فاستبدل كل تكرارات المشغل $$$\ مرات$ (أو * ) على / ، ماذا سيحدث؟ أي من $$$ن$ خيارات التقسيم $$$n!$ هل سيعطينا البرنامج؟

إليكم الخوارزمية المفضلة لحساب الفصائل كبرنامج على جوليا :

 function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end end 

قدمت هذه الخوارزمية أجيال كاملة من المهووسين لمفهوم العودية. في شكل نص ، فإنه يقرأ: إذا $$$ن$ يساوي $$$1$ اذن $$$mul! (n)$ يساوي $$$1$ . خلاف ذلك ، تحتاج إلى حساب الوظيفة $$$mul! (n-1)$ ثم اضرب النتيجة ب $$$ن$ .

_{قد تسأل ماذا يحدث إذا} $$_{$ن$ سيكون صفر أو سلبي. يمكنك أن تسأل ، لكن من الأفضل عدم ذلك. لأهدافنا الحالية} $$_{$n \ in \ mathbb {N}$ .}

بدءا من أي إيجابية $$$ن$ ، تسلسل المكالمات العودية سوف تنخفض عاجلاً أم آجلاً إلى $$$ن = 1 دولا$ .

يمكن كتابة الوظيفة بشكل أكثر إيجازًا باستخدام نمط تعريف جوليا أحادي السطر:

 mul!(n) = n == 1 ? 1 : n * mul!(n - 1) 

هل الجزء الأيمن من عامل التعيين تعبير شرطي ، أو عامل الثلاثي للنموذج a ? b : c a ? b : c . هنا الحالة الشرطية للاختبار ، والتي يجب أن تُرجع إما true أو false . إذا كان a true ، فسيتم تقييم التعبير b ، وتصبح النتيجة هي قيمة التعبير بالكامل. خلاف ذلك ، c حساب c .

فقط للتأكد من أنني فعلت كل ما هو صواب ، فيما يلي أول عشرة فصائل محسوبة بواسطة هذا البرنامج:

 [mul!(n) for n in 1:10] 10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 

الآن ، دعونا نغير هذا التعريف ونحول التكرار الوحيد * في / ، مع ترك كل شيء آخر دون تغيير (باستثناء اسم الوظيفة).

 div!(n) = n == 1 ? 1 : n / div!(n - 1) 

وهذا هو ما سيعود البرنامج إذا قمنا بتشغيله من أجل القيم $$$ن$ من $$$1$ قبل $$ :

 [div!(n) for n in 1:20] 20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418 

ماذا؟ بالتأكيد ليس مثل التقارب إلى الصفر ، تمامًا مثل $$$\ frac {1} {n!}$ او $$$\ frac {n} {n - 1}$ . في الواقع ، لا تبدو القيم هكذا ، لأنها لن تتقارب. بناءً على الرسم البياني أدناه ، يتكون التسلسل من مكونين متقطعين ، يبدو أن كل منهما ينمو ببطء نحو اللانهاية ، وينحرف أيضًا عن الآخر.


فهم ما نلاحظه هنا ، سيكون من المفيد تغيير نوع مخرجات دالة div! . بدلاً من استخدام معامل القسمة / ، والتي تُرجع القيمة كرقم الفاصلة العائمة ، يمكننا استبدالها // التشغيل // ، الذي يُرجع القيمة المنطقية الدقيقة ، مقربًا إلى الحد الأدنى.

 div!(n) = n == 1 ? 1 : n // div!(n - 1) 

في ما يلي سلسلة من القيم لـ n 1:20 :

 20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189 

القائمة مليئة أنماط مثيرة للاهتمام. هذا هو الحلزون المزدوج الذي تتحرك فيه الأرقام الفردية والزوجية في متعرج. حتى الأرقام ليست فقط متساوية ، فهي كلها درجات $$ . بالإضافة إلى ذلك ، تظهر في أزواج - أولاً في البسط ، ثم في المقام - وتسلسلها غير متناقص. ولكن هناك فجوات. ليس كل الدرجات موجودة $$ . يبدو الخيط الغريب أكثر تعقيدًا ، وتظهر معاملات بسيطة صغيرة مختلفة وتختفي في الأرقام. ( يجب أن تكون الأعداد الأولية صغيرة ، على الأقل أقل $$$ن$ .)

هذه النتيجة فاجأتني. توقعت أن أرى تسلسلًا أكثر تماثلاً ، مثل تلك التي حسبتها على الورق. كل هذه القفزات صعودا وهبوطا لا معنى له. الاتجاه العام نحو نمو غير محدود في النسبة لم يكن له معنى أيضا. كيف يمكننا أن نقسم باستمرار ، مع تلقي جميع الأعداد الأكبر والأكبر؟

في هذه المرحلة ، يمكنك التوقف مؤقتًا عن القراءة ومحاولة الخروج بنظرية خاصة بك حول مصدر هذه الأعداد المتعرجة. إذا كنت بحاجة إلى تلميح ، فستجده قويًا للغاية ، وهو المفسد تقريبًا: ابحث عن سلسلة من البسط أو تسلسل القواسم في موسوعة Online Integer Sequences على الإنترنت .

---

هنا هو فكرة أخرى. تغيير بسيط في برنامج div! يحول تماما الإخراج. فقط قم بتغيير التعبير الأخير عن طريق استبدال n // div!(n - 1) بـ div!(n - 1) // n .

 div!(n) = n == 1 ? 1 : div!(n - 1) // n 

الآن تبدو النتائج كما يلي:

 10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800 

هذه هي الوظيفة العكسية للعنصر الذي رأيناه بالفعل ، سلسلة من القيم الناتجة عن الانتقال من اليسار إلى اليمين في سلسلة متزايدة من المقسومات $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ .

ليس من المستغرب أن يؤدي تغيير التعبير الأخير في إجراء إلى تغيير النتيجة. في النهاية ، نعلم أن الانقسام ليس تبادلاً أو نقابيًا. ولكن من الصعب أن نفهم لماذا يعطي تسلسل القيم المتولدة من البرنامج الأصلي مثل هذا الشكل المتعرج الغريب. ما هي الآلية التي تؤدي إلى ظهور هذه القوى المزدوجة وتناوب القيم الفردية والزوجية؟

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

 function div!_iter(n) q = 1 for i in 1:n q = i // q end return q end 

أعلن أن هذا الإجراء مع دورة وظيفية مماثل لوظيفة عودية ، بمعنى أنه إذا كانت div!(n) و div!_iter(n) تُرجع نتيجة لبعض الأعداد الصحيحة الموجبة n ، div!_iter(n) دائمًا هي نفسها. هنا هو دليلي:

 [div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189 

لفهم العملية التي تولد هذه الأرقام ، ضع في اعتبارك القيم المتسلسلة للمتغيرات $$$i$ و $$$ف دولا$ في كل مرة تقوم بتشغيل حلقة في الأصل $$$i$ و $$$ف دولا$ متساوون $$$1$ ؛ لذلك ، بعد مرور أول دورة ، تعبير q = i // q يعطي $$$ف دولا$ القيمة $$$\ frac {1} {1}$ . ثم $$$i = 2$ و $$$q = \ frac {1} {1}$ وهذا هو معنى جديد $$$ف دولا$ يساوي $$$\ frac {2} {1}$ . في التكرار الثالث $$$i = 3$ و $$$q = \ frac {2} {1}$ هذا يعطينا $$$\ frac {i} {q} \ rightarrow \ frac {3} {2}$ . إذا كان هذا لا يزال مربكا ، تخيل ذلك $$$\ frac {i} {q}$ كيف $$$i \ times \ frac {1} {q}$ . ملاحظة مهمة هنا هي أنه مع كل دورة حلقة $$$ف دولا$ يحصل على القيمة المعاكسة ، تصبح $$$\ frac {1} {q}$ .

إذا قمت بتوسيع هذه العمليات ونظرت إلى الضرب والأقسام الموجودة في كل عنصر من عناصر السلسلة ، فسيظهر نمط:

$$

$$\ frac {1} {1} ، \ quad \ frac {2} {1} ، \ quad \ frac {1 \ cdot 3} {2} ، \ quad \ frac {2 \ cdot 4} {1 \ cdot 3 } ، \ quad \ frac {1 \ cdot 3 \ cdot 5} {2 \ cdot 4} \ quad \ frac {2 \ cdot 4 \ cdot 6} {1 \ cdot 3 \ cdot 5}$$

بشكل عام:

$$

$$\ frac {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n} {2 \ cdot 4 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {odd} n) \ qquad \ frac {2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n} {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {even} n)$$

---

وظائف $$$1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n$ لغريب $$$ن$ و $$$2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n$ حتى لو $$$ن$ لها اسم خاص بهم! يطلق عليهم المصنوعات المزدوجة ، ويتم كتابتها كـ $$$n!$ .

_{المصطلحات الرهيبة ، أليس كذلك؟ سيكون من الأفضل أن يطلق عليهم "شبه فصائل". وإذا لم أكن أعرف ، فسأقرأ} $$_{$n!$ كعامل مضروب.}

يتم تعريف العامل المضروب n بأنه ناتج كل الأعداد الصحيحة الموجبة الأصغر والمتساوية في التماثل. لذلك لدينا تسلسل فضولي من القيم متعرج هو مجرد $$$\ frac {n !!} {(n-1) !!}$ .

يستكشف مقال هنري و. جولد وجوسلين كوينتنز عام 2012 (للأسف وراء paywall) استخدام المصانع المزدوجة. أنها أكثر شيوعا بكثير مما قد يعتقد. في منتصف القرن السابع عشر ، اشتق جون واليس الهوية التالية:

$$

$$\ frac {\ pi} {2} = \ frac {2 \ cdot 2 \ cdot 4 \ cdot 4 \ cdot 6 \ cdot 6 \ cdots} {1 \ cdot 3 \ cdot 5 \ cdot 5 \ cdot 7 \ cdots} = \ lim_ {n \ rightarrow \ infty} \ frac {((2n) !!) ^ 2} {(2n + 1) !! (2n - 1) !!}$$

يتم تلخيص سلسلة غريبة حتى تنطوي على مكعب من القيم مضروب مزدوج $$$\ frac {2} {\ pi}$ . اكتشفه سرينيفاسا رامانوجان.

نظرت جولد وكينتينز أيضًا في المعادل المزدوج المضروب للمعاملات ذات الحدين. يتم تعريف معامل ذي الحدين القياسي على النحو التالي:

$$

$$\ binom {n} {k} = \ frac {n!} {k! (ن ك)!}$$

الإصدار المزدوج يشبه هذا:

$$

$$\ left (\! \ binom {n} {k} \! \ right) = \ frac {n !!} {k !! (ن ك)!}$$

لاحظ أن الأرقام المتعرجة الخاصة بنا تتوافق مع هذا الوصف ، وبالتالي يمكن اعتبارها معاملات ذات الحدين في المصانع المزدوجة. بشكل أكثر تحديدا ، هم مثل هذه الأرقام:

$$

$$\ left (\! \ binom {n} {1} \! \ right) = \ left (\! \ binom {n} {n - 1} \! \ right) = \ frac {n !!} {1 !! (ن -1) !!}$$

فول عادي $$$\ binom {n} {1}$ ليست مثيرة جدا للاهتمام. انه عادل على قدم المساواة $$$ن$ . لكن النسخة المزدوجة $$$\ left (\! \ binom {n} {1} \! \ right)$ كما رأينا ، والرقص أكثر حيوية هو الرقص. وعلى عكس الحدين المعتاد ، فإنه ليس دائمًا عددًا صحيحًا. (القيم الصحيحة الوحيدة هي $$$1$ و $$ .)

يفسر إلقاء نظرة على أرقام متعرجة كعدد من المصانع المزدوجة عددًا كبيرًا من خصائصها ، بدءًا من القيم المتساوية والغريبة. يمكننا أيضا أن نرى لماذا كل الأرقام الزوجية في التسلسل هي قوى 2. النظر في المثال مع $$$ن = 6 دولارا$ . البسط من هذا الكسر هو $$$2 \ cdot 4 \ cdot 6 = 48$ تلقي من $$ مضاعف $$ . لكن القاسم هو $$$1 \ cdot 3 \ cdot 5 = 15 دولارً$ . يتقلص ثلاثة توائم فوق وتحت ، وترك لنا $$$\ frac {16} {5}$ . تحدث هذه التخفيضات في كل حالة. في كل مرة يظهر عامل غريب في تسلسل الأرقام الزوجية $$$م دولا$ ، لديه بالضرورة النموذج $$$2 \ cdot m$ ولكن بحلول هذا الوقت نفسه $$$م دولا$ يجب أن تظهر بالفعل في سلسلة من الأرقام الفردية.

---

هل تسلسل الأرقام المتعرجة هو إجابة معقولة للسؤال: "ماذا يحدث إذا انقسمنا ، بدلاً من أن نتضاعف $$$n!$ ؟ " أو هل تبين أن برنامج الكمبيوتر الذي ينتج عنها مجرد خوارزمية خاطئة؟ في رأيي الشخصي ، $$$\ frac {1} {n!}$ - إجابة أكثر سهولة ، ولكن $$$\ frac {n !!} {(n - 1) !!}$ - أكثر إثارة للاهتمام.

علاوة على ذلك ، فإن وجود تسلسل متعرج يوسع آفاقنا. كما هو مذكور أعلاه ، إذا كنت تصر على أن خوارزمية القسمة يجب أن تنتقل دائمًا عبر قائمة البسط $$$ن$ ، في كل خطوة تقسم الرقم على اليسار على الرقم على اليمين ، هناك إجمالي $$$ن$ النتائج الممكنة ، وأنهم جميعا تبدو متشابهة جدا. لكن الحل متعرج يوفر إمكانيات أوسع بكثير. يمكننا صياغة المشكلة على النحو التالي: خذ مجموعة البسط $$$\ {1 \ dots n \}$ ، اختر مجموعته الفرعية وعكس كل عناصر هذه المجموعة الفرعية ؛ الآن نقوم بضرب جميع البسط ، سواء العكسي والمباشر. إذا كانت المجموعة الفرعية المقلوبة فارغة ، فستكون النتيجة فصيل منتظم $$$n!$ . إذا أصبحت جميع البساط معكوسًا لقيمها ، فسنحصل على العكس $$$\ frac {1} {n!}$ . وإذا تم تحويل كل البسط الثاني ، بدءا من $$$n - 1 دولا$ ، ثم ستكون النتيجة عنصر تسلسل متعرج.

هذه ليست سوى بعض من العديد من الخيارات المتاحة ؛ في المجموع هناك $$$2 ^ n$ مجموعات فرعية من $$$ن$ العناصر. على سبيل المثال ، يمكنك أن تأخذ معكوس كل رقم أولي أو قوة أولية $$$(2 ، 3 ، 4 ، 5 ، 7 ، 8 ، 9 ، 11 ، \ dots)$ . في الصغيرة $$$ن$ النتائج تقفز ، ولكن تبقى باستمرار أقل من $$$1$ :


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

---

الآن سوف أطرح سؤالا. رأينا الاختلافات الموضعية تقترب من الصفر $$$ن$ إلى ما لا نهاية على سبيل المثال $$$1 / ن!$ . لقد رأينا اختلافات أخرى تنمو مع تزايد $$$ن$ غير محدود ، بما في ذلك نفسي $$$n!$ وأرقام متعرجة. هل هناك أي أنواع من العملية الحزبية تتلاقى مع بعض الحدود المحدودة التي ليست صفراً؟

بادئ ذي بدء ، حدثت الخوارزمية التالية لي:

 function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q end 

نحن حلقة من خلال القيم الصحيحة من $$$ن$ وصولا الى $$$1$ حساب المنتج الحالي / الباقي في العملية $$$ف دولا$ . في كل خطوة ، إذا كانت القيمة الحالية $$$ف دولا$ المزيد $$$1$ ، نقسمها على البسط التالي ، وإلا ، فإننا نقوم بإجراء الضرب. ينفذ هذا المخطط نوعًا من إدارة الملاحظات أو سلوك البحث المستهدف. إذا $$$ف دولا$ الحصول على كبير جدا ، ونحن تقليله. إذا كانت صغيرة جدا ، نزيدها. اقترحت ذلك أثناء السعي $$$ن$ إلى ما لا نهاية $$$ف دولا$ سوف تتلاقى إلى مجموعة ضيقة باستمرار من القيم بجانب $$$1$ .

لكن التجربة أذهلتني مفاجأة أخرى:


مثل هذه الموجة مسننة ليست بالضبط ما كنت أتوقعه. من الغريب أن المنحنى ليس متماثلًا حوله $$$1$ ؛ الانحرافات من أعلاه لديها سعة أكبر من أدناه. ولكن هذا التشويه هو أكثر البصرية من الرياضيات. منذ $$$ف دولا$ هو خاص ، المسافة من $$$1$ قبل $$ نفس المسافة من $$$1$ قبل $$$\ frac {1} {10}$ ولكن على نطاق خطي لا يبدو ذلك. يمكنك إصلاح ذلك من خلال تجميع رسم بياني لوغاريتمي في الحاصل:


الآن الرسم البياني متماثل ، أو على الأقل تقريبًا ، ويتم توسيطه بالنسبة للقيمة $$$0$ وهو اللوغاريتم $$$1$ . ولكن لا يزال هناك سر أكثر خطورة. موجة سن المنشار منتظمة جدا ولها فترة $$ ، في حين لا تظهر علامات الانضغاط في اتجاه قيمة الحد المتوقعة $$$\ log q = 0$ . القيم العددية تشير إلى أنه عندما $$$ن$ إلى ما لا نهاية ، تتقارب قمم المنحنى إلى قيمة أعلى قليلاً $$$q = \ frac {5} {3}$ ، والقيعان تقترب من قيمة أقل قليلاً $$$q = \ frac {3} {5}$ . (لوغاريتمات قاعدة المقابلة $$ متساوون تقريبا $$$\ pm0.222$ ) لم أستطع معرفة سبب حدوث ذلك. ربما شخص ما يمكن أن يفسر.

الفشل في هذه الخوارزمية الجشعة لا يعني أننا لا نستطيع تقسيم التقارب بين الفصائل $$$ف = 1 دولا$ .

_{إذا عملنا مع لوغاريتمات البسط ، يصبح هذا الإجراء هو حالة مشكلة حسابية معروفة تسمى "مشكلة تقسيم مجموعة من الأرقام". يتم إعطاء العديد من الأرقام الحقيقية ، ويجب أن نقسمها إلى مجموعتين ، مجموعها يساوي ، أو أقرب ما يمكن من المساواة. هذه مهمة ثبت أنها صعبة ، ولكنها تسمى أيضًا ( PDF ) بأنها "أبسط مهمة معقدة".}

لأي $$$ن$ يمكننا أن نجد أنه عند استخدام القيم المعكوسة لبعض المجموعات الفرعية الأخرى من البسط يعطينا تقريبًا أفضل $$$ن! = 1 دولا$ . ل الصغيرة $$$ن$ يمكننا حل هذه المشكلة بالقوة الغاشمة: فقط فكر في كل شيء $$$2 ^ n$ مجموعات فرعية واختيار الأفضل.

حسبت الأقسام المثالية حتى $$$ن = 30 دولا$ عندما تحتاج إلى الاختيار من بين مليار الخيارات.


من الواضح أن الرسم البياني يزداد. يمكنك استخدام نفس الطريقة لفرض التقارب على أي قيمة أخرى في النطاق من $$$0$ قبل $$$n!$ .

وهكذا نحصل على إجابة أخرى على السؤال الذي طرحته سقسقة وبدأنا رحلتنا. ماذا يحدث إذا انقسمنا ولم نتضاعف $$$n!$ ؟ أي شيء نريده.