время получения целочисленного корня

[maxal]

Задача Рустема про n-е приближение к квадратному корню напомнило мне один примечательный факт связанный с процедурой вычисления целочисленного квадратного корня.

Рассмотрим вариант метода Ньютона вычисления целочисленного квадратного корня из заданного числа n:

$$x_1 = n,\quad x_{k+1} = \left\lfloor \frac{x_k + \lfloor n / x_k \rfloor}{2} \right\rfloor$$

Пусть $m=m(n)$ - это минимальный индекс, для которого $x_m = \lfloor \sqrt{n} \rfloor$. Понятно, что последовательность вплоть до индекса m является убывающей, т.е. $n = x_1 > x_2 > \dots > x_m = \lfloor \sqrt{n} \rfloor.$ Индекс m можно определить так же как минимальный индекс, для которого $x_{m+1}\geq x_m.$

Вот таблица значений $m(n)$ для $n=1,\dots,50$:

*1: 1     *2: 2     *3: 3      4: 2      5: 3
 6: 3      7: 3     *8: 4      9: 3     10: 3
11: 3     12: 4     13: 4     14: 4     15: 4
16: 4     17: 4     18: 4     19: 4     20: 4
21: 4     22: 4     23: 4    *24: 5     25: 4
26: 4     27: 4     28: 4     29: 4     30: 4
31: 4     32: 5     33: 5     34: 5     35: 5
36: 4     37: 4     38: 4     39: 4     40: 5
41: 5     42: 5     43: 5     44: 5     45: 5
46: 5     47: 5    *48: 6     49: 5     50: 5

Звездочками помечены пиковые значения $n$ - те, для которых $m(n)>m(n')$ для всех $n'<n$.

Пусть $p$ - номер пика и $n(p)$ - соответствующее ему значение $n$. Таблица значений $n(p)$ и соответствующих значений $\sqrt{n(p)+1}$:

         p             n(p)     sqrt(n+1)
-----------------------------------------
         1                1          -
         2                2          -
         3                3          2
         4                8          3
         5               24          5
         6               48          7
         7              120         11
         8              360         19
         9             1088         33
        10             3135         56
        11             9999        100
        12            31328        177
        13           103040        321
        14           342224        585

Вопросы в порядке возрастания сложности:

1) Доказать, что число $n(p)+1$ является полным квадратом для $p\geq 3$.

2) Найти явную формулу для $n(p)$.

3) Те же вопросы для случая, когда $x_1$ определено по-другому. Например, $x_1 = \lfloor n/2 \rfloor$ или $x_1 = \lfloor n/3 \rfloor$.

[Руст]

maxal, тебе тоже вопросы.
1. Ты уверен, что процесс стабилизируется всегда?. Когда берётся целые части, может появится ситуация блуждания последовательности y, следующий y+1, потом опять y.
2. Даже при стабилизации он может не совпасть с целой частью от кватратного корня.
3. Эти задачи решённые, или выдуманные наобум?

[maxal]

Руст писал(а):

maxal, тебе тоже вопросы.
1. Ты уверен, что процесс стабилизируется всегда?. Когда берётся целые части, может появится ситуация блуждания последовательности y, следующий y+1, потом опять y.
2. Даже при стабилизации он может не совпасть с целой частью от кватратного корня.
3. Эти задачи решённые, или выдуманные наобум?

1-2. Посыпаю голову пеплом и исправляю условие.

3. Когда-то очень давно решал, но сейчас сходу не могу найти решения. Так что, сейчас я решаю эту задачу вместе со всеми

[Егор]

Мне кажется, Руст прав (в первом замечании). При $x_1=n=8$ у меня получается последовательность $8,4,3,2,3,2,\ldots$. Видимо, через $m(n)$ нужно обозначить наименьший номер $k$, для которого $x_k\le\sqrt{n}$, что равносильно $x_{k+1}\ge x_k$.

[maxal]

Рустем и Егор, конечно, вы правы. Я перепутал с другой задачей. Сейчас внесу изменения.

[Руст]

Легко проверить, что при $n=k^2+2k=m^2-1$ придём к блужданию k, k+1,k,... Это единственный случай. Когда точка стационарная, то действительно совпадает.

[maxal]

Условие исправлено.

[Руст]

maxal писал(а):

Индекс m можно определить так же как минимальный индекс, для которого $x_{m+1}\geq x_m.$

Опять неверно. Точнее минимальный индекс, при котором $x_m=[\sqrt n ].$

[maxal]

Руст писал(а):

maxal писал(а):

Индекс m можно определить так же как минимальный индекс, для которого $x_{m+1}\geq x_m.$

Опять неверно. Точнее минимальный индекс, при котором $x_m=[\sqrt n ].$

Это равносильные определения. Дело в том, что если $x_k\geq\sqrt{n},$ то $x_{k+1}\geq\lfloor\sqrt{n}\rfloor.$

С другой стороны, если $x_k<\sqrt{n},$ то $x_{k+1}\geq x_k.$ Поэтому $x_k\geq \lfloor\sqrt{n}\rfloor$ для всех $k.$

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

Кстати, внутреннее взятие целой части в формуле для $x_{k+1}$ можно отбросить:

$$x_{k+1} = \left\lfloor \frac{x_k + n / x_k}{2} \right\rfloor$$

Это упрощает анализ. В частности, применяя неравенство о средних получаем еще одно доказательство нижней грани:

$$x_{k+1} = \left\lfloor \frac{x_k + n / x_k}{2} \right\rfloor \geq \left\lfloor \sqrt{n} \right\rfloor.$$

[Руст]

maxal писал(а):

Это равносильные определения. Дело в том, что если $x_k\geq\sqrt{n},$ то $x_{k+1}\geq\lfloor\sqrt{n}\rfloor.$

$$x_{k+1} = \left\lfloor \frac{x_k + n / x_k}{2} \right\rfloor$$

Это упрощает анализ. В частности, применяя неравенство о средних получаем еще одно доказательство нижней грани:

$$x_{k+1} = \left\lfloor \frac{x_k + n / x_k}{2} \right\rfloor \geq \left\lfloor \sqrt{n} \right\rfloor.$$

Это равносильно, когда приближение сверху. В части 3 меется начальное приближение, при котором это может нарушаться, т.е. уже $x_1\ge x_0$, но ещё далеки от стабилизации. Это замечание полезное, хотя нельзя сказать, что оно упрощает ситуацию.

[maxal]

Руст писал(а):

Это равносильно, когда приближение сверху. В части 3 меется начальное приближение, при котором это может нарушаться, т.е. уже $x_1\ge x_0$, но ещё далеки от стабилизации.

Предлагаю для начала сфокусироваться на начальной задаче с $x_1 = n$, когда приближение идет именно сверху.

[Руст]

1. Вопрос 1 простой.
2. Для второго вопроса боюсь не удастся получить точную формулу (похоже на это) всвязи с быстрым ростом.
3. Для 1 и приближения сверху всё остаётся в силе. 2 практически нерешаема.

[maxal]

Еще одна задача:
4) Доказать, что $m(t^2-1)$ неубывающая функция для $t=2,3,\dots$.

Добавлено спустя 2 часа 58 минут 9 секунд:

Руст писал(а):

2. Для второго вопроса боюсь не удастся получить точную формулу (похоже на это) всвязи с быстрым ростом.

Что-то я не понял этого аргумента. Растет настолько быстро, что нельзя выразить через элементарные функции? Или о чем речь?