Что такое период последовательности

ЧИСЛОВАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ

ЧИСЛОВАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ – функция вида y = f(x), x О N, где N – множество натуральных чисел (или функция натурального аргумента), обозначается y = f(n) или y₁, y₂,…, y_n,…. Значения y₁, y₂, y₃,… называют соответственно первым, вторым, третьим, … членами последовательности.

Например, для функции y = n 2 можно записать:

Способы задания последовательностей. Последовательности можно задавать различными способами, среди которых особенно важны три: аналитический, описательный и рекуррентный.

1. Последовательность задана аналитически, если задана формула ее n-го члена:

Пример. y_n= 2n – 1 – последовательность нечетных чисел: 1, 3, 5, 7, 9, …

2. Описательный способ задания числовой последовательности состоит в том, что объясняется, из каких элементов строится последовательность.

Пример 1. «Все члены последовательности равны 1». Это значит, речь идет о стационарной последовательности 1, 1, 1, …, 1, ….

Пример 2. «Последовательность состоит из всех простых чисел в порядке возрастания». Таким образом, задана последовательность 2, 3, 5, 7, 11, …. При таком способе задания последовательности в данном примере трудно ответить, чему равен, скажем, 1000-й элемент последовательности.

3. Рекуррентный способ задания последовательности состоит в том, что указывается правило, позволяющее вычислить n-й член последовательности, если известны ее предыдущие члены. Название рекуррентный способ происходит от латинского слова recurrere – возвращаться. Чаще всего в таких случаях указывают формулу, позволяющую выразить n-й член последовательности через предыдущие, и задают 1–2 начальных члена последовательности.

Можно видеть, что полученную в этом примере последовательность может быть задана и аналитически: y_n = 4n – 1.

Последовательность, составленную в этом примере, специально изучают в математике, поскольку она обладает рядом интересных свойств и приложений. Ее называют последовательностью Фибоначчи – по имени итальянского математика 13 в. Задать последовательность Фибоначчи рекуррентно очень легко, а аналитически – очень трудно. n-е число Фибоначчи выражается через его порядковый номер следующей формулой .

На первый взгляд, формула для n-го числа Фибоначчи кажется неправдоподобной, так как в формуле, задающей последовательность одних только натуральных чисел, содержатся квадратные корни, но можно проверить «вручную» справедливость этой формулы для нескольких первых n.

Свойства числовых последовательностей.

Числовая последовательность – частный случай числовой функции, поэтому ряд свойств функций рассматриваются и для последовательностей.

Определение. Последовательность <y_n> называют возрастающей, если каждый ее член (кроме первого) больше предыдущего:

Возрастающие и убывающие последовательности объединяют общим термином – монотонные последовательности.

Пример 1. y₁ = 1; y_n = n 2 – возрастающая последовательность.

Пример 2. y₁ = 1; – убывающая последовательность.

Пример 3. y₁ = 1; – эта последовательность не является не возрастающей не убывающей.

Определение. Последовательность называется периодической, если существует такое натуральное число T, что начиная с некоторого n, выполняется равенство y_n = y_n+T. Число T называется длиной периода.

Пример. Последовательность периодична с длиной периода T = 2.

Арифметическая прогрессия.

Числовую последовательность, каждый член которой, начиная со второго, равен сумме предыдущего члена и одного и того же числа d, называют арифметической прогрессией, а число d – разностью арифметической прогрессии.

Таким образом, арифметическая прогрессия – это числовая последовательность <a_n>, заданная рекуррентно соотношениями

Пример. 1, 3, 5, 7, 9, 11, … – возрастающая арифметическая прогрессия, у которой a₁ = 1, d = 2.

Пример. 20, 17, 14, 11, 8, 5, 2, –1, –4,… – убывающая арифметическая прогрессия, у которой a₁ = 20, d = –3.

Нетрудно найти явное (формульное) выражение a_nчерез n. Величина очередного элемента возрастает на d по сравнению с предыдущим, таким образом, величина n элемента возрастет на величину (n – 1)d по сравнению с первым членом арифметической прогрессии, т.е.

