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

[sceptic]

Вот цитата из книжечки Живые числа (авторы Боро В. Цагир Д. Рольфс Ю.) (стр. 69-70):

"К списку необычных определений простых чисел, с которого мы начали наше путешествие, следует добавить еще одно, на этот раз из теории игр. А именно (по Конвею), отправляясь от N = 2, на каждом шаге мы заменяем N на а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,

для которого число аN — целое. Для получающейся при этом последовательности 2, 15, 825, 725, 1925, ... все фигурирующие в ней степени двойки будут иметь вид $2^p$, где р — простые, идущие в своем естественном порядке! С помощью хорошего калькулятора можно таким путем за несколько минут отыскать первые 4 или 5 простых чисел."

Кто-нибудь знает откуда "выросло" это представление? Ссылки на соотв. статьи, книги? Это тот Конвей, кторый - автор игры "Жизнь" (John Horton Comway)?

[Руст]

Да, это он. Однако, приведённые там числа неправильные. Вот более короткий алгоритм:
r(1)=5/3,r(2)=14553/500,r(3)=63/10,r(4)=7/125,r(5)=33/65,r(6)=1/5,r(7)=26/77,r(8)=10/7,r(9)=25/13,r(10)=125. ("Некоторое уточнение алгоритма Конвея" Вестник МГУ, №3,2005).

[sceptic]

Руст писал(а):

Да, это он. Однако, приведённые там числа неправильные. Вот более короткий алгоритм:
r(1)=5/3,r(2)=14553/500,r(3)=63/10,r(4)=7/125,r(5)=33/65,r(6)=1/5,r(7)=26/77,r(8)=10/7,r(9)=25/13,r(10)=125. ("Некоторое уточнение алгоритма Конвея" Вестник МГУ, №3,2005).

Спасибо за ссылку. Но как добраться до статьи?

[Руст]

Могу отправить по e-maile. Укажите адрес.

[sceptic]

*****
Заранее спасибо.

[zkutch]

Уважаемый Руст
Надеюсь не очень потревожу вас, если попрошу отправить эту статью и на мейл [e-mail]
Заранее благодарю.

[незваный гость]

В связи с обширным интересом публики, не будете ли Вы так любезны положить статью куда-нибудь (например, rapidshare.de), а всем нам дать одну ссылку.

Не мое это дело, кстати, но вот помещать свой email на сети я не советую -- спам замучает...

[maxal]

sceptic писал(а):

Кто-нибудь знает откуда "выросло" это представление? Ссылки на соотв. статьи, книги? Это тот Конвей, кторый - автор игры "Жизнь" (John Horton Comway)?

См. алгоритм FRACTRAN и последовательность A007542.

[maxal]

А вот статья Рустема "Некоторое уточнение алгоритма Конвея". Надеюсь, он не будет против того, что я ее выложил.

[Руст]

Лет 10-15 назад я с подробными доказательствами писал это для детского журнала "Квант", там не приняли, а электронного варианта у меня не сохранилось. Суть сводится к сопоставлению простым числам столбцы с их номером и сложение строк умножению на рациональное число. Для упорядочения элементарных процессов надо делать дополнительные столбцы (не участвующие непосредственно в элементарном процессе) с переключателями. При проверке на простоту требуется выполнять четыре элементарных процесса, соответственно требуется три переключателя. Это приводит к размеру таблицы 14*10. Но можно объединять переключатели. Например, устроив третье переключение на месте двух (третий переключатель открыт тогда и только тогда, когда открыты оба переключателя) таблица сокращается до 12*8. Объединив все переключатели в один, при этом переключение делаются элементами (3,-3),(2,-2),(1,-1) и соответственно появляются рациональные числами не совпадающие со своими радикалами (когда простые числа входят в разложение не в первой степени) таблицу удается сократить до 10*6. Попытка придумать алгоритм ещё короче, у меня не увенчались успехом.

[sceptic]

Особенно maxal'у.
Теперь бы добраться до всплывших работ :
1. Conway, J. H. Unpredictable Iterations. In Proceedings of the 1972 Number Theory Conference Held at the University of Colorado, Boulder, Colo., Aug. 14-18, 1972. Boulder, CO: University of Colorado, pp. 49-52, 1972.
2. Conway, J. H. Fractran: A Simple Universal Programming Language for Arithmetic. Ch. 2 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 4-26, 1987. (Хорошо бы и на всю книгу посмотреть)
3. R. K. Guy, Conway's prime producing machine. Math. Mag. 56 (1983), no. 1, 26-33.

[maxal]

1. Есть только аннотация с MathSciNet:

Цитата:

MR0392904 (52 #13717)
Conway, J. H.
Unpredictable iterations.
Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), pp. 49--52.
Univ. Colorado, Boulder, Colo., 1972.
10N05
References: 0 Reference Citations: 3 Review Citations: 2

Lothar Collatz had defined the function $g(n)$ to be $n/2$ for $n$ even and $3n+1$ for $n$ odd and conjectured that for every positive $n$ there exists a $k$ such that $g^k(n)=1$. The author considers generalizations of the form $g(n)=a_in+b_i (n\equiv i\,\text{mod}\,P)$ where the $a$'s and $b$'s are chosen so that $g(n)$ is always an integer. He shows that even when $b_i=0$ there is no algorithm for recognizing whether for given $a$'s and $n$ there exists a $k$ such that $g^k(n)=1$.

The main idea of the proof is to simulate Minsky machines.

\{For the entire collection see MR0351969 (50 \#4457).\}

Reviewed by Ju. V. Matijasevic

2. Книги нет.

3. Статья имеется: R. K. Guy, Conway's prime producing machine.

[maxal]

Руст писал(а):

Да, это он. Однако, приведённые там числа неправильные.

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

[Руст]

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

[maxal]

Руст писал(а):

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

На всякий случай повторяю ссылку на MathWorld. А числа там такие:

17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1