27
\$\begingroup\$

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 = qp. 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).

Aditional rules

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
\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Luis Mendo Aug 3 '17 at 18:32
  • \$\begingroup\$ By p-q you mean q-p right? \$\endgroup\$ – Erik the Outgolfer Aug 3 '17 at 18:39
  • \$\begingroup\$ @EriktheOutgolfer Yes; corrected, thanks! \$\endgroup\$ – Luis Mendo Aug 3 '17 at 18:41
  • \$\begingroup\$ OEIS A104138 \$\endgroup\$ – Luis Mendo Aug 3 '17 at 18:49
  • \$\begingroup\$ OEIS A002386 (Related) \$\endgroup\$ – Stephen Aug 3 '17 at 18:52

21 Answers 21

3
\$\begingroup\$

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

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
\$\endgroup\$
  • \$\begingroup\$ Do we know for certain that the result will always be greater-than-or-equal-to the input? (# will count up from the input here) It seems reasonable to assume this but I for one have no idea if it's a valid assumption. EDIT: FYI to fix (if necessary) prefix with \$\endgroup\$ – Jonathan Allan Aug 3 '17 at 18:55
  • 5
    \$\begingroup\$ @JonathanAllan Bertrand's postulate implies that a prime's gap is strictly less than the prime itself. \$\endgroup\$ – Dennis Aug 3 '17 at 19:08
  • \$\begingroup\$ @Dennis brilliant thank you very much! TMYK... \$\endgroup\$ – Jonathan Allan Aug 3 '17 at 19:47
4
\$\begingroup\$

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&]]&
\$\endgroup\$
  • \$\begingroup\$ Clever clever... you don't even need to make sure both p and q are prime... The first code seems invalid, though, because it only goes up to 65535 unless you explicitly feed the argument MaxIterations. \$\endgroup\$ – JungHwan Min Aug 4 '17 at 15:42
  • \$\begingroup\$ Also, -2 bytes for the 35-byte version: (For[t=2,NextPrime@t-t<#,t++];t)& \$\endgroup\$ – JungHwan Min Aug 4 '17 at 15:43
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Of course there is some monad magic, thanks :) \$\endgroup\$ – flawr Aug 3 '17 at 23:02
  • \$\begingroup\$ zip=<<tail$[...] saves a byte. \$\endgroup\$ – Zgarb Aug 4 '17 at 4:58
  • \$\begingroup\$ "This generates an infinite list of primes first, then ..." : well, then should never happen ? (ie, it will only happen after an infinitely long time, the time to "first generate" procedurally an infinite list of primes) \$\endgroup\$ – Olivier Dulac Aug 4 '17 at 13:01
  • 1
    \$\begingroup\$ Haskell uses lazy evaluation, so only as many entries of that list are generated as are actually used. So those primes are generated up to the point where we actually find the points. If you try it you'll see that for any n it will stop after a finite amount of time :) (Haskell is not a procedural, but a functional language with lazy evaluation.) \$\endgroup\$ – flawr Aug 4 '17 at 13:36
  • 1
    \$\begingroup\$ Well it is an infinite list, by definition it does not have an end. What I described is just what is happening under the hood in the usual interpreters, but that is not specified as part of the language so you cannot tell that! \$\endgroup\$ – flawr Aug 4 '17 at 14:23
3
\$\begingroup\$

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.

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

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.

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

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

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ saved a bunch of bytes: repl.it/JwBe \$\endgroup\$ – Maltysen Aug 3 '17 at 19:00
2
\$\begingroup\$

Perl 6, 63 bytes

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

Try it online!

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

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

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

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)
\$\endgroup\$
  • \$\begingroup\$ You need to add cat(s) at the end. Implicit printing doesn't work in full programs. \$\endgroup\$ – JAD Aug 3 '17 at 21:28
2
\$\begingroup\$

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!

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

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

\$\endgroup\$
  • \$\begingroup\$ Can reverse return 0; return 1 and remove the ! before p(++n) \$\endgroup\$ – ceilingcat Aug 4 '17 at 17:02
  • \$\begingroup\$ d%i==0 and !(d%i) can be d%i<0. Also, using D's template system the solution in D can be: T p(T)(T d){for(T i=2;i<=d/2;++i)if(d%i<1)return 0;return 1;}T g(T)(T d){T f=2,n=3;while(n-f<d){f=n;do++n;while(!p(n));}return f;. (The removal of braces after the for and the do might apply to C++ as well) \$\endgroup\$ – Zacharý Aug 4 '17 at 21:03
  • \$\begingroup\$ I posted the separate D version, which utilizes D specific tricks that can't be found in C/C++/C#/Java. \$\endgroup\$ – Zacharý Aug 5 '17 at 15:16
  • \$\begingroup\$ 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;} <- that should work for the C++ version \$\endgroup\$ – Zacharý Jun 6 '18 at 20:10
2
\$\begingroup\$

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

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

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

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

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

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

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