Задача, скорее всего, относящаяся к теории чисел

[N_B]

Доказать, что
[\sqrt{t+1}]-[\sqrt{t}] = \overline{\mathrm{sg}}(q(\varphi(t)+4)), где t\in\mathbb{N}, \varphi(t) = t+2[\sqrt{t}] и q(x)=x - [\sqrt{x}]^2,

[Бодигрим]

Скажите, в каком случае левая часть записанного уравнения равна 0? А в каких равна 1?

Добавлено спустя 3 минуты 36 секунд:

И далее: когда $q(x)=0$, а когда $q(x)>0$?

[Профессор Снэйп]

Кстати, откуда ноги растут у задачи? Примитивно рекурсивные функции изучаете?

[N_B]

Цитата:

Кстати, откуда ноги растут у задачи? Примитивно рекурсивные функции изучаете?

В книге Мальцева "Алгоритмы и рекурсивные функции" данный факт используется при доказательстве теоремы Р. Робинсона, а именно, в доказательстве того, что функция x^2 допустима.

Цитата:

когда q(x)=0, а когда q(x)>0?

q(x)=0 тогда и только тогда, когда x - полный квадрат.

Цитата:

Скажите, в каком случае левая часть записанного уравнения равна 0? А в каких равна 1?

К сожалению, мне не совсем понятно, как переписать это условие, и, вообще говоря, можно ли это сделать в терминах \sqrt{t} и \sqrt{t+1}, не используя целых частей.

[Бодигрим]

Левая часть равна 1, если $t+1$ - полный квадрат, и 0 в противном случае. Понятно, почему?

Воспользуйтесь тем, что всякое $t$ попадает ровно в один из отрезков $k^2,(k+1)^2-1$ (при этом $\lfloor \sqrt t \rfloor = k$). В силу поведения левой части достаточно рассмотреть два случая: $t=(k+1)^2-1$ и $t\in[k^2,(k+1)^2-2]$. Дальше - простая арифметика.