Постройте вычислимую биекцию между N и N \ {p^2 | p - натуральное}

задан 16 Мар '16 3:39

10|600 символов нужно символов осталось
0

Вычеркнем из натурального ряда все точные квадраты: 2, 3, 5, 6, 7, 8, 10, ... , и занумеруем всё заново от единицы. Ясно, что прежний номер, равный $%n$%, уменьшится на число $%[\sqrt{n}]$%. Это биекция между $%\mathbb N$% и $%\mathbb N\setminus\{k^2\mid k\in\mathbb N\}$%.

Можно точно так же построить и формулу для биекции в обратную сторону. Пусть число $%m$% перешло в $%n$%. Тогда, по предыдущему, $%n-[\sqrt{n}]=m$%, то есть $%[\sqrt{n}]=n-m$%. Заметим, что $%n$% не является точным квадратом, поэтому в определении целой части оба неравенства будут строгими: $%n-m < \sqrt{n} < n-m+1$%. Возведём в квадрат: $%(n-m)^2 < n < (n+1-m)^2$%. Можно оставить только первое из неравенств, добавив, что $%n$% является наибольшим числом, которое ему удовлетворяет. Действительно, при замене $%n$% на $%n+1$% первое неравенство приобретает вид $%(n+1-m)^2 < n+1$%, но это не так в силу второго из неравенств. Таким образом, нам нужно найти наибольшее $%n$%, для которого $%(n-m)^2\le n-1$%.

Итак, $%n^2-2mn+m^2-n+1\le0$%. Выделяем полный квадрат: $%(n-m-\frac12)^2\le(m+\frac12)^2-m^2-1=m-\frac34$%. Умножаем на четыре: $%(2n-2m-1)^2\le4m-3$%, то есть $%2n-2m-1\le\sqrt{4m-3}$%. Поэтому $%n\le\frac{2m+1+\sqrt{4m-3}}2$%, и оговорка насчёт того, что $%n$% берётся наибольшим, даёт формулу $%n=\lfloor\frac{2m+1+\sqrt{4m-3}}2\rfloor$% со взятием целой части.

ссылка

отвечен 16 Мар '16 4:44

изменен 16 Мар '16 4:45

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

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

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

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

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

отмечен:

×25

задан
16 Мар '16 3:39

показан
325 раз

обновлен
16 Мар '16 4:45

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

по почте:

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

по RSS:

Ответы

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

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