Find prime gaps

Question

A prime gap is the difference between two consecutive primes. More specifically, if p and q are primes with p <q and p+1, p+2, ..., _q_−1 are not primes, the primes p and q define a gap of n = q_−_p. The gap is said to be started by p, and to have length n.

It is known that arbitrarily large prime gaps exist. That is, given n there exists a prime gap of length n or larger. However, a prime gap of length exactly n may not exist (but a larger one will).

The challenge

Given a positive integer n, output the first prime that starts a gap of length n or larger.

As an example, for input 4 the output should be 7, because 7 and 11 are the first consecutive primes that differ by at least 4 (the previous gaps are 1, from 2 to 3; 2, from 3 to 5; and 2, from 5 to 7). For input 3 the answer should also be 7 (there are no gaps of length 3).

Additional rules

• The algorithm should theoretically work for arbitrarily high n. In practice, it is acceptable if the program is limited by time, memory or data-type size.

• Input and output can be taken by any reasonable means.

• Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

• Shortest code in bytes wins.

Test cases

Input -> Output

1        2
2        3
3        7
4        7
6        23
10       113
16       523
17       523
18       523
30       1327
50       19609
100      370261
200      20831323

Answer 1

Jelly, 10, 9, 8 10 bytes

Æn_$:ð1#»2

Try it online!

Two bytes saved thanks to @Dennis! (and then added back again due to edge-cases)

Explanation:

Æn          #   The next prime after 'P'
  _$        #   Minus 'P'
    :       #   Divided by 'N'
            #
            # This will give a falsy value unless the distance to the next prime is >= N
            #
     ð      # Treat all of that as a single dyad (fucntion with two arguments). 
            # We'll call it D(P, N)
            #
      1#    # Find the first 'P' where D(P, input()) is truthy
        »2  # Return the maximum of that result and 2

Answer 2

Mathematica, 30 bytes

2//.x_ /;NextPrime@x-x<#:>x+1&

Try it online!

Mathematica, 35 bytes

