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

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

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

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

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

.

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