# Bertrand's Primes

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.

# 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!

# 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


# Wolfram Language (Mathematica), 27 bytes

Saved one byte thanks to Martin Ender.

0-indexed.

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


Try it online!

# 05AB1E, 147 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.

• Fx.ØØ is so close... Works for anything above n > 2. – Magic Octopus Urn Feb 13 '18 at 16:09
• I had $F·ÅPθ for the same byte count. – Emigna Feb 13 '18 at 17:27 • @Emigna had? That's like 0% the same haha. I mean, technically the same, but not. Could still post it ;P. – Magic Octopus Urn Feb 13 '18 at 17:35 # 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.

# Jelly, 6 bytes

2ḤÆp$¡  Try it online! 0-indexed. ## Explanation 2ḤÆp$¡  Main link. Input: n
2       Constant 2

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

## 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*


# Japt, 161413 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


# Pari/GP, 34 bytes

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


Try it online!

# 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

# 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!

# 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 nth 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!

# C (gcc), 97878680 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!

• @ceilingcat Thank you. – Jonathan Frech Sep 18 '19 at 9:51

{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. # Perl 6, 35 bytes 2,{(2*$_,*-1...&is-prime).tail}...*


Try it online!

This expression is an infinite list of Bertrand primes.

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

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


# 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


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