(t=2;While[NextPrime@t-t<#,t++];t)&

Try it online!

Mathematica, 77 bytes

Prime@Min@Position[s=Differences@Prime@Range[(r=#)^3+1],#&@@Select[s,#>=r&]]&

Answer 3

Haskell, 106 102 93 77 73 72 bytes

This generates an infinite list of primes first, then looks for the prime gaps. The prime list was taken from here. It can probably be shortened, but I haven't figured out how yet:)

Thanks to @BruceForte for -4 bytes and @Zgrab for -1 byte!

f n=[x|(y,x)<-zip=<<tail$[n|n<-[2..],all((>0).rem n)[2..n-1]],y-x>=n]!!0

Try it online!

Answer 4

Gaia, 6 bytes

zṅọ⊃∆ṇ

This is extremely inefficient (the 16 test case took over an hour to compute on my machine).

Try it online!

Explanation

The sequence seems to have the property that a(n) <= 2^n.

z       Push 2^input.
 ṅ      Get the first 2^input prime numbers.
  ọ     Get the deltas of the list.
   ⊃∆   Find the index of the first that is greater than or equal to the input.
     ṇ  Push the index-th prime number.

Answer 5

Pyth - 14 bytes

It filters from [1, inf), filtering by primality(P_) and that the next prime filtered from (n, inf), has a different >= to the input.

f&P_T<tQ-fP_Yh

Test Suite.

Answer 6

PowerShell, 97 96 91 bytes

param($n)for($a=$b=2){for(;'1'*++$b-match'^(?!(..+)\1+$)..'){if($b-$a-ge$n){$a;exit}$a=$b}}

Try it online!

Takes input $n, sets $a and $b equal to 2, then enters an infinite for loop. Inside, we loop up on $b until we get to the next prime. Then we check if $b-$a (i.e., the gap) is -greaterthanorequal to $n. If it is, we output $a and exit. Otherwise we set $a to be $b and increment $b and start our next search.

Warning: This is slow for large input. In fact, it can't complete the 50 or higher tests within the 60s timeout on TIO. Oh well.

Answer 7

Husk, 13 11 10 bytes

´ȯ!V≥⁰Ẋ-İp

Try it online!

´       İp  -- with the primes
 ȯ!         -- get the value at position
      Ẋ-    -- where the difference of the current and next prime
   V≥⁰      -- is greater or equal than the input N

Answer 8

Mathematica, 39 bytes

(For[i=2;p=NextPrime,i+#>p@i,i=p@i];i)&
(* or *)
(For[i=1;p=Prime,p@i+++#>p@i,];p[i-1])&

33 byte version (not valid because it only goes up to the 65535th prime)

p=NextPrime;2//.i_/;p@i-i<#:>p@i&

Answer 9

Python 2, 96 88 bytes

- 8 bytes Thanks to @Maltysen

n,p,r=input(),3,[2]
while p-r[-1]<n:r+=[p]*all(p%i for i in range(2,p));p+=1
print r[-1]

Try it online!

Answer 10

Perl 6, 63 bytes

->\d{(grep &is-prime,^∞).rotor(2=>-1).first({-d>=[-] $_})[0]}

Try it online!

Answer 11

Mathematica, 37 bytes

gNestWhile[p=NextPrime,2,p@#-#<g&]

Function with first argument g. Starting with 2, applies the function p=NextPrime repeatedly as long as p@#-#<g& gives True (the gap between the current prime and the next prime is less than g).

Answer 12

R + gmp, 55 bytes

Makes use of the nextprime function from the gmp library

s=2;n=scan();while((x=gmp::nextprime(s))-s<n)s=x;cat(s)

Answer 13

Ruby, 61 bytes

->g{*r,f=2,3;f+=1while r.find{|n|f%n<1}||r<<f&&g>f-z=r[-2];z}

Try it online!

Answer 14

C = 141 109 bytes ; C++, D = 141 bytes ; C#, Java = 143 bytes

WARNING : LOW PERFORMANCE ALGORITHM

This code was not able to calculate the prime gap for g(200) within 10 minutes. For g(100), it needed 10 seconds ( C++ version )

C++ and D version :

int p(int d){for(int i=2;i<=d/2;++i){if(!(d%i))return 0;}return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do{++n;}while(!p(n));}return f;}

C# and Java version :

int p(int d){for(int i=2;i<=d/2;++i){if(d%i==0)return 0;}return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do{++n;}while(p(n)==0);}return f;}

C version, -32 bytes thanks to ceilingcat :

i;p(d){for(i=2;d/2/i;)if(!(d%i++))return 0;return 1;}f;n;g(d){for(f=2,n=3;n-f<d;)for(f=n;!p(++n););return f;}

Differences between the C#/Java and C/C++/D version : !p(n) <==> p(n)==0

Answer 15

D, 127 125 122 bytes

WARNING: LOW PERFORMANCE ALGORITHM!!

T p(T)(T d){T r;for(T i=2;i<=d/2;)r=d%i++<1||r;return r;}T g(T)(T d){T f=2,n=3;while(n-f<d){f=n;while(p(++n)){}}return f;}

Try it online!

How?

HatsuPointerKun again, but I'll do the D specific sorcery.

• Template system can infer types T p(T)(T d), and is shorter than C++
• r=d%i++<1||r, D specific shenanigans, might work in C/C++, but I don't know.
• p(++n), same as above, not sure if it works in C/C++
• while(p(++n)){}, here one sees why D is bad at golfing, one can't use ; as an empty statement.

Answer 16

Perl 6, 41 37 bytes

{+(1...(^$_+*)>>.is-prime eqv!<<^$_)}

Try it online!

Explanation

{                                   }  # Block taking n as $_
   1...   # Sequence 1,2,... until
       (^$_+*)  # Range [i,i+n)
              >>.is-prime  # is-prime for each
                          eqv!<<^$_  # Equals (True,False,False,False,...)?
 +(                                )  # Length of sequence

Answer 17

Haskell, 64 bytes

f n=until(\p->and[any((<1).mod k)[2..k-1]|k<-[p+1..p+n-1]])(+1)2

Try it online!

Count up from 2 looking for a p such that [p+1..p+n-1] are all composite.

p itself will always be prime: otherwise [p..p+n-1] is a larger prime gap and we'd have returned p-1.

Answer 18

QBIC, 28 bytes

{~µs||~s-r>=:|_Xr\r=s]]s=s+1

Explanation

{         DO
~µs||     IF s is prime THEN (note, s starts as 3)
~s-r>=:   IF the gap between s (current prime) and r (prev prime) is big enough
|_Xr      THEN QUIT, printing prev prime r
\r=s      ELSE (gap too small, but s is prime), set r to prime s
]]        END IF x2, leaving us in the WHILE
s=s+1     increment s, retest for primality ...

Answer 19

05AB1E, 9 bytes

∞<ØD¥I@Ïн

Try it online or verify all test cases. (Test Suite doesn't contain the last two test cases, because TIO times out for those.)

Since the other question is closed as a dupe of this one, I'm posting my answer here as well.

Explanation:

∞           # Get an infinite list in the range [1, ...]
 <          # Decrease it by one to make it in the range [0, ...]
  Ø         # Get for each the (0-indexed) n'th prime: [2,3,5,7,11,...]
   D        # Duplicate this list of primes
    ¥       # Get all deltas (difference between each pair): [1,2,2,4,2,...]
     I@     # Check for each if they are larger than or equal to the input
            #  i.e. 4 → [0,0,0,1,0,1,0,1,1,0,...]
       Ï    # Only keep the truthy values of the prime-list
            #  → [23,31,47,53,61,...]
        н   # And keep only the first item (which is output implicitly)
            #  → 23

Answer 20

Java 8, 99 92 bytes

n->{int a=2,b=3,f,k;for(;b-a<n;)for(f=0,a=b;f<2;)for(f=++b,k=2;k<f;)f=f%k++<1?0:f;return a;}

Try it online. (Largest test case is excluded, because it times out in TIO.)

Explanation:

n->{               // Method with integer as both parameter and return-type
  int a=2,b=3,     //  Prime-pair `a,b`, starting at 2,3
      f,           //  Prime-checker flag `f`, starting uninitialized
      k;           //  Temp integer, starting uninitialized
  for(;b-a         //  Loop as long as the difference between the current pair of primes
          <n;)     //  is smaller than the input
    for(f=0,       //   (Re)set the prime-checker flag to 0
        a=b;       //   Replace `a` with `b`, since we're about to search for the next prime-pair
        f<2;)      //   Inner loop as long as the prime-checker flag is still 0 (or 1)
                   //   (which means the new `b` is not a prime)
      for(f=++b,   //    Increase `b` by 1 first, and set this value to the prime-checker flag
          k=2;     //    Set `k` to 2
          k<f;)    //    Inner loop as long as `k` is still smaller than the prime-checker flag
        f=         //     Change the prime-checker flag to:
          f%k++<1? //      If the prime-checker flag is divisible by `k`
           0       //       Set the prime-checker flag to 0
          :        //      Else:
           f;      //       Leave it unchanged
                   //    (If any integer `k` in the range [2, `b`) can evenly divide `b`,
                   //     the prime-checker flag becomes 0 and the loop stops)
  return a;}       //  And finally after all the nested loops, return `a` as result

Answer 21

Tidy, 33 bytes

{x:({v:⊟v<=-x}↦primes+2)@0@0}

Try it online!

Or, 28 chars/34 bytes: {x:({v:⊟v≤-x}↦primes+2)@0@0}

I'll explain this using an equivvalent, ASCII equivalent:

{x:({v:(-)over v<=-x}from primes+2)@0@0}
{x:                                    }    lambda w/ parameter `x`
                          primes+2          overlapping pairs of primes
                                            [[2, 3], [3, 5], [5, 7], ...]
    {v:             }from                   select prime pairs `v = [a, b]`...
       (-)over v                            ...where `a` - `b`...
                <=-x                        is <= `x`
   (                              )@0@0     select the first element of the first pair

Answer 22

APL(NARS), 36 char, 72 bytes

∇r←h w;k
r←2
→0×⍳w≤r-⍨k←1πr⋄r←k⋄→2
∇

1π is the function "next prime"; test:

  h¨1 2 3 4 6 10 16 17 18 30 50 100 200
2 3 7 7 23 113 523 523 523 1327 19609 370261 20831323  

Answer 23

Japt, 14 bytes

@§XnÈj}aX+j}a2

Try it or run all test cases (except 200 - seriously, don't even try it! If you want to verify that 200 returns the correct result, you can increase the starting value of 2 at the end to something closer to the expected output.)

@§XnÈj}aX+j}a2     :Implicit input of integer U
@                  :Function taking an integer X as argument
 §                 :  Is U <= ...
  Xn               :  Subtract X from
    È              :    Function taking an integer as input
     j             :      Is prime?
      }            :    End function
       a           :    Get the first integer that returns true when passed through that function starting at
        X+j        :      X plus is X prime
           }       :End function
            a2     :Get the first integer that returns true when passed through that function starting at 2