итерации в вычислении целочисленного корня

[maxal]

Несложно видеть, что для фиксированного целого $n>0$ итерации функции $f_n(x) := \left\lfloor \frac{x+\lfloor n/x\rfloor}{2} \right\rfloor$ приводят к $\lfloor \sqrt{n}\rfloor$ для любого стартового значения $x=a>0$.

Пусть $g(n)$ равно минимальному $m$, что $f_n^{(m)}(n)=\lfloor \sqrt{n}\rfloor$, то есть минимальное количество итераций $f_n(x)$ необходимых для достижения целочисленного корня из $n$, начиная с $x=n$.
Значения $g(x)$ для $n\le 100$ такие:

01: 0 | 11: 2 | 21: 3 | 31: 3 | 41: 4 | 51: 4 | 61: 4 | 71: 4 | 81: 4 | 91: 5
02: 1 | 12: 3 | 22: 3 | 32: 4 | 42: 4 | 52: 4 | 62: 4 | 72: 4 | 82: 4 | 92: 5
03: 2 | 13: 3 | 23: 3 | 33: 4 | 43: 4 | 53: 4 | 63: 5 | 73: 4 | 83: 4 | 93: 5
04: 1 | 14: 3 | 24: 4 | 34: 4 | 44: 4 | 54: 4 | 64: 4 | 74: 4 | 84: 4 | 94: 5
05: 2 | 15: 3 | 25: 3 | 35: 4 | 45: 4 | 55: 4 | 65: 4 | 75: 4 | 85: 4 | 95: 5
06: 2 | 16: 3 | 26: 3 | 36: 3 | 46: 4 | 56: 4 | 66: 4 | 76: 4 | 86: 4 | 96: 5
07: 2 | 17: 3 | 27: 3 | 37: 3 | 47: 4 | 57: 4 | 67: 4 | 77: 5 | 87: 4 | 97: 5
08: 3 | 18: 3 | 28: 3 | 38: 3 | 48: 5 | 58: 4 | 68: 4 | 78: 5 | 88: 4 | 98: 5
09: 2 | 19: 3 | 29: 3 | 39: 3 | 49: 4 | 59: 4 | 69: 4 | 79: 5 | 89: 4 | 99: 5
10: 2 | 20: 3 | 30: 3 | 40: 4 | 50: 4 | 60: 4 | 70: 4 | 80: 5 | 90: 4 | 100: 4

Здесь жирным шрифтом выделены рекордные значения (т.е. большие всех предыдущих) функции $g(x)$.

Докажите:

1) Функция $h(n) := g(n^2)$ является неубывающей.

2) Для всякого $n\geq 3$, если $g(n)$ - рекордное значение, то $n+1$ является квадратом.

3) Для всякого $n\geq 6$, $h(n)$ - рекордное значение (для $h$) тогда и только тогда, когда $g(n^2-1)$ - рекордное значение (для $g$).

4) Найдите формулу для аргумента $k$-го рекордного значения функции $h$.

[wrest]

maxal в сообщении #1410109 писал(а):

Значения $g(x)$ для первой сотни значений $n$ такие:

А что брали за стартовое значение? От него же зависит количество итераций...

[ex-math]

То значение, при котором количество итераций минимально

[nnosipov]

ex-math в сообщении #1410112 писал(а):

То значение, при котором количество итераций минимально

А если в качестве $a$ взять $[\sqrt{n}]$? Это же неподвижная точка для $f(x)$, вроде бы.

[maxal]

ex-math, нет. Согласно указанной формуле стартовое значение равно $n$. Но на всякий уточнил его явно.

[nnosipov]

В плане вычислений это хуже, но аналитически выглядит проще:

$$f(x)=\left[\frac{x^2+n}{2x}\right]$$

(знак целой части внутри можно убрать).

[kthxbye]

maxal в сообщении #1410109 писал(а):

4) Найдите формулу для аргумента $k$-го рекордного значения функции $h$.

Больше всего заинтересовал этот вопрос. Нашел вашу A327010 (и остальные, но последний вопрос, собственно, как раз о ней). Прошелся по посл.-тям, для которых она является подпосл.-тью в надежде на какую-нибудь несложную закономерность, но, увы. Все, чем пока могу поделиться - наблюдение, связанное с первыми разностями, а именно

$$T(n,m)=[m=1]\left\lfloor\frac{n^2+1}{2}\right\rfloor+[m>1]\left\lfloor\frac{T(n,m-1)+\left\lfloor n^2/T(n,m-1)\right\rfloor}{2}\right\rfloor$$

$$T_1(n,m)=[n>1](T(n,m)-T(n-1,m))$$

$$T_1(n,1)=2\left\lfloor\frac{n+1}{2}\right\rfloor-1$$

$$T_1(n,2)=\left\lfloor\frac{n}{2}\right\rfloor$$

$$[T_1(n,3)=\left\lfloor\frac{n+1}{4}\right\rfloor]=[n>2]$$

$$[T_1(n,4)=\sum\limits_{k=1}^{5}\left\lfloor\frac{n+k}{8}\right\rfloor(-1)^{k-1}]=[n>6]$$

$$[T_1(n,5)=\sum\limits_{k=1}^{13}\left\lfloor\frac{n+k}{16}\right\rfloor(-1)^{k-1}-\left(\left\lfloor\frac{n+3}{16}\right\rfloor-\left\lfloor\frac{n+4}{16}\right\rfloor-\left\lfloor\frac{n+10}{16}\right\rfloor+\left\lfloor\frac{n+11}{16}\right\rfloor\right)]=[n>30]$$

Ну и далее по аналогии, знакочередующаяся сумма, в знаменателе степень двойки, часть $k$ не берем, верно начиная с некоторого $n$. Вернуться к $T(n,m)$ можно через

$$\sum\limits_{k=0}^{n}\left\lfloor\frac{k+a}{c}\right\rfloor=\left\lfloor\frac{n+a}{c}\right\rfloor\left(n+a+1-\frac{c}{2}\left(\left\lfloor\frac{n+a}{c}\right\rfloor+1\right)\right)$$

например

$$T(n,1)=2\left\lfloor\frac{n+1}{2}\right\rfloor\left\lfloor\frac{n+2}{2}\right\rfloor-n$$

$$T(n,2)=\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n+1}{2}\right\rfloor+1$$

$$T(n,3)=\left\lfloor\frac{n+1}{4}\right\rfloor\left(n-2\left\lfloor\frac{n+1}{4}\right\rfloor\right)+2-[n=1]$$

От четверки и выше выглядит страшновато, но можно попробовать использовать

$$n=\sum\limits_{k=0}^{m-1}\left\lfloor\frac{n+k}{m}\right\rfloor$$

но все же не уверен, что это как-то облегчит страдания.