Prime Difference

Question

Given an integer n, output the smallest prime such that the difference between it and the next prime is at least n.

For example, if n=5, you would output 23, since the next prime is 29, and 29-23>=5.

More Input/Output Examples

1 -> 2 (3 - 2 >= 1)
2 -> 3 (5 - 3 >= 2)
3 -> 7 (11 - 7 >= 3)
4 -> 7
5 -> 23
6 -> 23
7 -> 89
8 -> 89

This is code-golf, so shortest code wins.

Answer 1

Husk, 8 bytes

Ψḟo≥⁰≠İp

Try it online!

Inspired by this post in chat

ḟ, under normal circumstances, finds the first element of a list that satisfies a predicate. However, when combined with the function Ψ, it finds the first element that satisfies a predicate with respect to its successor in the list.

The predicate is o≥⁰≠, which asks if the absolute difference of two numbers is at least the input.

The list is İp, the list of prime numbers

Answer 2

Perl 6, 40 bytes

{1-$_+first ++($*=!*.is-prime)>=$_,2..*}

Try it online!

38 bytes, 0-based (I'm not sure this is allowed):

{-$_+first ++($*=!*.is-prime)>$_,2..*}

Try it online!

Answer 3

Perl 6, 56 bytes

{first {$^a.$![1]-$a>=$_},.$!}
$!={grep &is-prime,$_..*}

Try it online!

I feel like there's definitely some improvement to be made here, especially in regards to the $![1]. This is an anonymous code block that can be assigned to a variable, as well as a helper function assigned to $!.

Answer 4

J, 26 24 22 bytes

>:@]^:(>:4&p:-])^:_ 2:

Try it online!

0-based

Explanation:

                      2:  start with the first prime number and 
      ^:(        )^:_     while
         >:               the argument is greater or equal to the
               -          difference of
           4&p:           the next prime number and
                ]         the current prime number
  >:@]                    go to the next number

Answer 5

C (gcc), 58 bytes

Same logic as my JS answer, with a non-recursive implementation.

f(n,p,q,x){for(p=q=x=2;q-p<n;q%x--||(p=x?p:q,x=q++));q=p;}

Try it online!

Answer 6

Jelly, 8 bytes

2Æn:+ɗ1#

Try it online!

How it works

2Æn:+ɗ1#  Main link. Argument: n

2         Set the return value to 2.
      1#  Find the first k ≥ 2 such that the link to the left, called with arguments
          k and n, returns a truthy value.
     ɗ    Dyadic chain:
 Æn           Find the next prime p ≥ k.
    +         Yield k + n.
   :          Perform integer division.

Answer 7

JavaScript (ES6),  61 57 56  54 bytes

n=>(g=(q,x=q++)=>q-p<n?q%x--?g(q,x):g(x?q:p=q):p)(p=2)

Try it online!

Commented

n => (                    // n = input
  g = (                   // g = recursive function taking:
    q,                    //   q = prime candidate
    d = q++               //   d = divisor
  ) =>                    //
    q - p < n ?           // if q - p is not large enough:
      q % d-- ?           //   decrement d; if d was not a divisor of q:
        g(q, d)           //     try again until it is
      :                   //   else:
        g(                //     do a recursive call to look for the next prime
          d ? q : p = q   //       if q was prime, update the previous prime p to q
        )                 //     end of recursive call
    :                     // else:
      p                   //   success: return p
                          //   NB: we don't know if q is prime or not, but the only
                          //       thing that matters at this point is that the next
                          //       prime is greater than or equal to q
)(p = 2)                  // initial call to g with p = q = 2

---

Non-recursive version, 54 bytes

By porting back in JS my non-recursive port in C, it turns out that we can reach 54 bytes as well.

n=>eval(`for(p=q=x=2;q-p<n;q%x--||(p=x?p:q,x=q++));p`)

Try it online!

Performance

This piece of code is a good illustration of the utterly bad performance of eval(), which prevents JIT compilation:

• It takes 35 to 40 sec. to compute \$a(1)\$ to \$a(37)\$ on TIO with the above code.

• It takes ~1.5 sec. to do the same thing without eval():

  // 55 bytes
  n=>{for(p=q=x=2;q-p<n;q%x--||(p=x?p:q,x=q++));return p}
  

Answer 8

05AB1E, 9 bytes

∞<ØD¥I@Ïн

Try it online or verify all test cases.

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 9

Brachylog, 12 bytes

∧⟧ṗˢsĊ-≥?∧Ċt

Try it online!

Explanation

∧⟧              Take a descending range from an unknown integer down to 0
  ṗˢ            Select only primes in that range
    sĊ          Take a substring of 2 elements in that range; call it Ċ
      -≥?       The subtraction of those 2 elements must be greater than the input
         ∧Ċt    The output is the tail of Ċ

Answer 10

Python 2, 63 bytes

n=input()
k=P=b=2
while k-b<n:
 if P%k:b=k
 P*=k*k;k+=1
print b

Try it online!

Answer 11

Pari/GP, 38 bytes

n->i=2;while(nextprime(i+1)-i<n,i++);i

Try it online!

Answer 12

Ruby, 39 38 bytes

->n,m=2{Prime.find{|i|i-m>=n||!m=i};m}

Try it online!

Answer 13

Husk, 9 bytes

→←ġo<⁰-İp

Try it online!

This is a really interesting question allowing a range of possible approaches (and Husk is a good fit for it; I learned the language for the challenge).

The TIO link contains a wrapper to run this function on all inputs from 1 to 10.

Explanation

→←ġo<⁰-İp
       İp   The (infinite) list of primes
  ġ         Group them, putting adjacent primes in the same group if
      -         the difference between them
    <⁰          is less than the input
   o          (fix for a parser ambiguity that causes this parse to be chosen)
→           Take the last element of
 ←          the first group

Grouping primes that are too close together means that the first break in the groups will be the first point at which the primes are sufficiently far apart, so we simply just need to find the prime just after the break.

Other potential solutions

Here's an 8-byte solution that, sadly, only works with even numbers as input (and thus isn't valid):

-⁰LU⁰mṗN
       N   On the infinite list of natural numbers
     m     replace each element with
      ṗ      0 if composite, or a distinct number if prime
   U       Find the longest prefix with no repeated sublist of length
    ⁰        equal to the input
-⁰         Subtract the input from
  L          the length of that prefix

The idea is that when we have two primes that are a distance of (say) 6 apart, there'll be a sequence of five consecutive zeroes in the mṗN sequence, which contains two identical sublists of length 4 (the first four zeroes and last four zeroes), but such a repetition cannot happen earlier (because as each prime is mapped to a unique number, any length-4 substrings before the first prime gap > 4 will contain a prime number, and the substring will therefore be unique as it's the only substring which contains that number in that position). Then we just have to subtract the trailing zeroes from the length of the prefix to get our answer.

This doesn't work with odd inputs because the sublist of input zeroes only occurs once rather than twice, so the code ends up finding the second point at which it occurs rather than the first.

Answer 14

Japt, 16 bytes

@§Xn_j}aXÄ)©Xj}a

Try it or test 0-20