Постулат Бертрана утверждает, что для каждого целого числа n ≥ 1 существует хотя бы одно простое число p такое, что n <p ≤ 2n . Чтобы проверить эту теорему для n <4000, нам не нужно проверять 4000 случаев: трюк Ландау говорит, что достаточно проверить, что

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 5003

все простые. Поскольку каждое из этих чисел менее чем в два раза превосходит своего предшественника, каждый интервал {y: n <y ≤ 2n} содержит хотя бы одно из этих простых чисел.

Эта последовательность чисел - простые числа Бертрана (OEIS A006992), и они определены следующим образом:

a(1) = 2
a(n) = largest prime below 2a(n-1)

Вызов

Реализуйте эту последовательность. Вы можете написать

• функция или программа, для которых задано некоторое n, возвращает a (n) (0 или 1 проиндексировано),
• функция или программа, для которых задано некоторое n, возвращает первые n (или n-1 или n + 1 ) записей этой последовательности,
• бесконечный список или поток или генератор или аналогичный эквивалент в вашем языке.

Октава , 32 байта

k=2
do k=primes(k+k)(end)until 0

Сохраняет значения на неопределенный срок (каждому значению предшествует k =).

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

Октава , 42 байта

k=2
for i=2:input('')k=primes(k+k)(end)end

Принимает n в качестве входных данных и выводит n первых значений (каждому значению предшествует k =).

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

Октава , 51 байт

k=2;for i=2:input('')k=primes(k+k)(end);end
disp(k)

Аналогично ответу Луиса Мендо на MATL . Принимает n в качестве входных данных и выводит a (n) (1-индексированный).

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

Октава , 60 байт

k=2;for i=2:input('')k*=2;while~isprime(--k)
end
end
disp(k)

Принимает n в качестве входных данных и выводит a (n) (1-индексированный).

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

J 11 байт

_4&(p:+:)2:

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

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

_4&(p:+:)2:  Input: integer n
         2:  Constant 2
_4&(    )    Repeat n times
      +:       Double
_4  p:         Find the largest prime less than the double

Wolfram Language (Mathematica) , 27 байтов

Сохранено один байт благодаря Мартину Эндеру.

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

