تحليل العجلة

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 3 صور
الموسوعة الحرة
تحليل العجلة مع n = 2 × 3 × 5 = 30. لن تظهر أي أعداد أولية في المناطق الصفراء.

التحليل إلى عوامل هو طريقة لتوليد سلسلة من الأعداد الطبيعية عن طريق عمليات الجمع المتكررة، كما هو محدد بعدد الأعداد الأولية القليلة الأولى ، بحيث تكون الأعداد المولدة أولية نسبياً مع هذه الأعداد الأولية، بحسب البناء.

وصف

بالنسبة لعدد مختار n (عادةً لا يتجاوز 4 أو 5)، تحدد الأعداد الأولية n الأولى الطريقة المحددة لتوليد سلسلة من الأعداد الطبيعية التي يُعرف مسبقًا أنها أولية فيما بينها؛ أي أنها ليست من مضاعفات أي من هذه الأعداد الأولية. وبالتالي، يمكن استخدام هذه الطريقة لتحسين طريقة القسمة التجريبية لتحليل الأعداد الصحيحة إلى عواملها الأولية، حيث لا يلزم اختبار أي من الأعداد المولدة في عمليات قسمة تجريبية باستخدام تلك الأعداد الأولية الصغيرة.

تعتمد طريقة القسمة التجريبية على قسمة العدد المراد تحليله على الأعداد الصحيحة بالترتيب التصاعدي (2، 3، 4، 5، ...) على التوالي. ومن التحسينات الشائعة اختبار الأعداد على الأعداد الأولية فقط، أي 2، 3، 5، 7، 11، ... أما في طريقة التحليل الدائري، فيبدأ المرء بقائمة صغيرة من الأعداد تُسمى الأساس (عادةً ما تكون الأعداد الأولية القليلة الأولى )؛ ثم يُنشئ قائمة تُسمى العجلة ، وهي قائمة الأعداد الصحيحة التي تكون أولية فيما بينها مع جميع الأعداد في الأساس.

بعد ذلك، بالنسبة للأعداد الناتجة عن "تدوير العجلة"، يكفي اعتبار الأعداد الأولية غير الموجودة في الأساس عوامل محتملة لها. وكأن هذه الأعداد قد تم اختبارها مسبقًا، وثبت أنها غير قابلة للقسمة على أي من الأعداد الأولية في الأساس. وهذا يُعدّ تحسينًا لأن جميع هذه العمليات تصبح زائدة عن الحاجة، ويتم الاستغناء عنها تمامًا.

عند استخدام هذه الطريقة في إيجاد الأعداد الأولية، أو في عملية الفرز عمومًا، فإنها تقلل من عدد الأعداد المرشحة التي يجب اعتبارها أعدادًا أولية محتملة. مع الأساس {2، 3}، ينخفض ​​العدد إلى 1/3 < 34% من جميع الأعداد. هذا يعني أنه يتم تخطي ثلثي جميع الأعداد المرشحة تلقائيًا. أما مع الأسس الأكبر، فينخفض ​​هذا المعدل أكثر؛ على سبيل المثال، مع الأساس {2، 3، 5} ينخفض ​​إلى 8/30 < 27% ، ومع الأساس {2، 3، 5، 7} ينخفض ​​إلى 48/210 < 23% .

كلما كبرت العجلة، زادت الموارد الحاسوبية المطلوبة وقلّت التحسينات الإضافية، مما يؤدي إلى تناقص العوائد بسرعة.

مقدمة

يتم تعداد الأعداد الطبيعية من 1 فصاعدًا عن طريق الجمع المتكرر للعدد 1:

1، 2، 3، 4، 5، ...

يتم النظر إليها على شكل نطاقات من رقمين لكل منها، ويتم تعدادها عن طريق عمليات جمع متكررة للعدد 2:

1، 2  ؛  3، 4  ؛  5، 6  ؛  ...

كل عدد ثانٍ يتم توليده بهذه الطريقة سيكون زوجيًا. وبالتالي، يتم توليد الأعداد الفردية من خلال الجمع المتكرر للعدد 2.

1  ؛  3  ؛  5  ؛  7  ؛  ...

يتم النظر إليها على شكل مجموعات من ثلاثة أرقام لكل منها، ويتم تعدادها عن طريق عمليات جمع متكررة لـ 2 × 3 = 6:

1، 3، 5  ؛  7، 9، 11  ؛  ...

