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

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

משפט המספרים הראשוניים אומר בקירוב שאם $p_{i}$ הוא המספר הראשוני ה-$i$, אז

$p_{i}\leq i\ln(i).$

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

$p_{i}\leq i\left(\log(i)^{2}+O(1)\right).$

.

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

הפתרון

ברור שאפשר לתאר את $m$ בעזרת $p_{i}$ ו-${\frac {m}{p_{i}}}$. אך נשים לב שקל לבנות תוכנית המוצאת את המספר הראשוני ה-$i$. לכן, נוכל לתאר את $m$ בעזרת $i$ ו-${\frac {m}{p_{i}}}$. מהתרגילים הקודמים נובע שkתיאור שני מספרים אלה מספיק $2\log \left(\log(i)\right)+\log(i)+\log \left({\frac {m}{p_{i}}}\right)$ מצד שני, סיבוכיות רוב המספרים מסוג $m$ הנה לפחות $\log(m)-O(1)$ משילוב שני הדברים נקבל

$\log(m)-O(1)\geq \log \left(\log(i)\right)+O(1)+\log(i)+\log \left({\frac {m}{p_{i}}}\right)=\log \left(\log(i)\right)+O(1)+\log(i)+\log(m)-\log \left({p_{i}}\right).$

התוצאה מתקבלת ע"י קיזוז $\log(m)$ משני האגפים, ופישוט.