Алгоритм Конвея

[Руст]

Эта последовательность так же не работает. Ошибка в обоих по видимому, заключается в подряд идущих числах 11/13 и 13/11, приводящих к зациклению. Хотя тут не всё так просто, и по этому написал "по видимому".

[sceptic]

Лет 17-18 назад я "игрался" с этим генератором (на той еще технике ), до тех чисел, до которых я добрался, генератор работал корректно.

[Руст]

Для недоверчивых отправлю маленькую программу для проверки работоспособности чисел. По моим числам все простые до 1000 программа выдает за 2-3 минуты, в то время как для чисел Конвея вообще не встречаются степени двойки, а следовательно нет вывода.

[sceptic]

е-mail Вы знаете.

[Руст]

У меня была идея напрямую и эффективно доказать теорему Матиясевича (10 проблема Гильберта) из табличного алгоритма для рекурсивной функции. Т.е. для заданной таблицы, реализующей вычисление рекурсивной функции указать многочлен корнями которого являются значения рекурсивной функции. Но так и оставил эту идею не реализованной. Если кто хочет, может попробовать эту идею.

[Руст]

Я не прав. Числа Конвея так же работают. Раньше в программе программы надо было рациональные числа кодировать в виде строк в ручную (что нетрудно ошибиться), переделал кодировку так, чтобы можно было вводит рациональные числа в виде числитель и знаменатель. Вчера даже после этого получал зацикливание, т.е. ошибся при вводе даже при таком упрощении, так как после проверки maxal сегодня ещё раз проверил и они считают. Единственное в свое оправдание могу сказать, что ввод десяти чисел проще (меньше вероятность ошибки) и программа считает быстрее.

[Sonic86]

В книге "Живые числа" (с 70) нашел следующее определение простых чисел.
Если начиная с $N=2$ заменять $N$ на $\alpha N$, где $\alpha$ - первое из 14 чисел:
17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55,
для которого $\alpha N$ - целое, то в числах получающейся последовательности
показатели двойки будут последовательностью простых чисел.

Объясните мне - это как так? Написано, что это - из теории игр.
Мне кажется - это неверно, так как максимум разности между простыми растет
до бесконечности, а степень двойки среди числителей конечного числа дробей
ограничена для любого набора дробей.

// перенесено из темы Простые числа // maxal

[Руст]

Количество чисел у меня уменьшено до 10. Здесь это ранее обсуждалось. Мне кажется что можно уменьшит до 9, но руки ни как не доходят.

[sceptic]

Зайдите сюда

Sonic86 писал(а):

В книге "Живые числа" (с 70) нашел следующее определение простых чисел.
Если начиная с $N=2$ заменять $N$ на $\alpha N$, где $\alpha$ - первое из 14 чисел:
17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55,
для которого $\alpha N$ - целое, то в числах получающейся последовательности
показатели двойки будут последовательностью простых чисел.

Объясните мне - это как так? Написано, что это - из теории игр.
Мне кажется - это неверно, так как максимум разности между простыми растет
до бесконечности, а степень двойки среди числителей конечного числа дробей
ограничена для любого набора дробей.

Это не так. Порождаемая здесь последовательность чисел содержит в себе бесконечную подпоследовательность натуральных чисел - степеней двойки, причем эти степени и есть в точности множество простых. Почему это происходит - объясняется в статьях, упомянутых в вышеуказанном топике.

[sceptic]

to maxal
В том топике, в частности, я просил книгу "Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, 1987" - и Вы не нашли ее тогда. Прошло два с лишком года - книга появилась (если интересует - в гигапедии: из 3-х линков лучшее качество предлагают первые 2).

Добавлено спустя 1 час 6 минут 43 секунды:

to p-h-o-e-n-i-x: знать предыдущие простые необязательно

p-h-o-e-n-i-x писал(а):

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

Собственно, машина Конвея предоставляет алгоритм получения из простого числа $P$ следующего за ним простого $P'$:
1. Берем $N=2^P$.
2. Умножаем $N$ на числа $17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55$ и определяете $a$ — первое из них, для которого число $aN$ — целое.
3. Проверяем, не является ли это число степенью двойки:
если $aN=2^k$, то $k$ и есть искомое следующее простое $P'$ - в этом случае алглритм заканчивает работу;
если не является, то переобозначаем $N:=aN$ и отправляемся на пункт 2.

Конвей гарантирует, что этот алгоритм обязательно остановится и выдаст искомое следующее простое число. Как видите, для вычисления следующего простого числа (за простым $P$) знать предыдущие простые (до $P$) необязательно.
Алгоритм, правда, страшно неэффективен. Но это не столь важно, не правда ли?

Любопыто, в выше упомянутой книге Конвей строит аналогичную машину, генерирующую по номеру $n$ $n$-ую цифру (десятичную) числа $\pi$ после десятичной точки.

[Sonic86]

Посчитал с помощью машины Конвея простые p от 2 до 3001 (431 чисел) и номера шагов N(p), на которых она выдает их.
Так как я не понимаю, как она работает (может, объяснит кто-нибудь, как она работает?), то я провел анализ ее работы на асимптотику.
Кривая $ln(N(p))/ln(p)$ падает до $3,039$. Может быть, она падает до 3 (?)
Кривая $N(p)/p^3$ падает примерно до 1,347 (и часто дергается, среднее доходит до 1,37).
Кривая $N(p) - 1,347p^3$ с ростом р начинает сильно осциллировать.

З.Ы. Если ввести в машину составное число, то она все равно выдает простые, большие данного.
Таким образом, ее можно использовать для проверки простоты данного числа!
Например так: для данного n вводим в машину n-1. Если она выдаст n, то n - простое, иначе - составное.
(тоже задача - попробуйте это доказать)
З.З.Ы. Вопрос: можно ли уменьшить число простых множителей в исходных дробях?
У Руста по ходу 6 (В этой машине оно равно 10)... надо было сразу Руста программировать...
З.З.З.Ы. Уважаемый Руст! У меня дробях, которые здесь написаны, машина почему-то зациклилась (я вручную проверил).
Я еще в вашей статье посмотрю.

[Руст]

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

[Sonic86]

Дык, я не понимаю, как он работает!!! Откуда делимость???

А статью Вашу я не нашел сейчас

[sceptic]

Если Руст не возражает и у него нет более свежей версии статьи (у меня статья 2-летней давности, которую мне выслал Руст в феврале 2006 г.).

[Руст]

Я не возражаю. У меня у самого осталась только одна бумажная версия статьи и нет электронной версии. Когда то я писал для Кванта подробную на 9 стр. статью. Но она не принята. Коротко это есть вычислимость в сетях Пэтри и эти операции непосредственно выражаются через таблицы. Аддитвному представлению строки в таблице сопоставляется мультипликативное умножение на произведение простых в соответствующих степенях.