математика - Нечетный делитель

Пусть речь идёт о числах от 1 до $%n$%. Обозначим через $%f(n)$% разность между количеством чисел вида $%4k+1$% и количеством чисел вида $%4k+3$%, о которых говорится в условии задачи. Рассмотрим случай, когда $%n$% кратно четырём. Тогда среди нечётных чисел имеется поровну тех и других, а для чётных чисел результат будет равен $%f(n/2)$%. Если $%n$% даёт в остатке 1 при делении на 4, то само число $%n$% вносит в $%f(n)$% вклад $%1$%, и далее можно перейти к числу $%n-1$%, а поскольку оно делится на 4, то к $%(n-1)/2$%. Если $%n$% даёт в остатке $%2$% при делении на $%4$%, то есть $%n=4m+2$%, то $%4n+1$% вносит в $%f(n)$% вклад 1, у остальных нечётных чисел они одинаковый, а для анализа вклада чётных чисел надо перейти к числу $%2m+1=n/2$%. Наконец, если $%n$% даёт в остатке $%3$% при делении на $%4$%, то есть $%n=4m+3$%, то у нечётных чисел вклад в $%f(n)$% нулевой, а для анализа вклада чётных чисел надо перейти к числу $%2m+1=(n-1)/2$%.

Итоговый вклад числа $%n$%, то есть значение $%f(n)$%, проще всего прослеживается через двоичное представление числа $%n$%. Для $%n=10^6$% оно таково: 11110100001001000000. Идём справа, и если на конце 00, то последний из нулей списываем. Если на конце 01, то добавляем 1 к "счётчику", и 1 списываем, переходя к $%(n-1)/2$%. Если на конце 10, то также добавляем 1 к "счётчику", и последний 0 списываем. Наконец, если на конце 11, то переходим к числу $%(n-1)/2$%, списывая последнюю цифру 1.

Из описания понятно, что $%f(n)\ge0$% для всех чисел, а применительно к миллиону описанная выше процедура даёт $%f(10^6)=8$%. Жирным шрифтом выделены те цифры, при списывании которых мы добавляли 1 к значению $%f(n)$%: 11110100001001000000. Их ровно восемь.