Подсчет цепей Каннингема

14

Простые числа всегда очаровывали людей. 2300 лет назад Евклид писал в своих «Элементах»

Простое число - это то, что измеряется одной единицей.

что означает, что простое число делится только на 1(или само по себе).

Люди всегда искали отношения между простыми числами и придумали довольно странные (как в «интересных») вещи.

Например, простое число Софи Жермен - простое число, pдля которого 2*p+1также простое число.

Безопасный премьер является главным , pдля которого (p-1)/2также простой, что именно условия назад штриха Софи Жермен.

Они связаны с тем, что мы ищем в этом вызове.

Cunningham цепь типа I представляет собой ряд простых чисел, где каждый элемент , за исключением последнего, представляет собой простое Sophie Germain , и каждый элемент , кроме первого является безопасным премьер . Количество элементов в этой цепочке называется его длиной .

Это означает, что мы начинаем с простого pи вычисляем q=2*p+1. Если qпервично тоже, у нас есть оттяжки Каннингхэма цепь типа I длины 2. Тогда мы тестируем 2*q+1и так далее, до следующего сгенерированного число не является составным.

Цепи Каннингема типа II построены по почти одинаковому принципу, единственное отличие состоит в том, что мы проверяем 2*p-1на каждом этапе.

Цепи Каннингема могут иметь длину 1 , что означает, что ни 2 * p + 1, ни 2 * p-1 не являются простыми. Мы не заинтересованы в этом .

Некоторые примеры цепей Каннингема

2начинается цепочка типа I длиной 5.

2, 5, 11, 23, 47

Следующее построенное число будет 95не простым.
Это также говорит нам, что 5, 11, 23и 47не начинать любую цепь типа I , так как он будет иметь предшествующие элементы.

2также начинается цепочка типа II длиной 3.

2, 3, 5

Следующим будет 9, который не прост.

Давайте попробуем 11для типа II (мы исключили его из типа I ранее).
Что ж, 21будет следующим, что не является простым, поэтому у нас будет длина 1 для этой «цепочки», которую мы не учитываем в этом вызове.

Вызов

Написать программу или функцию , что, учитывая число в nкачестве входных, записи / возвращает исходный номер п - й Cunningham цепи типа I или II , по меньшей мере , длины 2 , с последующим пробелом, а затем по типу цепи она начинается ( я или II ), за которым следует двоеточие, за которым следует длина цепи этого типа. В случае, если простое число запускает оба типа цепей (типа I и типа II), цепочка типа I учитывается первой.

Пример: 2 I:5

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

Давайте посмотрим, как это начинается

Начнем с 2. Так как это вообще первое простое число, мы можем быть уверены, что нет цепочки, начинающейся с нижнего простого числа, которое содержит 2.
Следующее число в цепочке типа я был бы 2*2+1 == 5. 5является простым, поэтому у нас уже есть цепочка, по крайней мере, длиной 2.
Мы считаем это первой цепочкой. А как насчет типа II? Следующий номер будет 2*2-1 == 3. 3простое число, поэтому цепочка как минимум длиной 2 для типа II тоже.
Мы считаем это второй цепочкой. И мы сделали для 2.

Следующий штрих есть 3. Здесь мы должны проверить, находится ли цепочка, в которой началось нижнее простое число.
Проверьте тип I: (3-1)/2 == 1. 1не является простым, поэтому 3 может быть отправной точкой для цепочки типа I.
Давайте проверим это. Дальше будет 3*2+1 == 7. 7является простым, поэтому мы имеем цепочку типа I, по крайней мере, длины 2. Мы считаем это как третью цепочку.
Теперь мы проверяем, 3появляется ли в цепочке типа II, что началось нижнее простое число. (3+1)/2 == 2, 2является простым, поэтому 3 не может рассматриваться как начальное число для цепочки типа II. Так что это не считается, даже если следующий 3в этой цепочке номер, который будет5простое. (Конечно, мы уже знали это, и вы, конечно, можете подумать о своем собственном методе выполнения этих проверок.)

И поэтому мы проверяем на для 5, 7, 11и так далее, подсчета голосов , пока мы не найдем п - й Cunningham цепи , по меньшей мере , длиной 2.

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

Между прочим: в моих тестах я не нашел никакого простого числа, кроме того, 2что запускались оба типа цепочек с длиной больше чем 1.

Примеры ввода / вывода

вход

1

Выход

2 I:5


вход

10

Выход

79 II:3


вход

99

Выход

2129 I:2


Выходы на входы 1..20

2 я: 5
2 II: 3
3 я: 2
7 II: 2
19 II: 3
29 я: 2
31 II: 2
41 я: 3
53 я: 2
79 II: 3
89 я: 6
97 II: 2
113 я: 2
131 я: 2
139 II: 2
173 я: 2
191 я: 2
199 II: 2
211 II: 2
229 II: 2

Список первых 5000 выходов можно найти здесь .

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

Удачи :)

Cabbie407
источник
3
Забыл упомянуть в песочнице: легко доказать, что 2и 3это единственные простые числа, pдля которых 2p-1и 2p+1простые, 2и единственное простые числа, которые запускают нетривиальные цепочки Каннингема обоих типов.
Питер Тейлор,
Ладно. Спасибо за вашу помощь:)
Cabbie407
3
(Преобразованный комментарий от ответа.) Там нет каких - либо другие , чем простые чисел 2с двойной длиной цепи больше 1. Вот доказательство по ликвидации.
pbeentje
Что ж, спасибо, что снова указали на это так подробно. Вы просто хотели это отметить, или вы думаете, что я должен как-то изменить вызов из-за этого?
Cabbie407 25.09.15
Только замечание. Я не думаю, что это меняет задачу в любом случае, только потенциально полезно для игры в гольф: когда одна цепь найдена, другую не нужно проверять.
pbeentje

Ответы:

2

Javascript, 236 208 байт

Сохранено 28 байт:

p=(n,i=n)=>n%--i?p(n,i):i==1;f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:`+eval(`for(j=1;p(k=2*k+l);j++);j`))}

Сохраненные 9 байт на pфункцию с: p=(n,i=n)=>n%--i?p(n,i):i==1
The tфункцией были заменены eval(...)заявлением непосредственно в fфункции.


Предыдущее решение:

p=n=>{for(i=n;n%--i&&i;);return 1==i};t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j};f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

Пример: f(6)

Выход: 29 I:2

Пояснение
я использую 3 функции

1 p : узнать , простое ли n : p=n=>{for(i=n;n%--i&&i;);return 1==i}

2 t : узнать длину цепи Каннингема, начиная с n типа I или II, в зависимости от параметра m, который будет 1 или -1: t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}

3 f : считает цепочки ( для цикла ) и отображает результат

f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

для цикла : для каждого числа действительна цепочка Каннингема (I затем II, если необходимо), если

  • число простое
  • предшественник не прост
  • преемник главный
Хеди
источник