Проблема Флавия и псевдослучайные числа

[Akula]

PAV писал(а):

Для каких целей вы думаете можно использовать данный генератор?

Я не стремлюсь добиться того, чтоб мой генератор признали хорошим. Я просто буду использовать его - и все. А использовать - везде, где понадобятся мне случайные числа (Это в основном игры). Все равно реальный человек вряд ли предскажет следующее случайное число моей последовательности.

[Akula]

Но на самом деле все эти рассуждения о случайности уводят в сторону от основной моей цели: я хочу доказать равновероятность на периоде и найти скорость возрастания периода ( НОК(1, ... , n) ) замкнутой формулой. А уж потом, если удастся, то поискать замкнутую формулу и для самой функции (или доказать, что такой нет)

[maxal]

Akula писал(а):

найти скорость возрастания периода ( НОК(1, ... , n) ) замкнутой формулой

НОК(1,2,...,n) - это т.н. функция Ландау, довольно хорошо изученная.

[Егор]

maxal писал(а):

НОК(1,2,...,n) - это т.н. функция Ландау, довольно хорошо изученная.

Разве это функция Ландау? Вроде бы, это $\exp(\psi(x))$, где $\psi(x)$ - вторая функция Чебышёва. Таким образом, НОК(1,2,...,n) растёт примерно как экспонента.

Вопрос: в результате какой операции из колец ${\mathbb Z}_m$ и ${\mathbb Z}_n$ получается структура, состоящая из $[m,n]$ элементов?

[maxal]

Егор писал(а):

maxal писал(а):

НОК(1,2,...,n) - это т.н. функция Ландау, довольно хорошо изученная.

Разве это функция Ландау? Вроде бы, это $\exp(\psi(x))$, где $\psi(x)$ - вторая функция Чебышёва. Таким образом, НОК(1,2,...,n) растёт примерно как экспонента.

Да, конечно.
А функцию Ландау здесь можно использовать для верхней оценки: НОК(1,...,n) <= g(n*(n+1)/2)

[Akula]

maxal писал(а):

А функцию Ландау здесь можно использовать для верхней оценки: НОД(1,...,n) <= g(n*(n+1)/2)

Вы не ошиблись? НОД или НОК?
$\lim\limits_{n \to \infty}\frac {\textbf{ln}(g(n))}{\sqrt{n\textbf{ln}n}}=1$, значит g(n)\sim e^{\sqrt{n\textbf{ln}n}}, получается g\left(\frac {n(n+1)}{2}\right)\sim e^{\sqrt{\frac{n(n+1)}{2}\textbf{ln}\frac{n(n+1)}{2}}}.

[maxal]

Akula писал(а):

Вы не ошиблись? НОД или НОК?
$\lim\limits_{n \to \infty}\frac {\textbf{ln}(g(n))}{\sqrt{n\textbf{ln}n}}=1$, значит g(n)\sim e^{\sqrt{n\textbf{ln}n}}, получается g\left(\frac {n(n+1)}{2}\right)\sim e^{\sqrt{\frac{n(n+1)}{2}\textbf{ln}\frac{n(n+1)}{2}}}.

НОК конечно. Разговор про него шел. Исправил.

[Akula]

maxal писал(а):

НОК конечно.

Верно ли, что $\verb или выполняется только неравенство?
И не подскажете ли где найти это доказательство связи с НОК функции Ландау?

[maxal]

Akula писал(а):

И не подскажете ли где найти это доказательство связи с НОК функции Ландау?

По определению функция Ландау $g(n)=\max\limits_{k_1+\dots+k_m=n} \verb, где максимум берется по всем возможным положительным целым числам $k_1,\dots,k_m$ с суммой $k_1+\dots+k_m=n$. Понятно, что для $n=m(m+1)/2$ значения $k_i=i,\ i=1,\dots,m$ являются только одним из возможных вариантов. Откуда $\verb.

[Akula]

Я, кажется, нашел скорость возрастания НОК(1,...,n).
$\verb. Я не ошибся? Так просто?
Было бы неплохо еще и доказательство достать... на странице написано, что этот факт следует из "теоремы о простых числах".
Помогите его доказать, плиз.

[Lucifer Anh]

Подскажите, пожалуйста, как доказать, что функция Ландау сходится к $\exp( \sqrt{n\ln n} )$

[Руст]

На счёт сходится это по моему слишком сильно. Я в форуме НГУ доказал более слабый результат

$$\lim_{n\to \infty } \frac{ln(g(n)}{\sqrt{n\ln n }}=1.$$

Можно показать, что пределы от функций:

$$g(n)-e^{\sqrt{n \ln n }}, \frac{g(n)}{e^{\sqrt{n \ln n}}}$$

не существуют.