22
\$\begingroup\$

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.
\$\endgroup\$

21 Answers 21

8
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

Wolfram Language (Mathematica), 27 bytes

Saved one byte thanks to Martin Ender.

0-indexed.

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

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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.

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

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ poke you need another byte now ;)... \$\endgroup\$ – Magic Octopus Urn Feb 13 '18 at 17:01
  • \$\begingroup\$ @MagicOctopusUrn An input of 0 returns 2, 1 returns 3, and so on. I don't see any issue. \$\endgroup\$ – miles Feb 13 '18 at 18:22
  • \$\begingroup\$ I meant you need to save a byte on this answer to win because I tied you at 6-bytes, your answer itself is fine. \$\endgroup\$ – Magic Octopus Urn Feb 13 '18 at 18:25
5
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice language! I've added it to my list of golfing langs. Let me know if you see anything wrong, or if there's anything else you'd like to add. \$\endgroup\$ – ETHproductions Feb 14 '18 at 0:22
  • \$\begingroup\$ @ETHproductions: Nice, thanks! If you don't mind, could you change the interpreter url to staxlang.xyz I decided to get a domain for it. \$\endgroup\$ – recursive Feb 14 '18 at 6:41
  • 1
    \$\begingroup\$ Wow, a whole domain just for a golfing language? Lucky esolang ;) Updated! \$\endgroup\$ – ETHproductions Feb 14 '18 at 12:19
  • \$\begingroup\$ @recursive WOW, $1.99 for each xyz domain? I'm in. \$\endgroup\$ – Magic Octopus Urn Feb 14 '18 at 19:11
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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*
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 34 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 97 87 86 80 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 an never-ending stream.
f(p,r,i,m,e){for(r=2;p--;)for(e=0,i=r+r;!e;r=i--)for(e=m=1;i-++m;e=e&&i%m);p=r;}

Try it online!


If only correctly calculating the first eight sequence elements due to integer inaccuracies is acceptable, 78 bytes are possible.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 35 bytes

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

Try it online!

This expression is an infinite list of Bertrand primes.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
  }
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.