كل عدد ثانٍ في هذه الثلاثيات سيكون من مضاعفات العدد 3، لأن الأعداد التي على الصورة 3 + 6k هي جميعها مضاعفات فردية للعدد 3. وبالتالي، فإن جميع الأعداد الأولية فيما بينها مع أول عددين أوليين (2 و3) سيتم توليدها عن طريق عمليات جمع متكررة للعدد 6، بدءًا من {1، 5}:

1، 5  ؛  7، 11  ؛  13، 17  ؛  ...

يمكن توليد نفس التسلسل عن طريق عمليات جمع متكررة لـ 2 × 3 × 5 = 30، مما يحول كل خمسة امتدادات متتالية، كل منها مكون من رقمين ، إلى امتداد واحد متصل مكون من عشرة أرقام:

1، 5، 7، 11، 13، 17، 19، 23، 25، 29  ؛  31، 35، 37، ...

من بين كل عشرة من هذه الأعداد الأولية فيما بينها ذات العدد 6، اثنان منها مضاعفات للعدد 5، وبالتالي فإن الأعداد الثمانية المتبقية ستكون أولية فيما بينها ذات العدد 30:

1، 7، 11، 13، 17، 19، 23، 29  ؛  31، 37، 41، 43، 47، 49، ...

هذا تعميم طبيعي.

يوضح الشكل أعلاه العجلات الثلاث الأولى:

  • {1} (يحتوي على 1 = 2 − 1 عدد) مع "محيط" 2 لتوليد سلسلة من 2-الأعداد الأولية عن طريق الجمع المتكرر لـ 2؛
  • {1، 5} (تحتوي على 2 = (2 − 1) × (3 − 1) أعداد) مع "محيط" 2 × 3 = 6، لتوليد سلسلة من الأعداد الأولية المشتركة 6 عن طريق عمليات الجمع المتكررة لـ 6؛
  • {1، 7، 11، 13، 17، 19، 23، 29} (تحتوي على 8 = (2 − 1) × (3 − 1) × (5 − 1) أعداد) مع "محيط" 2 × 3 × 5 = 30، لتوليد سلسلة من الأعداد الأولية فيما بينها 30 عن طريق عمليات الجمع المتكررة للعدد 30؛ إلخ.

هناك تمثيل آخر لهذه العجلات ، وهو تحويل أرقام العجلة، كما هو موضح أعلاه، إلى قائمة دائرية بالفروقات بين الأرقام المتتالية، ثم توليد التسلسل بدءًا من 1 عن طريق إضافة هذه الزيادات بشكل متكرر واحدًا تلو الآخر إلى آخر رقم تم توليده، إلى ما لا نهاية. هذا هو أقرب ما يكون إلى استعارة دحرجة العجلة . على سبيل المثال، هذا يحول {1، 7، 11، 13، 17، 19، 23، 29، 31} إلى {6، 4، 2، 4، 2، 4، 6، 2}، ثم يتم توليد التسلسل على النحو التالي:

ن =1؛ ن +6=7; ن +4=11; ن +2=13; ن +4=17; ن +2=19; ن +4=23; ن +6=29; ن +2=31; ن +6=37; ن +4=41; ن +2=43; إلخ.

مثال نموذجي

مع أساس معين من الأعداد الأولية الثلاثة الأولى {2، 3، 5}، تتكون "الدورة الأولى" للعجلة مما يلي:

7، 11، 13، 17، 19، 23، 29، 31 .

يُحسب العدد الثاني بإضافة 30، وهو حاصل ضرب الأساس، إلى الأعداد في العدد الأول. ويُحسب العدد الثالث بإضافة 30 إلى العدد الثاني، وهكذا.

لتطبيق هذه الطريقة، يمكن ملاحظة أن الزيادات بين عنصرين متتاليين من عناصر العجلة، أي

inc = [4, 2, 4, 2, 4, 6, 2, 6],

تبقى على حالها بعد كل دورة.

يستخدم التطبيق المقترح التالي دالة مساعدة div(n,k) لاختبار ما إذا كان العدد n يقبل القسمة على k بالتساوي ، ويعيد القيمة true في هذه الحالة و false في غير ذلك. في هذا التطبيق، يكون العدد المراد تحليله هو n ، ويعيد البرنامج أصغر قاسم للعدد n ، ويعيد n نفسه إذا كان عددًا أوليًا.

