גמדים
לפניך 1000 מנורות, לכל מנורה מתג המדליק אותה בלחיצה אחת ומכבה אותה בלחיצה שנייה. כל המנורות כבויות. 1,000 גמדים מגיעים. הראשון לוחץ על כל המתגים ומדליק את כל הנורות, השני לוחץ על כל מתג שני (המתגים הזוגיים), השלישי לוחץ על כל מתג שלישי, וכן הלאה. אילו נורות תהיינה דלוקות לאחר שכל הגמדים סיימו להשתולל?
גמד ראשון מגיע:(1 1 1 1 1 1 1 1 ...)
גמד שני מגיעה:
(0 1 0 1 0 1 0 1 ...)
ואחר כך שלישי ורביעי...
אם נעשה סכום של כל עמודה - תצאה :
(1 2 2 3 2 4 2 4) = O0(n)
שכל מספר בסכום של שורה -
זה מספר גורמים של מספר סידורי של גמד - factor!
לכן, כאשר
O0(n)
הוא אי זוגי - מנורה דולקת,
וכאשר מספר הוא זוגי - מנורה כבויה,
אבל O0(n)
אי זוגי רק כאשר n הוא מספר ריבועי.
סה"כ מנורות דלוקות יהיה
לכן, מנורה 25 תהיה דלוקה - ריבועי (O0(25) = 3 ) מנורה 93 כבויה - לא ריבועי (O0(93) = 4 ) מנורה 576 דלוקה - ריבועי (O0(576) = 21 ) וסה"כ 31 מנורות דלוקות - שורש 1000 = 31