Это формула n-го члена арифметической прогрессии.

Используя явное выражение a_nчерез n, можно доказать следующее свойство арифметической прогрессии: если натуральные числа i, j, k, l таковы, что i + j = k + l, то a_i + a_j= a_k + a_l. Чтобы в этом убедиться, достаточно подставить i, j, k и l вместо n в формулу n-го члена арифметической прогрессии и сложить. Отсюда следует, что если рассматривать первые n членов арифметической прогрессии, то суммы членов, равно отстоящих от концов, будут одинаковы:

Последнее равенство позволяет вычислить сумму первых n членов арифметической прогрессии:

С этой целью берется еще одна такая же сумма, но слагаемые записывается в обратном порядке:

Далее она складывается почленно с исходной суммой, причем слагаемые сразу попарно группируются. В результате

откуда . Это формула суммы n членов арифметической прогрессии.

Арифметической прогрессия названа потому, что в ней каждый член, кроме первого, равен среднему арифметическому двух соседних с ним – предыдущего и последующего. Действительно, так как

Сложение двух последних равенств дает .

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

Пример. При каком значении x числа 3x + 2, 5x – 4 и 11x + 12 образуют конечную арифметическую прогрессию?

Согласно характеристическому свойству, заданные выражения должны удовлетворять соотношению

Решение этого уравнения дает x = –5,5. При этом значении x заданные выражения 3x + 2, 5x – 4 и 11x + 12 принимают, соответственно, значения –14,5, –31,5, –48,5. Это – арифметическая прогрессия, ее разность равна –17.

Геометрическая прогрессия.

Числовую последовательность, все члены которой отличны от нуля и каждый член которой, начиная со второго, получается из предыдущего члена умножением на одно и то же число q, называют геометрической прогрессией, а число q – знаменателем геометрической прогрессии.

Таким образом, геометрическая прогрессия – это числовая последовательность <b_n>, заданная рекуррентно соотношениями

Пример 1. 2, 6, 18, 54, … – возрастающая геометрическая прогрессия b = 2, q = 3.

Пример 2. 2, –2, 2, –2, … – геометрическая прогрессия b = 2, q = –1.

Пример 3. 8, 8, 8, 8, … – геометрическая прогрессия b = 8, q = 1.

Формула n-го члена геометрической прогрессии имеет вид

Можно получить формулу суммы членов конечной геометрической прогрессии.

Пусть дана конечная геометрическая прогрессия

пусть S_n – сумма ее членов, т.е.

Принимается, что q № 1. Для определения S_nприменяется искусственный прием: выполняются некоторые геометрические преобразования выражения S_nq.

Это формула суммы n членов геометрической прогрессии для случая, когда q ≠ 1.

При q = 1 формулу можно не выводить отдельно, очевидно, что в этом случае S_n = a₁n.

Геометрической прогрессия названа потому, что в ней каждый член кроме первого, равен среднему геометрическому предыдущего и последующего членов. Действительно, так как

следовательно, b_n2= b_n–1 b_n+1 и верна следующая теорема (характеристическое свойство геометрической прогрессии):

числовая последовательность является геометрической прогрессией тогда и только тогда, когда квадрат каждого ее члена, кроме первого (и последнего в случае конечной последовательности), равен произведению предыдущего и последующего членов.

Предел последовательности.

Пусть есть последовательность <c_n> = <1>n>. Эту последовательность называют гармонической, поскольку каждый ее член, начиная со второго, есть среднее гармоническое между предыдущим и последующим членами. Среднее геометрическое чисел a и b есть число , или . С ростом n все члены геометрической прогрессии убывают и их значение приближается к нулю. В этом случае принято говорить, что при n, стремящемся к бесконечности, данная последовательность сходится и нуль есть ее предел. Записывается это так:

Строгое определение предела формулируется следующим образом:

Источник

Период псевдослучайной последовательности

Дата добавления: 2014-11-28 ; просмотров: 5006 ; Нарушение авторских прав

