חידת אוילר

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

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

השאלה היא פשוטה: מבין כל המספרים מ-2 עד מיליון, מהו המספר \( n \) שעבורו היחס \( \frac{n}{\varphi(n)} \) הוא הגדול ביותר?