Nest[-NextPrime[-2#]&,2,#]&

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

05AB1E , 14 7 6 байтов

$F·.ØØ

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

1-индексированный ответ (если 0 не должен выводить 1), объяснение:

$       # Push 1 and input (n)...
 F      # n-times do... 
  ·     # Double the current prime (first iteration is 1*2=2).
   .ØØ  # Find prime slightly less than double the current prime.

Он индексируется 1, потому что все итерации имеют «фиктивную» итерацию с n=1.

Haskell , 50 байтов

f p|sum(gcd p<$>[1..p-1])<p=p:f(2*p)|1>0=f$p-1
f 2

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

Выводит бесконечный список.

Haskell , 40 байт?

f p|mod(2^p-2)p<1=p:f(2*p)|1>0=f$p-1
f 2

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

Это работает, если простые числа Бертрана не содержат псевдослучайных чисел Ферма для 2 .

Желе , 6 байт

2ḤÆp$¡

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

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

объяснение

2ḤÆp$¡  Main link. Input: n
2       Constant 2
    $¡  Repeat n times
 Ḥ        Double
  Æp      Find the largest prime less than the double

MATL , 9 байт

1i:"EZq0)

Входы n , выходы a ( n ), 1-индексированные.

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

объяснение

1       % Push 1
i       % Push input n
:"      % Do the following that many times
  E     %   Multiply by 2
  Zq    %   Primes up to that
  0)    %   Get last entry
        % End (implicit). Display (implicit)

Stax , 10 байт

ü☼┌τ,æ▒ìn(

Выполнить тестовые случаи

Эта проблема выявила ошибку в реализации stax :p, которая представляет собой инструкцию, которая получает наибольшее простое число меньше, чем ее ввод. Если бы это работало правильно, было бы 5 6-байтовое решение. Но, увы, этого нет и нет. Как создатель языка, я исправлю это, но после того, как проблема была опубликована, кажется, что исправить и использовать ее довольно дешево.

В любом случае, вот соответствующее представление программы в формате ascii выше.

ODH{|p}{vgs

Это относительно простая реализация постановки задачи. Единственное, что может быть интересным, это использованиеgs формы генератора. Генераторы - это семейство конструкций, которые объединяют начальное условие, преобразование и фильтр для получения одного или нескольких удовлетворяющих значений. В этом случае он используется вместо сломанной :pинструкции.

O               Push integer 1 underneath the input number.
 D              Pop the input and repeat the rest of the program that many times.
  H             Double number.
   {|p}         Predicate block: is prime?
       {vgs     Decrement until the predicate is satisfied.
                Output is implicitly printed.

Изменить: вот 6-байтовое решение, но оно требует исправления ошибки, которое было применено только после публикации этого запроса.

Python 2 , 63 байта

r=m=k=P=2
while k:
 P*=k;k+=1
 if k>m:print r;m=r*2
 if P%k:r=k

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

Отпечатки навсегда.

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

Два байта сохраняются, выполняя, P*=kа не P*=k*kкак обычно, поскольку единственный эффект состоит в том, чтобы утверждать, что 4 является простым, и последовательность удвоения пропускает его.

CJam (15 байт)

2{2*{mp},W=}qi*

Демо онлайн . Обратите внимание, что это 0-индексированный.

Более эффективный подход - поиск в обратном направлении, но для этого требуется еще один символ, поскольку он не может использовать неявный ,(диапазон):

2{2*,W%{mp}=}qi*

Japt , 16 14 13 12 байт

Два решения по цене одного, оба с 1 индексированием.

N-й срок

Наконец, задача, которую я могу написать рабочее решение для использования F.g().

_ôZ fj Ì}g°U

Попытайся

                 :Implicit input of integer U
_       }g       :Starting with the array [0,1] take the last element (Z),
                 :pass it through the following function
                 :and push the returned value to the array
 ôZ              :  Range [Z,Z+Z]
    fj           :  Filter primes
       Ì         :  Get the last item
          °U     :Repeat that process U+1 times and return the last element in the array

Первые N Условия

ÆV=ôV fj ̪2

Попытайся

                 :Implicit input of integer U
                 :Also makes use of variable V, which defaults to 0
Æ                :Create range [0,U) and pass each through a function
  ôV             :  Range [V,V+V]
     fj          :  Filter primes
        Ì        :  Get the last item
         ª2      :  Logical OR with 2, because the above will return undefined on the first iteration
 V=              :  Assign the result of the above to V

Par / GP , 34 байта

a(n)=if(n<2,2,precprime(2*a(n-1)))

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

Python 2 , 64 байта

n=2
while 1:
 if all(n%i for i in range(2,n)):print n;n*=2
 n-=1

Попробуйте онлайн! Печатает последовательность бесконечно

Haskell , 58 байт

a 1=2
a n=last[p|p<-[2..2*a(n-1)],all((>0).mod p)[2..p-1]]

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

Python 2 , 68 байт

Печатает последовательность бесконечно (вам нужно нажать «Выполнить» во второй раз, чтобы остановить выполнение).

k=2
while 1:
 print k;k+=k
 while any(k%u<1for u in range(2,k)):k-=1

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

Python 3 , 90 байт

Возвращает n- ^й член.

f=lambda n,i=1,p=1:n*[0]and p%i*[i]+f(n-1,i+1,p*i*i) 
a=lambda n:n and f(2*a(n-1))[-1]or 1

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

C (gcc) , 97 87 86 80 79 байт

• Сохранение десяти байтов путем включения функции проверки неосновности Pв основной цикл.
• Сохранил байт, переместив printfвызов.
• Сохранено шесть байтов, возвращая i -ой записи последовательности (с 0 индексами) вместо вывода бесконечного потока.
• Сохраненный байт благодаря потолку .

f(p,r,i,m,e){for(r=2;p--;)for(e=0,i=r+r;e=m=!e;r=i--)for(;i-++m;e=e&&i%m);p=r;}

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

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

{If[_,Last[Series[Prime,2*$[_-1]]],2]}

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

0 на основе; возвращаетn пятое число Бертрана.

В настоящее время нет встроенной функции для поиска предыдущих / следующих простых чисел, поэтому я использую Seriesвстроенную функцию для вычисления всех простых чисел до 2*$[_-1]. Это последнее выражение использует неявную рекурсию (привязанную к $), чтобы легко определить рекуррентное отношение. Условие if используется для определения базового условия.

Perl 6 , 35 байт

2,{(2*$_,*-1...&is-prime).tail}...*

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

Это выражение представляет собой бесконечный список простых чисел Бертрана.

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

.K`_
"$+"{`_
__
+`^(?=(..+)\1+$).

*\`_

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

.K`_

Начните с 1.

"$+"{`

Повторите цикл, используя вход в качестве счетчика цикла.

_
__

Удвойте значение.

+`^(?=(..+)\1+$).

Найти самое высокое простое число меньше значения.

*\`_

Распечатай.

Ruby , 51 + 7 (-rprime) = 58 байт

->n{x=2
n.times{x=(x..2*x).select(&:prime?)[-1]}
x}

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

Ламба, принимающая nи возвращающая nthпростое число Бертрана, 0-индексированная. Здесь не так много, но позвольте мне все же разжать это

->n{
  x=2                       # With a starting value of 2
  n.times{                  # Repeat n times:
    x=(x..2*x)              # Take the range from x to its double
      .select(&:prime?)[-1] # Filter to only primes, and take the last
  }
  x                         # Return
}

Рубин , 48 + 7 = 55 байт

x=2
loop{puts x
x*=2
loop{(x-=1).prime?&&break}}

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

Для развлечения вот решение с бесконечным циклом. Он печатает, как он идет, и требует прерывания. В зависимости от того, когда именно вы прерываете, вы можете видеть или не видеть результат. Ungolfed:

x=2
loop{
  puts x
  x*=2
  loop{
    (x-=1).prime? && break
  }
}

APL (Dyalog Extended) , 12 байт

Принимает ввод от пользователя как N, возвращает N-й элемент последовательности (0-индексированный).

{¯4⍭2×⍵}⍣⎕⊢2

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

Объяснение:

{¯4⍭2×⍵}⍣⎕⊢2 ⍝ Full program
          ⎕   ⍝ Get input from user - call it 'N'
         ⍣ ⊢2 ⍝ Repeat the left function N times, beginning with 2
    2×⍵       ⍝ Double the function input
 ¯4⍭          ⍝ Find the largest prime less than above

р , 87 байт

Данные nвыводыa(n)

j=scan();n=2;while(j-1){for(i in (n+1):(2*n)){n=ifelse(any(i%%2:(i-1)<1),n,i)};j=j-1};n

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

Я все еще работаю над "Учитывая n выходных данных (1), a (2) ... a (n)". Я думал, что смогу немного изменить этот код, но он кажется более сложным.