2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 итерации в вычислении целочисленного корня
Сообщение13.08.2019, 04:36 
Модератор
Аватара пользователя


11/01/06
5660
Несложно видеть, что для фиксированного целого $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$.

 Профиль  
                  
 
 Re: итерации в вычислении целочисленного корня
Сообщение13.08.2019, 06:26 


05/09/16
11468
maxal в сообщении #1410109 писал(а):
Значения $g(x)$ для первой сотни значений $n$ такие:

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

 Профиль  
                  
 
 Re: итерации в вычислении целочисленного корня
Сообщение13.08.2019, 06:52 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
То значение, при котором количество итераций минимально

 Профиль  
                  
 
 Re: итерации в вычислении целочисленного корня
Сообщение13.08.2019, 07:04 
Заслуженный участник


20/12/10
8858
ex-math в сообщении #1410112 писал(а):
То значение, при котором количество итераций минимально
А если в качестве $a$ взять $[\sqrt{n}]$? Это же неподвижная точка для $f(x)$, вроде бы.

 Профиль  
                  
 
 Re: итерации в вычислении целочисленного корня
Сообщение13.08.2019, 07:05 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: итерации в вычислении целочисленного корня
Сообщение13.08.2019, 08:58 
Заслуженный участник


20/12/10
8858
В плане вычислений это хуже, но аналитически выглядит проще: $$f(x)=\left[\frac{x^2+n}{2x}\right]$$(знак целой части внутри можно убрать).

 Профиль  
                  
 
 Re: итерации в вычислении целочисленного корня
Сообщение19.08.2019, 12:24 
Аватара пользователя


22/11/13
496
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$$
но все же не уверен, что это как-то облегчит страдания.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group