Оба рассмотренных генератора основаны на получении последовательности целых чисел, причем каждое следующее число полностью определяется предыдущим числом (и параметрами генератора, которые в процессе счета не изменяются). Поэтому очевидно, что при большом количестве запусков генератора числа в последовательности после какого-то шага начнут повторяться. Очевидно, что из целых чисел, лежащих в диапазоне от 0 до (M-1), можно в лучшем случае сформировать последовательность, не содержащую повторов, длиной не более M.

Периодом генератора называют количество неповторяющихся чисел, которые генератор может сформировать при заданных параметрах и «затравке». Обычно период генератора получается меньше M. Генератор может считаться достаточно хорошим, если он обеспечивает период последовательности более M/4 для большинства «затравок».

При экспериментальном определении периода последовательности следует учитывать, что число-«затравка» может не повторяться никогда, как и несколько последовательно получаемых из нее чисел (апериодическая часть последовательности). Тем не менее, каждая «затравка» задает то или иное подмножество из M целых чисел, которые будут циклически перебираться генератором.

Примером последовательности с апериодической частью, может служить последовательность, получаемая с помощью мультипликативного датчика с параметрами:

При указанных параметрах генератор выдает три апериодических числа: 2285, 1451, 7292 — после чего, начиная с числа 45065, идет периодическая часть последовательности с периодом всего-навсего 93 числа. Распределение этих 93 чисел оказывается почти идеально равномерным, и по критерию Пирсона вероятность подтверждения гипотезы получается равной 100%, однако такую последовательность никак нельзя назвать «хорошей».

Для определения периода генератора необходимо зафиксировать одно из целых чисел, полученных в результате работы процедуры генератора, и подсчитать количество вызовов процедуры генератора до того момента, когда в результате получится то же целое число, сгенерировав, таким образом, не менее M чисел. Если при генерации M чисел повторений не обнаружено, — значит, зафиксированное число относится к апериодической части псевдослучайной последовательности и следует взять другое, более «позднее» число для проверки повторения. Следует заметить, что апериодическая часть в подавляющем большинстве случаев все же состоит из единственного числа-«затравки» или отсутствует вовсе.

Проводить проверку повторения вещественных чисел из диапазона [0,1) не следует.

Пример анализа последовательности случайных чисел.

В качестве примера для анализа рассмотрим последовательность из 25 чисел, получаемых с помощью мультипликативного датчика со следующими параметрами: M=1000, a=47, b=1. В качестве x₀ возьмем 1 (табл. 5.1).

О периоде. Прежде всего, в полученной последовательности есть одна отрадная особенность: числа не повторяются (период больше 25). С другой стороны, если проанализировать получаемую последовательность целых чисел x_i, можно видеть, что все они заканчиваются только на 8, 7, 0 и 1. Таким образом, из 10 возможных последних цифр используются лишь 4, поэтому из 1000 возможных чисел получится не более 400 неповторяющихся чисел с

такими последними цифрами. На самом деле период этой последовательности равен 200 для большинства «затравок», включая нашу единицу, но для некоторых затравок он составит 40 или даже всего 8 неповторяющихся чисел.

Математическое ожидание. Для случайной величины X, равномерно распределенной на интервале от A до B, мат.ожидание вычисляется по формуле:

,

следовательно, для равномерного распределения от 0 до 1 MX=0.5.

Оценка мат. ожидания (выборочное среднее) для выборки объемом N чисел x_i вычисляется по формуле.

(Следует использовать оценку мат. ожидания, а не теоретически рассчитанное мат. ожидание.)

Для нашей последовательности из 25 чисел выборочная дисперсия составляет 0.0816.

Для реальных выборок объемом несколько тысяч значений ошибка, как правило, не должна превышать 1%.

Критерий Пирсона. Критерий Пирсона позволяет оценить вероятность того, что данная выборка является выборкой значений случайной величины (СВ) с заданным законом распределения. Теоретическое обоснование этого критерия изучается в рамках курса «Теория вероятности и мат. статистика».

