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