إذا كان القسمة على 2 يساوي صفرًا، فأرجع 2. إذا كان القسمة على 3 يساوي صفرًا، فأرجع 3. إذا كان القسمة على 5 يساوي صفرًا، فأرجع 5. k : = 7; i := 0 طالما أن k * k ≤ n، إذا كان القسمة على k يساوي صفرًا، فأرجع k . k := k + inc[ i ] إذا كان i < 7، فأرجع i : = i + 1 وإلا فأرجع n .

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

العوامل := [ ] بينما قسمة ( ن ، 2) = صحيح كرر العوامل := أضف(2، العوامل) n := n / 2 بينما div( n , 3) ​​= true do العوامل := أضف(3، العوامل) n := n / 3 بينما div( n , 5) = true do العوامل := أضف(5، العوامل) n := n / 5 k := 7; i := 0 while k * k ≤ n do if div( n , k ) = true then add( k , factors) n := n / k else k := k + inc[ i ] if i < 7 then i := i + 1 else i := 0 if n > 1 then add( n , factors) return factors

عرض تقديمي آخر

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

يمكن تطبيق هذه الطريقة بشكل متكرر كمنخل عجلة الأعداد الأولية لتوليد عجلات أكثر دقة. وقد أنجز بول بريتشارد [ 1 ] [ 2 ] [ 3 ] [ 4 ] أعمالًا بحثية رائدة في مجال تحليل العجلات، والمناخل التي تستخدم تحليل العجلات، ومنخل العجلات نفسه، وذلك من خلال صياغة سلسلة من الخوارزميات المختلفة. ولتوضيح استخدام عجلة التحليل، يمكن البدء بكتابة الأعداد الطبيعية حول دوائر كما هو موضح في الرسم التخطيطي المجاور. ويتم اختيار عدد الأضلاع بحيث تميل الأعداد الأولية إلى التراكم في عدد قليل من الأضلاع.

إجراء بياني نموذجي

  1. أوجد الأعداد الأولية القليلة الأولى التي تشكل أساس عجلة التحليل. وهي معروفة أو ربما تم تحديدها من تطبيقات سابقة لعجلات تحليل أصغر أو من خلال إيجادها بسرعة باستخدام غربال إراتوستينس .
  2. اضرب الأعداد الأولية الأساسية معًا للحصول على النتيجة n ، وهي محيط عجلة التحليل.
  3. اكتب الأرقام من 1 إلى n داخل دائرة. ستكون هذه الدائرة الداخلية التي تمثل دورة واحدة للعجلة.
  4. من الأرقام من 1 إلى n في الدائرة الداخلية، قم بحذف جميع مضاعفات الأعداد الأولية الأساسية من الخطوة الأولى كما هو مطبق في الخطوة 2. يمكن إنجاز عملية إزالة الأعداد المركبة هذه إما باستخدام غربال مثل غربال إراتوستينس أو كنتيجة لتطبيقات عجلات التحليل الأصغر.
  5. باعتبار x هو عدد الدوائر المكتوبة حتى الآن، استمر في كتابة xn + 1 إلى xn + n في دوائر متحدة المركز حول الدائرة الداخلية، بحيث يكون xn + 1 في نفس موضع ( x - 1) n + 1 .
  6. كرر الخطوة 5 حتى تغطي أكبر دائرة دوران أكبر عدد يتم اختباره للتأكد من أوليته.
  7. احذف الرقم 1.
  8. قم بشطب أضلاع الأعداد الأولية كما تم العثور عليها في الخطوة 1 وتطبيقها في الخطوة 2 في جميع الدوائر الخارجية دون شطب الأعداد الأولية في الدائرة الداخلية (في الدائرة 1).
  9. قم بإزالة أضلاع جميع مضاعفات الأعداد الأولية التي تم شطبها من الدائرة الداخلية 1 في الخطوة 4 بنفس طريقة إزالة أضلاع الأعداد الأولية الأساسية في الخطوة 8.
  10. معظم الأعداد المتبقية في عجلة التحليل هي أعداد أولية (وتُسمى مجتمعةً بالأعداد الأولية "النسبية"). استخدم طرقًا أخرى مثل غربال إراتوستينس أو تطبيق عجلات تحليل أكبر لإزالة الأعداد غير الأولية المتبقية.

مثال

