11
\$\begingroup\$

I know, I know, yet another primes challenge...

Related

A lonely (or isolated) prime is a prime number p such that p-2, p+2, p-4, p+4 ... p-2k, p+2k for some k are all composite. We call such a prime a kth-times-isolated prime.

For example, a 5th-times-isolated prime is 211, since all of 201, 203, 205, 207, 209, 213, 215, 217, 219, 221 are composite. (p-2*5=201, p-2*4=203, etc.)

Challenge

Given two input integers, n > 3 and k > 0, output the smallest kth-times-isolated prime that is strictly larger than n.

For example, for k = 5 and any n in range 4 ... 210, the output should be 211, since that's the smallest 5th-times-isolated prime strictly larger than the input n.

Examples

n=55 k=1
67

n=500 k=1
503

n=2100 k=3
2153

n=2153 k=3
2161

n=14000 k=7
14107

n=14000 k=8
14107

Rules

  • If applicable, you can assume that the input/output will fit in your language's native Integer type.
  • The input and output can be given by any convenient method.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
  • \$\begingroup\$ Is a 3rd-times-isolated prime also a 2nd-times-isolated prime? \$\endgroup\$ – Erik the Outgolfer Mar 7 '18 at 15:43
  • \$\begingroup\$ @EriktheOutgolfer The last two test cases indeed seems to confirm that. \$\endgroup\$ – Kevin Cruijssen Mar 7 '18 at 15:45
  • 1
    \$\begingroup\$ @KevinCruijssen Test cases are not a part of the challenge specification. \$\endgroup\$ – Erik the Outgolfer Mar 7 '18 at 15:49
  • 1
    \$\begingroup\$ @EriktheOutgolfer Yes, a kth-times-isolated is also, by definition, a k-1th, k-2th, etc. \$\endgroup\$ – AdmBorkBork Mar 7 '18 at 15:50
  • \$\begingroup\$ @AdmBorkBork Just wanted to check, thanks. \$\endgroup\$ – Erik the Outgolfer Mar 7 '18 at 15:52

10 Answers 10

3
\$\begingroup\$

Jelly, 17 13 bytes

_æR+⁼ḟ
‘ç1#Ḥ}

Try it online!

How it works

‘ç1#Ḥ}  Main link. Left argument: n. Right argument: k

‘       Increment; yield n+1.
    Ḥ}  Unhalve right; yield 2k.
 ç1#    Call the helper link with arguments m = n+1, n+2, ... and k until 1 one
        them returns a truthy value. Return the matching [m].


_æR+⁼ḟ  Helper link. Left argument: m. Right argument: k

_       Subtract; yield m-2k.
   +    Add; yield m+2k.
 æR     Prime range; yield the array of primes in [m-2k, ..., m+2k].
     ḟ  Filterfalse; yield the elements of [m] that do not occur in [k], i.e., [m]
        if m ≠ 2k and [] otherwise.
        The result to the left will be non-empty when m = 2k, as there always is
        a prime in [0, ..., 2m], since m > n > 3.
    ⁼   Test the results to both sides for equality.
        This yields 1 iff m is the only prime in [m-2k, ..., m+2k].
\$\endgroup\$
3
\$\begingroup\$

Husk, 13 bytes

ḟ§=;ofṗM+ṡD⁰→

Try it online!

Explanation

Pretty straightforward.

ḟ§=;ofṗM+ṡD⁰→  Inputs are k and n.
            →  Increment n
ḟ              and find the first number m >= n+1 such that:
         ṡD⁰    Take symmetric range [-2k,..,2k].
       M+       Add m to each.
    ofṗ         Keep those that are prime.
 §=             Check equality with
   ;            the singleton [m].
\$\endgroup\$
2
\$\begingroup\$

Java 8, 144 143 bytes

(n,k)->{for(k*=2;;)if(p(++n)>1){int i=-k;for(;i<=k&p(n+i)<2|i==0;i+=2);if(i>k)return n;}}int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}

Explanation:

Try it online.

(n,k)->{                      // Method with two integer parameters and integer return-type
  for(k*=2;                   //  Multiply `k` by 2
      ;)                      //  Loop indefinitely
    if(p(++n)>1){             //   Increase `n` by 1 before every iteration with `++n`
                              //   And if it's a prime:
      int i=-k;for(;i<=k      //    Loop `i` from `-k` to `k` (inclusive)
        &p(n+i)<2|i==0;       //    As long as `n+i` is not a prime (skipping `n` itself)
        i+=2);                //    And iterate in steps of 2 instead of 1
      if(i>k)                 //    If we've reached the end of the loop:
        return n;}}           //     We've found our result, so return it

