Была задача: Есть 100 бит информации в ряд. Изначально все они равны "1".

Question

Программа пробегает по всем битам и меняет значение каждого второго на противоположный. Потом еще раз - но на этот раз каждый 3-й. Потом каждый 4-й, так дале. На последнем 99 пробеге она меняет лишь последний 100-й бит. Сколько бит после этогот имеют значение "1".
И были вопросы:
Как решать не перебирая все проходы?
Есть ли общая формула для любого числа бит?
 
Ни где не нашел ответа в виде полной формулы! Может быть кто-кто решил или решит?

Answer 1

Там в комментариях вроде была формула - целая часть из sqr (n) . или споры по ней. Я её не проверял.
Но я полагаю, что если решение строится на переборе простых множителей. то общей формулы быть не может, поскольку нет общей формулы для простых чисел.

Answer 2

n-ый бит будет изменён k раз,
где k - число делителей у n.
То есть,
если число делителей у n - чётно,
то n-ый бит останется равным 1.
Иначе станет нулём.

Answer 3

Единицами останутся только полные квадраты, значит, целая часть корня из длины строки.