У каждого из чисел от 1 до 1 000 000 выписан наибольший нечётный делитель. Каких среди выписанных чисел больше: дающих остаток 1 или дающих остаток 3 при делении на 4?

задан 12 Янв '14 0:03

изменен 14 Янв '14 16:54

Наверное, следует подправить заголовок, так как здесь не идёт речь про НОД.

(12 Янв '14 3:12) falcao
10|600 символов нужно символов осталось
1

Пусть речь идёт о числах от 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. Их ровно восемь.

ссылка

отвечен 12 Янв '14 3:11

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,709

задан
12 Янв '14 0:03

показан
1204 раза

обновлен
14 Янв '14 16:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru