В частности, PRIMEGAME Конвея .

Это алгоритм, разработанный Джоном Х. Конвеем для генерации простых чисел с использованием последовательности из 14 рациональных чисел:

 A   B   C   D   E   F   G   H   I   J   K   L   M   N
17  78  19  23  29  77  95  77   1  11  13  15  15  55
--  --  --  --  --  --  --  --  --  --  --  --  --  --
91  85  51  38  33  29  23  19  17  13  11  14   2   1

Например, F - это дробь 77/29 .

Итак, вот как алгоритм находит простые числа. Начиная с числа 2, найдите первую запись в последовательности, которая при умножении дает целое число. Вот это M, 15/2, которая производит 15. Затем для этого целого числа 15найдите первую запись в последовательности, которая при умножении дает целое число. Это последний N, или 55/1, который дает 825. Запишите соответствующую последовательность. (Проницательный из вас может распознать это как ФРАКТРАН программу .)

После нескольких итераций вы получите следующее:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4 ...

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

2 ... 2^2 ... 2^3 ... 2^5 ... 2^7 ... etc.

Таким образом, получая простые числа. Это OEIS A007542 .

Соревнование

Для заданного числа ввода n, либо с нулями, либо с одним индексом (на ваш выбор), либо выведите первые nчисла этой последовательности, либо выведитеn номер этой последовательности.

Примеры

Приведенные ниже примеры выводят nth-й член последовательности с нулевым индексом.

 n   output
 5   2275
19   4
40   408

правила

• Если применимо, вы можете предположить, что ввод / вывод будет соответствовать целочисленному типу вашего языка.
• Вход и выход могут быть заданы любым удобным способом. .
• Либо полная программа или функция приемлемы. Если функция, вы можете вернуть вывод, а не распечатать его.
• Стандартные лазейки запрещены.
• Это код-гольф, поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код (в байтах).

Python 3 , 173 165 153 145 144 136 135 127 126 125 108 107 104 байта

