Ювілей

У році $2134$, коли населення Землі досягло 10^{18}, люди вирішили відсвяткувати цю подію. $N$ крихітних лампочок (лінійний розмір кожної був менше $0.1$ міліметра) розмістили на величезній площі, спеціально виділеній для святкування. Лампочки були пронумеровані послідовними цілими числами від $1$ до $N$ в певному порядку.

Спочатку всі лампочки були вимкнені. Далі виконали рівно 10^{18} кроків — по одному для кожного жителя Землі. На $i$-му кроці одночасно змінювався стан усіх лампочок із номерами $X$, таких що $i$ ділить $X$. Змінити стан означає: якщо лампочка вимкнена, її вмикали, якщо ввімкнена — вимикали. Проміжок між кроками становив $1$ пікосекунду, тож усе святкування тривало близько півтора тижня.

Зовнішньому спостерігачу це могло здаватися безглуздим хаотичним блиманням, проте всі були вражені масштабом події!

Зрештою, усе завершилось. Більше не було на що дивитися; і, подумавши — насправді ніколи й не було на що дивитися.

Після 10^{18}-го кроку деякі лампочки залишилися увімкненими. Поки люди оговтуються та розмірковують, чи було потрібне таке святкування й як сплатити його астрономічні витрати, вам пропонується підрахувати, скільки лампочок все ще ввімкнені й споживають дорогоцінну електроенергію.