تحليل العجلة مع n = 2 × 3 = 6
  1. أوجد أول عددين أوليين: 2 و 3.
  2. ن = 2 × 3 = 6
  3.  1 2 3 4 5 6
  4. شطب عاملي العددين 2 و3 وهما 4 و6 باعتبارهما عاملين للعدد 2؛ أما العدد 6 باعتباره العامل الوحيد للعدد 3 فقد تم شطبه بالفعل: 
     1 2 3 4 5 6
  5. x = 1. xn + 1 = 1 ⋅ 6 + 1 = 7. ( x + 1) n = (1 + 1) × 6 = 12. اكتب الأعداد من 7 إلى 12 بحيث يكون 7 محاذيًا للرقم 1. 
     1 2 3 4 5 6 7 8 9 10 11 12
  6. x = 2. xn + 1 = 2 ⋅ 6 + 1 = 13. ( x + 1) n = (2 + 1) · 6 = 18. اكتب الأرقام من 13 إلى 18. كرر ذلك للأسطر القليلة التالية. 
     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  7. غربلة 
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  8. غربلة 
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  9. تحتوي القائمة الناتجة على عدد غير أولي هو 25، وهو 5 2. استخدم طرقًا أخرى مثل الغربال لاستبعاده والوصول إلى
    2 3 5 7 11 13 17 19 23 29

لاحظ أنه باستخدام العدد الأولي التالي لدورات العجلة المكونة من 5 دورات، وحذف مضاعفات هذا العدد الأولي (فقط هذا العدد الأولي) من القائمة الناتجة، نحصل على العجلة الأساسية كما في الخطوة 4 لعجلة تحليل ذات أعداد أولية أساسية هي 2 و3 و5؛ وهذه عجلة متقدمة بواحدة عن عجلة التحليل السابقة {2،3}. يمكن بعد ذلك اتباع الخطوات حتى الخطوة 10 باستخدام العدد الأولي التالي لدورات العجلة المكونة من 7 دورات، وحذف مضاعفات العدد 7 فقط من القائمة الناتجة في الخطوة 10 (مع ترك بعض الأعداد الأولية "النسبية" في هذه الحالة وجميع الحالات اللاحقة - أي بعض الأعداد الأولية غير الكاملة)، للحصول على العجلة المتقدمة التالية، مع تكرار الخطوات بشكل متكرر حسب الحاجة للحصول على عجلات أكبر تدريجيًا.

التحليل والتنفيذ الحاسوبي

بشكل رسمي، تعتمد هذه الطريقة على الرؤى التالية: أولاً، أن مجموعة الأعداد الأولية الأساسية متحدة مع مجموعتها (اللامتناهية) من الأعداد الأولية فيما بينها هي مجموعة شاملة للأعداد الأولية؛ ثانياً، أنه يمكن تعداد المجموعة اللانهائية من الأعداد الأولية فيما بينها بسهولة من الأعداد الأولية فيما بينها إلى المجموعة الأساسية الواقعة بين 2 وحاصل ضرب المجموعات الأساسية. (لاحظ أن 1 يتطلب معالجة خاصة).

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

بمجرد أن تغطي عجلة ما الحد الأعلى المطلوب لنطاق الغربلة، يمكن التوقف عن إنشاء عجلات أخرى واستخدام المعلومات الموجودة في تلك العجلة لاستبعاد الأعداد المركبة المتبقية من قائمة العجلة الأخيرة باستخدام تقنية من نوع غربال إراتوستينس، مع الاستفادة من نمط الفجوات المتأصل في العجلة لتجنب عمليات الاستبعاد المتكررة. يمكن إجراء بعض التحسينات بناءً على حقيقة (سيتم إثباتها في القسم التالي) أنه لن يكون هناك استبعاد متكرر لأي عدد مركب: سيتم استبعاد كل عدد مركب متبقٍ مرة واحدة فقط. بدلاً من ذلك، يمكن الاستمرار في إنشاء قوائم عجلات مختصرة باستخدام الأعداد الأولية حتى الجذر التربيعي لنطاق الغربلة المطلوب، وفي هذه الحالة ستكون جميع تمثيلات الأعداد المتبقية في العجلة أولية. ومع ذلك، على الرغم من أن هذه الطريقة فعالة لدرجة أنها لا تستبعد الأعداد المركبة أكثر من مرة، إلا أنها تستهلك الكثير من الوقت خارج عمليات الاستبعاد المعتادة في معالجة عمليات مسح العجلة المتتالية، مما يجعلها تستغرق وقتًا أطول بكثير. تعتمد عملية استبعاد الأعداد المركبة باستخدام عجلة التحليل إلى عواملها الأولية على ما يلي: إذا كان لدينا عدد k > n ، فإننا نعلم أن k ليس عددًا أوليًا إذا لم يكن k mod n و n أوليين فيما بينهما. ومن ثم، يمكن تحديد نسبة الأعداد التي تستبعدها عجلة الغربال (مع العلم أنه ليس من الضروري استبعاد جميع الأعداد فعليًا؛ إذ يمكن استبعاد العديد منها تلقائيًا أثناء نسخ العجلات الأصغر إلى العجلات الأكبر) على أنها 1 − φ ( n ) / n ، وهي أيضًا كفاءة الغربال.

