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

[Akula]

Я уже года 3 бьюсь над этой проблемой. Большинству преподов она почему-то не интересна. Я уже довольно много фактов доказал, но мне не известно, какие из фактов уже доказаны. Может кто поможет.

[sceptic]

И, если можно, формулировки доказанных Вами утверждений.

[Akula]

sceptic писал(а):

И, если можно, формулировки доказанных Вами утверждений.

N человек стоят по кругу. Считалочка: каждый q-й выкидывается из круга. Надо найти номер оставшегося. (Люди пронумерованы от 0 до N-1). Обозначим f(n,q)
Есть (это известно) рекуррентное соотношение f(n,q)=(f(n-1,q)+q) mod n, где mod - остаток от деления.
Я доказал, что f(n,q) периодична по q с периодом B(n)=НОК(1,2,3,...,n) и что это минимальный период[/math]

[bot]

Хм, уже не раз встречался с этой задачей. С ходу ничего хорошего не находил. Есть ли она у классиков в какой-либо форме - не проверял.
Имхо (долго не думал) - дохлая задача.

[Akula]

Кстати насчет "дохлая задача", может вы и правы, но есть одно но...
Найти f(n,q) - для меня второстепенная задача, а в первую очередь я хочу доказать (по-моему это правда), что на периоде по q каждый человек (от 0 до n-1) остается одинаковое количество раз, тоесть f(n,q)=a (0<=a<=n-1, 1<=q<=B(n)) имеет относительно q ровно B(n)/n решений. Отсюда получается, что f(n,q) - отличный генератор случайных чисел от 0 до n-1. С очень большим периодом (для достаточно больших n)

[Someone]

Akula писал(а):

...Отсюда получается, что f(n,q) - отличный генератор случайных чисел от 0 до n-1. С очень большим периодом (для достаточно больших n)

Ну, насчёт "отличного" ещё посмотреть надо. Величина периода, вообще говоря, ничего не гарантирует. Вон Mersenne Twister имеет вообще умопомрачительный период $2^{19937}-1$ и обеспечивает равномерное распределение точек в 623-мерном кубе с точностью 32 бита (точнее, все точки этого куба на полном периоде встречаются по 2 раза, кроме точки $(0,0,\dots,0)$, которая встречается один раз; впрочем, как объяснял Д.Кнут, вставив в последовательность, генерируемую датчиком, один дополнительный 0, легко исправить этот недостаток). Однако, если Вы попадёте на неудачный отрезок вырабатываемой им последовательности, то будете долго "чихать и кашлять" от такой "случайности".

[Dan_Te]

Что-то когда-то читал про это... в "Конкретной математике", в самом начале вроде бы разобран самый простой случай, q=2, но до конца.

[Akula]

Dan_Te писал(а):

Что-то когда-то читал про это... в "Конкретной математике", в самом начале вроде бы разобран самый простой случай, q=2, но до конца.

Я читал ту статью в Кнуте. Случай q=2 слишком очевидный вообще для разбора. Я даже сталкивался с разбором случая q=3. В последнем выводилась общая формула через константу. Но эта константа определялась только с определенной точностью через нахождение f(n,q) (для достаточно больших n - достаточно большая точность константы) в общем выходит эта формула выиграша не дает. Но меня, как я уже говорил, интересует больше доказательство (или опровержение) равнораспределенности f(n,q)

[Akula]

Someone писал(а):

Однако, если Вы попадёте на неудачный отрезок вырабатываемой им последовательности, то будете долго "чихать и кашлять" от такой "случайности".

На проверенных мною случаях (n<=7) изъянов в случайности моей последовательности я не нашел (субъективно моя точка зрения), для больших n период сильно большой. И одним взглядом я оценить распределенность не могу. А вот период растет очень быстро (для n=28 период приблизительно имеет 10й порядок, а что если взять n где-то 10^6?)

[PAV]

Akula писал(а):

На проверенных мною случаях (n<=7) изъянов в случайности моей последовательности я не нашел (субъективно моя точка зрения),

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

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

[maxal]

Возможно, вам будет интересна моя статья о задаче Иосифа Флавия.

[Anar Yusifov]

Я тоже давно уже её разбирал, нашёл больше 4-х различных по виду решений, однако не это главное. Совершенно уверен что более интерестна может быть лишь замкнутая формула. Потому как рекурсивных много. Несколько раз предпринимал попытки сделать это, но так и не вышло ничего более или менее интерестного. Зато эта задача хорошо развивает мышление и весьма полезна для тренингов. Лично я её использую на семинарах по алгоритмам, которые виду.

P.S. Формула у меня только другие чуть чуть, но на результат это не влияет . А насчёт периода я не интересовался, посижу посмотрю, может что и накопаю.

[Akula]

PAV писал(а):

Существует ряд стандартных тестов на случайность

Да, я проверил тесты на случайность. Стандартных тестов моя последовательность не прошла. (Прошла только тест на равность количества 0 и 1(полиномиальный по-моему)). Я взял n=16 и представил каждое число 4 битами. Но по-моему это еще не повод откидывать этот генератор. Вот, например, WinRar очень плохо архивирует файлы, сгенерированные последовательностями этих чисел.
Не знаю, может придумать тесты для генераторов [0, n-1], потому, как мне кажется, что этот генератор не проходит битовые тесты именно из-за того, что предназначен генерировать величину из [0, n-1]

[PAV]

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

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

[maxal]

PAV писал(а):

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

Вот например: Diehard Battery of Tests of Randomness.