לדלג לתוכן

תורת החישוביות/סיבוכיות קולמוגורוב/יישומי אי-דחיסות/תרגילים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

חסם פשוט על צפיפות המספרים הראשוניים[עריכה]

משפט המספרים הראשוניים אומר בקירוב שאם הוא המספר הראשוני ה-, אז

בעזרת סיבוכיות קולמוגורוב, אפשר להראות בקלות רבה מאד תוצאה מעט יותר חלשה, לפיה

.

הוכח תוצאה זו בצורה הבאה. נניח ש- הוא מספר כלשהו, ו- הוא המספר הראשוני הגדול ביותר המחלק אותו. תאר את בצורה יעילה (רמז: אל תשתמש ב- אלא ב--). הוסף את העובדה כי רוב המחרוזות אינן דחיסות במיוחד,והשתמש בה עבור הטבעיים.


הפתרון

ברור שאפשר לתאר את בעזרת ו-. אך נשים לב שקל לבנות תוכנית המוצאת את המספר הראשוני ה-. לכן, נוכל לתאר את בעזרת ו-. מהתרגילים הקודמים נובע שkתיאור שני מספרים אלה מספיק מצד שני, סיבוכיות רוב המספרים מסוג הנה לפחות משילוב שני הדברים נקבל

התוצאה מתקבלת ע"י קיזוז משני האגפים, ופישוט.