Для применения критерия Пирсона интервал возможных значений СВ разбивается на L равных отрезков. Для каждого отрезка подсчитывается G_i — количество попаданий в него чисел из выборки, а также P_i — ожидаемое количество попаданий в случае, если СВ имеет заданное распределение. Подсчитанные значения G_i позволяет построить гистограмму, по которой можно визуально оценить соответствие заданного распределения и полученного. Затем рассчитывается коэффициент хи-квадрат: , после чего по таблице распределения хи-квадрат для полученного коэффициента и (L-1) степени свободы находят вероятность истинности гипотезы о том, что исследуемая выборка имеет заданный закон распределения.

При расчете получаем 1.2, и по таблице распределения хи-квадрат с четырьмя степенями свободы определяем, что вероятность того, что наша выборка соответствует равномерному распределению на интервале от 0 до 1, составляет

87%. Хорошо это или плохо? Это хороший результат. Принято считать хорошими значения вероятности от 70 до 95%. Если получено меньшее значение, то велика вероятность, что заданное распределение не получено. Если вероятность более 95%, то велика вероятность того, что выборка не случайная. Наглядный пример такой ситуации: если по методу мультипликативного датчика построить генератор, взяв a=1, b=1, M=1000, и произвести 999 испытаний, то гистограмма идеально совпадет с ожидаемой и критерий Пирсона даст вероятность 100%. Однако, очевидно, что получаемая последовательность (арифметическая прогрессия) никак не может считаться случайной.

Источник

Найти период конечной периодической последовательности

краткое объяснение.

Я пытаюсь автоматически извлечь этот период из этой последовательности. Проблема в том, что я не знаю ни длины периода, ни положения, из которого последовательность становится периодической.

полное описание (может потребоваться math)

Я изучаю комбинаторную теорию игр, и краеугольный камень этой теории требует расчета Grundy values игры графика. Это порождает бесконечную последовательность, которая во многих случаях становится в конце концов периодические.

мой неэффективный подход заключается в том, чтобы попробовать все возможные смещения и каждый возможный период. Постройте последовательность, используя эти данные, и проверьте, совпадает ли она с оригиналом. Я не делал никакого нормального анализа, но похоже, что он по крайней мере квадратичен с точки зрения сложности времени.

вот мой быстрый код python (не протестировали его должным образом):

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

есть ли что-нибудь более эффективное?

3 ответов

я бы начал с построения гистограммы значений в последовательности

сортировка по возрастанию гистограмме

узнайте срок

the GCD(6,4)=2 и GCD(6,3)=3 вы должны проверить, по крайней мере +/-1 вокруг GCD результаты так что возможные периоды вокруг:

так что проверьте T= <3,4,5,6,7>просто чтобы быть уверенным. Использовать всегда GCD между наивысшими значениями и низкой счету. Если последовательность имеет много различных чисел, вы также можете сделать гистограмму подсчетов, проверяя только наиболее распространенные значения.

чтобы проверить срок действия, просто возьмите любой элемент в конце или середине последовательности (просто используйте вероятную периодическую область). Затем ищите его в непосредственной близости от вероятного периода до (или после) его возникновения. Если найдено несколько раз, вы получили правильный период (или его несколько)

вам точный период

найти смещение

[edit1] было любопытно, поэтому я пытаюсь закодировать его на C++

я упростил / пропустил несколько вещей (предполагая, что по крайней мере половина массива является периодической), чтобы проверить, не сделал ли я какую-то глупую ошибку в своем алгоритме, и здесь результат (работает как ожидалось):

код все еще не оптимизированный. Для n=10000 к 5ms настройки мои. Результат в t0 (смещение) и T (период). возможно, вам придется немного поиграть с константами treshold

Примечание: если есть срок P1 длиной L, тогда есть также Точка P2 С такая же длина, L, так что входная последовательность заканчивается точно на P2 (то есть у нас нет частичного периода в конце).

действительно, другой период той же длины всегда может быть получен путем изменения смещения. Новый период быть ротацией начального периода.

