Bertrand's Primes

Question

Bertrand's Postulate states that for every integer n ≥ 1 there is at least one prime p such that n < p ≤ 2n. In order to verify this theorem for n < 4000 we do not have to check 4000 cases: The Landau trick says it is sufficient to check that

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

are all prime. Because each of these numbers is less than twice its predecessor each interval {y : n < y ≤ 2n} contains at least one of those prime numbers.

This sequence of numbers are the Bertrand Primes (OEIS A006992) and they are defined as follows:

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

Challenge

Implement this sequence. You may write

• a function or program that given some n returns a(n) (0 or 1 indexed),
• a function or program that given some n returns the first n (or n-1 or n+1) entries of this sequence,
• an infinite list or stream or generator or similar equivalent in your langauge.

Answer 1

Octave, 32 bytes

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

Keeps printing the values indefinitely (each value is preceded by k =).

Try it online!

---

Octave, 42 bytes

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

Takes n as input and outputs the n first values (each value is preceded by k =).

Try it online!

---

Octave, 51 bytes

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

Similar to Luis Mendo's MATL answer. Takes n as input and outputs a(n) (1-indexed).

Try it online!

---

Octave, 60 bytes

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

Takes n as input and outputs a(n) (1-indexed).

Try it online!

Answer 2

J, 11 bytes

_4&(p:+:)2:

Try it online!

0-indexed.

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

Answer 3

Wolfram Language (Mathematica), 27 bytes

Saved one byte thanks to Martin Ender.

0-indexed.

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

Try it online!

Answer 4

05AB1E, 14 7 6 bytes

$F·.ØØ

Try it online!

---

1-indexed answer (unless 0 is supposed to output 1), explanation:

$       # 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.

---

It's 1-indexed because all iterations have a 'dummy' iteration with n=1.

Answer 5

Haskell, 50 bytes

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

Try it online!

Outputs an infinite list.

---

Haskell, 40 bytes?

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

Try it online!

This works if Bertrand's primes don't contain any Fermat pseudoprimes for 2.

Answer 6

MATL, 9 bytes

1i:"EZq0)

Inputs n, outputs a(n), 1-indexed.

Try it online!

Explanation

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)

Answer 7

Jelly, 6 bytes

2ḤÆp$¡

Try it online!

0-indexed.

Explanation

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

Answer 8

Stax, 10 bytes

ü☼┌τ,æ▒ìn(

Run test cases

This problem has exposed a bug in stax's implementation of :p, which is an instruction that gets the greatest prime less than its input. If it worked correctly, there would be a 5 6 byte solution. But alas, it does not, and there is not. As the language's creator, I will fix it, but it seems kind of cheap to fix and use it after the problem was posted.

Anyway, here is the corresponding ascii representation of the program above.

ODH{|p}{vgs

It's a relatively straight-forward implementation of the problem statement. The only thing possibly interesting about it is the use of the gs generator form. Generators are a family of constructions that combine an initial condition, a transform, and a filter, to produce one or more satisfying values. In this case, it's used in place of the broken :p instruction.

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.

Edit: here's the 6 byte solution, but it requires a bug-fix that was only applied after this challenge was posted.

Answer 9

Python 2, 63 bytes

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

Try it online!

Prints forever.

Uses the Wilson's Theorem prime generator even though generating primes forward is clunky for this problem. Tracks the current largest prime seen r and the doubling boundary m.

Two bytes are saved doing P*=k rather than P*=k*k as usual, as the only effect is to claim that 4 is prime, and the sequence of doubling misses it.

Answer 10

Japt, 16 14 13 12 bytes

Two solutions for the price of one, both 1-indexed.

---

Nth Term

Finally, a challenge I can write a working solution for using F.g().

_ôZ fj Ì}g°U

Try it

                 :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

---

First N Terms

ÆV=ôV fj ̪2

Try it

                 :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

Answer 11

CJam (15 bytes)

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

Online demo. Note that this is 0-indexed.

---

A more efficient approach would be to search backwards, but this requires one character more because it can't use implicit , (range):

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

Answer 12

Python 2, 64 bytes

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

Try it online! Prints the sequence indefinitely

Answer 13

Pari/GP, 34 bytes

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

Try it online!

Answer 14

Haskell, 58 bytes

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

Try it online!

Answer 15

Python 2, 68 bytes

Prints the sequence indefinitely (you have to click "Run" the second time to stop the execution).

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

Try it online!

Python 3, 90 bytes

Returns the n^th term.

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

Try it online!

Answer 16

C (gcc), 97 87 86 80 79 bytes

• Saved ten bytes by inlining a non-primality checking function P into the main loop.
• Saved a byte by moving the printf call.
• Saved six bytes by returning the i-th sequence entry (0-indexed) instead of outputting a never-ending stream.
• Saved a byte thanks to ceilingcat.

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;}

Try it online!

Answer 17

Attache, 38 bytes

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

Try it online!

0-based; returns the nth Bertrand prime.

There is currently no builtin to find the previous/next primes, so I use the Series builtin to calculate all primes up to 2*$[_-1]. This last expression uses implicit recursion (bound to $) to easily define the recurrence relation. The if condition is used to determine a base condition.

Answer 18

Perl 6, 35 bytes

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

Try it online!

This expression is an infinite list of Bertrand primes.

Answer 19

Retina, 39 bytes

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

*\`_

Try it online! Explanation:

.K`_

Start with 1.

"$+"{`

Repeat the loop using the input as the loop count.

_
__

Double the value.

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

Find the highest prime less than the value.

*\`_

Print it out.

Answer 20

Ruby, 51 + 7 (-rprime) = 58 bytes

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

Try it online!

A lamba accepting n and returning the nth Bertrand prime, 0-indexed. There's not much here, but let me ungolf it anyway:

->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
}

Ruby, 48 + 7 = 55 bytes

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

Try it online!

For fun, here's an infinite-loop solution. It prints as it goes, and requires an interrupt. Depending on exactly when you interrupt, you may or may not see the output. Ungolfed:

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

Answer 21

APL (Dyalog Extended), 12 bytes

Takes input from user as N, returns Nth element of the sequence (0-indexed).

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

Try it online!

Explanation:

{¯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

Answer 22

R, 87 bytes

Given n outputs 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

Try it online!

I'm still working on "Given n output a(1), a(2)... a(n)". I thought I could just modify this code slightly, but it seems more difficult than that.