من المعروف أن

ليممعلوماتφ(ن)نسجل⁡سجل⁡ن=هـ-γ∼0.56145948،{\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }\sim 0.56145948,}

حيث γ هو ثابت أويلر . [ 5 ] وبالتالي، فإن φ ( n )/ n يؤول إلى الصفر ببطء مع ازدياد n إلى ما لا نهاية، ويمكن ملاحظة أن هذه الكفاءة ترتفع ببطء شديد إلى 100% لقيم n الكبيرة جدًا . من خصائص φ ، يمكن بسهولة ملاحظة أن المنخل الأكثر كفاءةً الأصغر من x هو الذي يكون فيه n = p1 p2 … p1 < x و np1 + 1 ≥ x ( أي أن توليد العجلة يمكن أن يتوقف عندما تمر العجلة الأخيرة أو عندما يكون محيطها كافيًا لاحتواء أعلى رقم في نطاق الغربلة) .

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

  1. ابدأ بـ S1 = {1} ، وهي مجموعة الأعداد الأولية التي يكون فيها n = 1 والعدد 2 هو أول عدد أولي. تعني هذه المجموعة الأولية أن جميع الأعداد بدءًا من 2 فصاعدًا تُعتبر أعدادًا أولية "نسبية" لأن محيط العجلة يساوي 1.
  2. المجموعات التالية هي S 2 = {1} ، مما يعني أنها تبدأ من 3 لجميع الأعداد الفردية مع حذف عوامل 2 (محيط 2)، و S 6 = {1,5} مع حذف عوامل 2 و 3 (محيط 6) كما هو الحال بالنسبة للعجلة الأساسية الأولية في المثال أعلاه، وهكذا.
  3. ليكن S n + k المجموعة التي تمت إضافة k إليها لكل عنصر من عناصر S n .
  4. ثم S np i +1 = F p i +1 [ S n ∪ S n + n ∪ S n + 2 n ∪ … ∪ S n + n ( p i +1 − 1)] ، حيث يمثل F x عملية إزالة جميع مضاعفات x .
  5. سيكون 1 و p i +1 هما أصغر عددين من S n عندما n > 2 ، مما يلغي الحاجة إلى حساب الأعداد الأولية بشكل منفصل، على الرغم من أن الخوارزمية تحتاج إلى الاحتفاظ بسجل لجميع الأعداد الأولية الأساسية التي تم حذفها والتي لم تعد مدرجة في المجموعات اللاحقة.
  6. جميع المجموعات التي يكون محيطها n > 2 متناظرة حول n / 2 ، مما يقلل من متطلبات التخزين. لا تستخدم الخوارزمية التالية هذه الحقيقة، ولكنها تعتمد على حقيقة أن الفجوات بين الأرقام المتتالية في كل مجموعة متناظرة حول نقطة المنتصف.

انظر أيضاً

مراجع

  1. ↑ بريتشارد، بول، "المناخل الخطية للأعداد الأولية: شجرة عائلة"، Sci. Comput. Programming 9 :1 (1987)، ص 17-35.
  2. ↑ بول بريتشارد، غربال جمعي شبه خطي لإيجاد الأعداد الأولية، اتصالات رابطة آلات الحوسبة 24 (1981)، 18-23. MR 0600730 
  3. ↑ بول بريتشارد، شرح المنخل ذي العجلة، مجلة أكتا إنفورماتيكا 17 (1982)، 477-485. MR 0685983 
  4. ↑ بول بريتشارد، مناخل الأعداد الأولية السريعة والمضغوطة (من بين أمور أخرى)، مجلة الخوارزميات 4 (1983)، 332-344. MR 0729229 
  5. ↑ هاردي، جي إتش ؛ رايت، إي إم (1979)، مقدمة في نظرية الأعداد ( الطبعة الخامسة)، مطبعة جامعة أكسفورد ، thm. 328، ISBN  978-0-19-853171-5