например, следующая последовательность имеет период длины 4 и смещение 3:

0 0 0 (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2

но он также имеет период с той же длиной 4 и смещением 5, без частичного периода в конце:

0 0 0 1 2 (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2)

подразумевается, что мы можем найти минимальную длину периода путем обработки последовательности в обратном порядке и поиска минимального периода с использованием нулевого смещения от конец. Один из возможных подходов-просто использовать текущий алгоритм в обратном списке, без необходимости циклических смещений.

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

однажды мне пришлось сделать что-то подобное. Я использовал грубую силу и здравый смысл, решение не очень элегантное, но оно работает. Решение всегда работает,но вы должны установить правильные параметры (k, j, con) в функции.

Как вы можете заметить, что точность зависит от переменных j и k но если вы установите их на очень большие числа, это всегда будет правильно.

упрощенная версия

здесь max_period это максимальный период, который вы хотите найти, и test_numb сколько номеров последовательности вы хотите проверить, чем больше, тем лучше, но вы должны сделать max_period+test_numb

Источник

Числовая последовательность

Определение 1. Числовой последовательностью называется функция, аргументом которой является множество всех натуральных чисел, или множество первых n натуральных чисел.

Обозначается числовая последовательность так:

где −i-ый член последовательности.

При словестном задании последовательности, описывается из каких элементов она состоит.

Последовательность нечетных чисел:

Последовательность простых чисел :

Последовательности (1) и (2) мы задали словестно.

Последовательность нечетных чисел аналитически задается формулой

Отметим, что последовательность простых чисел невозможно задать аналитически.

Пример задания рекуррентной последовательности:

В этой последовательности

Пример стационарной последовательности:

Возрастающие и убывающие последовательности

Определение 3. Последовательность, в которой каждый последующий член (кроме первого) больше предыдующего, называется возрастающей :

Определение 4. Последовательность, в которой каждый последующий член (кроме первого) меньше предыдующего, называется убывающей :

Пример 1. Выяснить, монотонна ли последовательность

Решение. Запишем n+1 член последовательности (подставим вместо n, n+1):

Найдем разность членов и :

.

(3)

Так как n=1,2,3. то правая часть уравнения (3) положительна. Тогда:

Таким образом, каждый последующий член последовательности больше предыдующего. Следовательно последовательность является возрастающим (и монотонным).

Пример 2. Выяснить, при каких значениях a последовательность (b_n) является возрастающей и при каких, убывающей:

Решение. Запишем n+1 член последовательности (вместо n подставим n+1):

Найдем разность членов и :

(4)

Посмотрим на правую часть выражения (4). Если a 10, то . Тогда последовательность является убывающей. При a=10 . Последовательность имеет одинаковые члены:

т.е. имеем дело с последовательностью

Очевидно, что последовательность (5) не является монотонной. Она является стационарной последовательностью.

Ограниченные и неограниченные последовательности

Определение 5. Последовательность (y_n) называется ограниченной сверху, если существует такое число k, что y_n Определение 6. Последовательность (y_n) называется ограниченной снизу, если существует такое число k, что y_n>k при любом n.

Определение 7. Последовательность (y_n) называется ограниченной, если она ограничена и сверху, и снизу.

Пример 3. Показать, что последовательность (a_n) является монотоннной и ограниченной:

Решение. Запишем n+1 член последовательности (вместо n подставим n+1):

Найдем разность членов и :

(6)

Правая часть равенства (6) положительна при любых натуральных чисел n. Следовательно последовательно (a_n) возрастающая (и монотонная).

Далее, сделаем эквивалентное преобразование для проследовательности (5):

Из выражения (7) видно, что при любых n a_n≤1. Т.е. хотя последовательность возрастает, то остается меньше числа 1 (ограничена сверху). Запишем несколько членов данной последовательности, задав n=1,2,3.

Так как последовательность возрастающая, то все члены последовательности не меньше . Тогда последовательность ограничена также и снизу. Таким образом последовательность ограничена и всерху, и снизу, т.е. является ограниченной последовательностью.

Сходящиеся и расходящиеся последовательности

Рассмотрим две числовые последовательности:

На координатной прямой изобразим члены этих последовательностей:

Предел числовой последовательности

Точка, к которой приближаются члены последовательности при увеличении n, называется пределом последовательности. Для последовательности (10) пределом является число 0. Более строго предел последовательности определяется так:

Определение 8. Число k называют пределом последовательности (y_n), если для любой заранее выбранной окресности точки k, можно выбрать такой номер n₀, чтобы все члены последовательности, начиная с номера n₀ содержались в указанной окрестности.

Если k является пределом последовательности (y_n), то пишут ( стремится к k или сходится к k).

Обозначают это так:

Выраженние (11) читается так: предел проследовательности , при стремлении n к бесконечности равен k.

Изложим некоторые пояснения к определению 8.

Пусть выполнено (11). Возьмем окрестность точки k, т.е. интервал , где радиус этой окрестности ( >0). По определению, существует номер n₀, начиная с которого вся последовательность содержится в указанной окресности, т.е.

.

Если же взять другую окресность (пусть ), то найдется другой номер n₁, начиная с которого, вся последовательность содержится в указанной окрестности, но этот номер будет больше n₁ > n₀.

Пример 4. Дана полследовательность (y_n):

Доказать, что .

Решение. Найдем любую окрестность точки 0. Пусть ее радиус равен r. Тогда всегда можно выбирать n₀ так, чтобы .

Пусть, например, r=0.001. Вычислим n‘ из уравнения

.

В качестве n₀ берем 501. Имеем:

.

Запишем члены последовательности (12) начиная с номера 501:

.

Далее, учитывая (13), имеем:

.

Следовательно, все члены последовательности (12) начиная с номера 501 попадают в окресность . А по определению 8, это означает:

Пример 5. Дана полследовательность (y_n):

Доказать, что .

Решение. Найдем любую окрестность точки 2. Пусть ее радиус равен r. Тогда всегда можно выбирать n₀ так, чтобы

.

.

Неравенство в (17) всегда выполняется так как n₀ натуральное число, а правая часть неравенства отрицательно (это означает, что для любого n₀). Из неравенства (16) можно найти номер n₀, начиная с которого члены последовательности попадают в окресность (2−r; 2+r). Например, пусть r=0.001, тогда . Тогда нужно брать n₀=2000. И тогда все члены последовательности, начиная с номера 2000 попадают в окрестность (2−r; 2+r).

Запишем члены последовательности, начиная с номера 2000:

.

Легко проверить, что . Тогда, учитывая, что данная последовательность возрастающая (см. пример 1), получим:

.

Пример 6. Найти предел последовательности

Решение. Выполним некоторые преобразования выражения (18):

Тогда последовательность (18) можно переписать так:

(19)

Как видно из (19), пройдя по членам последовательности слева направо, из числа 1 вычитается все меньшее и меньшее положительное число. Т.е. последовательность приближается к числу 1. Тогда 1 является пределом последовательности (19) и (18):

Свойства сходящихся последовательностей

Сходящиеся последовательности обладают рядом свойств.

Свойство 1. Если последовательность сходится, то только к одному пределу.

Свойство 2. Если последовательность сходится, то она ограничена.

Свойство 3. Если последовательность монотонна и ограничена, то она сходится (теорема Вейерштрасса).

Предел стационарной последовательности равен значению любого члена последовательности:.

Теорема. Если , то

1. Предел суммы равен сумме пределов:

2. Предел произведения равен произведению пределов:

3. Предел частного равен частному пределов:

4. Постоянный множитель можно вывести за знак предела:

Пример 7. Найти предел последовательности:

Решение. Так как , то

.

Пример 8. Найти предел последовательности:

Решение. Применив правило «предел суммы» теоремы, получим

.

Пример 9. Вычислить:

Решение. Делим числитель и знаменатель дроби на наивысшую из имеющихся степень переменного n. Далее используем правило «предел суммы» для числителя и знаменателя и правило «предел частного»:

Источник