f=lambda n:2>>n*2or[f(n-1)*t//d for t,d in zip(b"NM_M\r7",b"[U3&!\r")if f(n-1)*t%d<1][0]

Попробуйте онлайн!

• -30 байтов благодаря Джонатану Фреху!
• -3 байта благодаря Линн!

2>>n*2является 2для n==0и0 в противном случае.

103 байта, если мы можем вернуть поплавки.

ФРАКТРАН , 99 байт

17/2821 78/2635 19/1581 23/1178 29/1023 77/899 95/713 77/589 1/527 11/403 13/341 15/434 15/62 55/31

Попробуйте онлайн!

Программа принимает 2*31^nв качестве входных данных, которые используются в качестве исходного состояния.

Все дроби в исходной программе FRACTRAN были разделены на 31 (первый неиспользуемый простой регистр), поэтому программа останавливается на n-й итерации.

Желе , 49 43 байта

ד×NŒçøM_M¢¿ÆÐÐ7‘“[U3&!øçŒ×Æ¿Ç£¢‘:@xḍɗḢ
2Ç¡

Попробуйте онлайн!

• -6 байт благодаря милям

Python 3 , 107 байт

f=lambda n,k=2:n and f(n-1,[k*a//b for a,b in zip(b"NM_M\r7",b"[U3&!\r")if k*a%b<1][0])or k

Попробуйте онлайн!

Кодирует список фракций zip две строки байтов, содержащие непечатаемые символы с низким ASCII.

Если nноль, мы возвращаем аргумент k; в противном случае мы рекурсируем с новыми параметрами. Наше новое kэто первое значение , k*a//bсоответствующее некоторой доле (a, b)в списке такого , что k*a//bявляется целым числом, то есть k*a%b<1.

MATL , 50 байтов

Hi:"'0m26<l~l *,..V'31-*'{uSFA=731-+."!'32-&\w~)1)

Попробуйте онлайн!

J , 116 110 байт

g=.3 :0
((1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x)([:({.@I.@(=<.){[)*)])^:y 2
)

Попробуйте онлайн!

0 индексированные; возвращает n-ное число

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

Объяснение:

J описывает рациональные числа в форме NrD, где N - числитель, а D - знаменатель, например, 17r91 78r85 19r51 23r38...я создал 2 отдельных списка для числителей и знаменателей и сделал из них 2 числа из 96 базисов.

1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x преобразует числа base-96 в списки и создает список дробей, разделяя два списка.

   1047856500267924709512946135x%&(96#.inv])5405040820893044303890643137x
17r91 78r85 19r51 23r38 29r33 77r29 95r23 77r19 1r17 11r13 13r11 15r14 15r2 55

2 начать с 2

^:y повторите глагол слева n (у - аргумент функции)

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

* умножить список дробей на правильный аргумент

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

{.@I.@находит индекс I.первого{. из целых чисел

{[ использует индекс для получения номера

05AB1E ,  44  43 байта

0 индексированные

2sF•Ë₁ǝßÌ?ƒ¥"h2ÔδD‡béαA5À>,•тв2ä`Š*s‰ʒθ_}нн

Попробуйте онлайн!

объяснение

2                                             # initialize stack with 2
 sF                                           # input times do:
   •Ë₁ǝßÌ?ƒ¥"h2ÔδD‡béαA5À>,•                  # push a base-255 compressed large number
                            тв                # convert to a list of base-100 digits
                              2ä`             # split in 2 parts to stack
                                 Š            # move denominators to bottom of stack
                                  *           # multiply the last result by the numerators
                                   s‰         # divmod with denominators
                                     ʒθ_}     # filter, keep only those with mod result 0
                                         нн   # get the div result

Большое количество нажатых является 17781923297795770111131515559185513833292319171311140201

Пари / ГП , 121 байт

n->a=2;for(i=1,n,a=[x|x<-a*[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],x\1==x][1]);a

Попробуйте онлайн!

JavaScript (Node.js) , 106 95 байтов

• спасибо @Arnauld и @Neil за сокращение на 11 байт

(n,N=2,I=13,B=Buffer(`[U3&!\rNM_M\r7`))=>n--?f(n,N/B.find(x=>N%x<!!++I)*B[I]):N

Попробуйте онлайн!

Сетчатка , 213 байт

K`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¶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¶2
\d+
*
"$+"+`((_+)/(_+)¶(.+¶)*)(\3)+$
$1$#5*$2
r`_\G

Попробуйте онлайн! Объяснение:

K`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¶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¶2

Замените входные данные списком всех дробей плюс начальное целое число.

\d+
*

Перевести все в одинарные.

"$+"+`

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

((_+)/(_+)¶(.+¶)*)(\3)+$

Найдите знаменатель, который равномерно делит целое число.

$1$#5*$2

Замените целое число на результат деления, умноженный на числитель.

r`_\G

Преобразуйте целое число в десятичное и выведите результат.

Атташе , 81 байт

Nest<~{Find[Integral,_*&`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]},2~>

Попробуйте онлайн! Выводит дробь больше 1. Например, ввод 5возвращает 2275/1. Это можно исправить с помощью плюс 2 байта, добавивN@ в программу.

объяснение

Это карри функция, которая карри Nest с двумя предопределенными аргументами:

{Find[Integral,_*&`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]}

и 2 . Этот последний аргумент является просто начальным семенем, а аргумент, который передается этой функции, является количеством итераций для вложения данной функции.

Для кодирования PRIMEGAME используется следующее:

&`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]]

Это оценивается как таковое:

A> "0zmt2R6E<@l<~6l2 0*,,*.-.!V "
"0zmt2R6E<@l<~6l2 0*,,*.-.!V "
A> Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "
[48, 122, 109, 116, 50, 82, 54, 69, 60, 64, 108, 60, 126, 54, 108, 50, 32, 48, 42, 44, 44, 42, 46, 45, 46, 33, 86, 32]
A> Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31
[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, 1]
A> Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]
 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  1
A> &`//=>Chop[Ords!"0zmt2R6E<@l<~6l2 0*,,*.-.!V "-31,2]
[(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/1)]

Давайте заменим это выражение Gв объяснении. Наша первая функция становится:

{Find[Integral,_*G]}

Это выполняет одну итерацию кода FRACTRAN _, вход в функцию. Это Findев в Integralэлемент (один , который представляет собой целое число) массив _*G, который является входным _умножается с каждым членом G. Nestпросто применяет это преобразование заданное количество раз.

Атташе, 42 байта

Я реализовал части $langsбиблиотеки, вдохновленный этим вызовом, поэтому я отмечаю этот раздел как неконкурентный.

Needs[$langs]2&FRACTRAN_EXAMPLES.prime.run

Это просто запрашивает список у FRACTRAN_EXAMPLESменя есть. Каждый пример является FractranExampleэкземпляром, который вызывает встроенную FRACTRANфункцию. primeПример PRIMEGAME Конвея.

F # (моно) , 215 байтов

let q m=
 let rec i x y=
  if y=m then x 
  else[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;1]|>List.chunkBySize 2|>List.find(fun[n;d]->x*n%d=0)|>fun[n;d]->i(x*n/d)(y+1)   
 i 2 0

Попробуйте онлайн!

PHP, 183 байта (189 с тегом "php")

Гольф:

$t=2;for(;@$i++<$argv[1];){foreach([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/1]as$n){$a=$t*$n;if(preg_match('/^\d+$/',$a)){$t=$a;break;}}}echo$t;

Ungolfed:

<?php 
$t=2;
for(;@$i++<$argv[1];){
    foreach([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/1] as $n){
        $a=$t*$n;
        if(preg_match('/^\d+$/',$a)){
            $t=$a;break;
        }
    }
}
echo $t;

Попробуйте онлайн!