// Separated method to check if `n` is a prime
// `n` is a prime if it remained unchanged, and not when it became 0 or 1
int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}
\$\endgroup\$
2
\$\begingroup\$

Python 2, 105 104 bytes

-1 byte thanks to ovs

n,k=input()
n+=1
while sum(all(x%i for i in range(2,x))^(x==n)for x in range(n-k*2,2*k-~n)):n+=1
print n

Try it online!

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

Stax, 14 bytes

åΣ▀ë F▬&■º↔╔^∞

Run and debug it

This is the corresponding ascii representation.

w^x:r{Hn+|p_!=m0#

w                   while; run the rest of the program until a falsy value remains
 ^                  increment candidate value.
  x:r               [-x, ..., -1, 0, 1, ... x] where x is the first input
     {        m     map using block, using k from -x to x
      Hn+           double and add to candidate value - this is "p+2k"
         |p         is it prime? produces 0 or 1
           _!       k is zero?
             =      two values are equal; always true for a passing candidate
               0#   any falses left after mapping? if so, continue running
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 94 92 89 bytes

f=(n,k)=>(Q=y=>y<-k||(P=(a,b=2)=>a>b?a%b&&P(a,b+1):1)(n+2*y)^!!y&&Q(--y))(k,++n)?n:f(n,k)

Try it online!

Mysteriously, further golfs end up stack overflow. Only this works at the size of 14000.

Finally one golf that won't end up stack overflow at 14000.

Explanation

f=(n,k)=>            // Two inputs
 (Q=y=>              // Function checking whether all numbers in 
                     // [n-2*k, n+2*k] except n are all composite
  y<-k               // The counter runs from k to -k
                     // If none breaks the rule, return true
  ||(P=(a,b=2)=>     // Function checking primality
   a>b?              // Check if a>b
   a%b&&P(a,b+1)     // If a>b and a%b==0 return false, else proceed
   :1                // If a<=b return 1 (prime)
  )(n+2*y)^!!y       // If n+2*y is prime, then y must be 0
                     // If n+2*y is not prime, then y must be non-zero
                     // If none of the conditions are met, return false
  &&Q(--y)           // Else proceed to the next counter
 )
 (k,++n)?            // Add 1 to n first, then start the check
 n                   // If conditions are met, return n
 :f(n,k)             // Else proceed to the next n.
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 113 bytes

P(n,d,b){for(b=d=n>1;++d<n;)b=b&&n%d;n=b;}f(n,k,i,f){for(f=n;f;)for(f=i=!P(++n);i++<k;f|=P(n+i+i)|P(n-i-i));f=n;}

Try it online!

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

Ruby + -rprime, 73 71 61 57 bytes

->n,k{n+=1;(-k..k).all?{|i|(i*2+n).prime?^(i!=0)}?n:redo}

Try it online!

It feels good to be learning! I'm using the Integer#[] and redo techniques that I learned here on PPCG. getting lost in the weeds of fun techniques...

-1 byte: Use n%2 instead of n[0] to get the least significant bit. Thanks, Asone Tuhid!

-1 byte: Use a ternary operator instead of a boolean expression. Thanks, Asone Tuhid!

-10 bytes: Use the XOR operator to avoid typing out .prime? twice... This is just as much Asone Tuhid's answer as mine now :)

-4 bytes: There's no harm in checking even values of n. Asone Tuhid is non-stop.

Ungolfed:

->n,k{
  n += 1;                   # Increment n
  (-k..k).all?{|i|          # In the set [n-2*k, n+2*k], is every number
    (i*2+n).prime? ^ (i!=0) #    EITHER prime XOR different from n itself?
  } ? n                     # If yes, return the current value of n
  : redo                    # Otherwise, restart the block
}
\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 55 bytes

f(n,k)=until(isprime(n++)&&#primes([n-2*k,n+2*k])<2,);n

Try it online!

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

Perl 6, 63 bytes

{$^k;first {[grep *.is-prime,$_-2*$k..$_+2*$k]eqv[$_]},$^a^..*}

Try it online!

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