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 ] 

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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