10
\$\begingroup\$

The prime cluster of an integer N higher than 2 is defined as the pair formed by the highest prime strictly lower than N and the lowest prime strictly higher than N.

Note that following the definition above, if the integer is a prime itself, then its prime cluster is the pair of the primes preceding and succeeding it.

Task

Given two integers integers N, M (N, M ≥ 3), output a truthy / falsy value based on whether N and M have the same prime cluster.

This is , so the aim is to reduce your byte count as much as possible. Thus, the shortest code in every programming language wins.

Test cases / Examples

For instance, the prime cluster of 9 is [7, 11], because:

  • 7 is the highest prime strictly lower than 9, and
  • 11 is the lowest prime strictly higher than 9.

Similarly, the the prime cluster of 67 is [61, 71] (note that 67 is a prime).

Truthy pairs

8, 10
20, 22
65, 65
73, 73
86, 84
326, 318
513, 518

Falsy pairs

4, 5
6, 8
409, 401
348, 347
419, 418
311, 313
326, 305
\$\endgroup\$
  • \$\begingroup\$ Do the truthy / falsy values have to be two distinct values or can one define a mapping from their program's output to a truthy / falsy value and output (potentially infinitely) many different values? \$\endgroup\$ – Jonathan Frech Nov 7 '17 at 22:53
  • \$\begingroup\$ @JonathanFrech Truthy/Falsy per decision-problem definition, not necessarily consistent but distict and truthy/falsy \$\endgroup\$ – Mr. Xcoder Nov 8 '17 at 5:03

16 Answers 16

14
\$\begingroup\$

Jelly, 6 4 3 5 4 bytes

rÆPE

Try it online! or Try all test cases.

How it works

rÆPE    Main link. Arguments: N, M
r       Yield the range of integers between N and M, inclusive.
 ÆP     For each integer, yield 1 if it is prime, 0 otherwise.
   E    Yield 1 if all items are equal (none in the range were prime,
        or there's only one item).

Works because two numbers have different prime clusters iff there is a prime between them, or either number is itself prime; unless both numbers are the same, in which case E returns 1 anyway (all items in a single-item array are equal).

\$\endgroup\$
  • 7
    \$\begingroup\$ Your programs source doesn’t look friendly... \$\endgroup\$ – Stan Strum Nov 7 '17 at 21:05
2
\$\begingroup\$

Perl 6, 52 bytes

{[eqv] @_».&{(($_...0),$_..*)».first(*.is-prime)}}

Test it

Expanded:

{  # bare block lambda with implicit slurpy input 「@_」

  [eqv]               # see if each sub list is equivalent

    @_».&{            # for each value in the input

      (

        ( $_ ... 0 ), # decreasing Seq
          $_ ..  *    # Range

      )».first(*.is-prime) # find the first prime from both the Seq and Range

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

Python 3, 103 95 91 bytes

lambda*z:len({*z})<2or[1for i in range(min(z),max(z)+1)if all(i%k for k in range(2,i))]<[0]

Try it online!

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

Ruby, 57 54 bytes

->n,m{[*n..m,*m..n].all?{|x|?1*x=~/^(11+)\1+$/}||n==m}

Try it online!

Uses the horrible regex primality test from my answer (which I had forgotten about until I clicked on it) to the related question Is this number a prime?. Since we have N, M ≥ 3, the check for 1 can be removed from the pattern, making the byte count less than using the built-in.

Note: The regex primality test is pathologically, hilariously inefficient. I believe it's at least O(n!), though I don't have time to figure it right now. It took twelve seconds for it to check 100,001, and was grinding for five or ten minutes on 1,000,001 before I canceled it. Use/abuse at your own risk.

\$\endgroup\$
  • 1
    \$\begingroup\$ At that rate it is likely . You know, 100001! = 2824257650254427477772164512240315763832679701040485762827423875723843380680572028502730496931545301922349718873479336571104510933085749261906300669827923360329777024436472705878118321875571799283167659071802605510878659379955675120386166847407407122463765792082065493877636247683663198828626954833262077780844919163487776145463353109634071852657157707925315037717734498612061347682956332369235999129371094504360348686870713719732258380465223614176068 ... (Warning: The output exceeded 128 KiB and was truncated.) which will take millenia to run. \$\endgroup\$ – user202729 Nov 7 '17 at 1:10
2
\$\begingroup\$

Retina, 58 bytes

\b(.+)¶\1\b

.+
$*
O`
+`\b(1+)¶11\1
$1¶1$&
A`^(11+)\1+$
^$

Try it online! Explanation:

\b(.+)¶\1\b

If both inputs are the same, simply delete everything, and fall through to output 1 at the end.

.+
$*

Convert to unary.

O`

Sort into order.

+`\b(1+)¶11\1
$1¶1$&

Expand to a range of all the numbers.

A`^(11+)\1+$

Delete all composite numbers.

^$

If there are no numbers left, output 1, otherwise 0.

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

PARI/GP, 28 bytes

v->s=Set(v);#s<2||!primes(s)

Try it online with all test cases!

Returns 0 or 1 (usual PARI/GP "Boolean" values).

Explanation:

v must be a vector (or a column vector, or a list) with the two numbers N and M as coordinates. For example [8, 10]. Then s will be the "set" made from these numbers, which is either a one-coordinate vector (if N==M), or a two-coordinate vector with sorted entries otherwise.

Then if the number #s of coordinates in s is just one, we get 1 (truthy). Otherwise, primes will return a vector of all primes in the closed interval from s[1] to s[2]. Negation ! of that will give 1 if the vector is empty, while negation of a vector of one or more non-zero entries (here one or more primes) will give 0.

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

JavaScript (ES6), 57 56 bytes

Takes input in currying syntax (a)(b). Returns 0 or 1.

a=>b=>a==b|!(g=k=>a%--k?g(k):k<2||a-b&&g(a+=a<b||-1))(a)

Test cases

let f =

a=>b=>a==b|!(g=k=>a%--k?g(k):k<2||a-b&&g(a+=a<b||-1))(a)

console.log('Truthy')
console.log(f(8)(10))
console.log(f(20)(22))
console.log(f(65)(65))
console.log(f(73)(73))
console.log(f(86)(84))
console.log(f(326)(318))
console.log(f(513)(518))

console.log('Falsy')
console.log(f(4)(5))
console.log(f(6)(8))
console.log(f(409)(401))
console.log(f(348)(347))
console.log(f(419)(418))
console.log(f(311)(313))

How?

a => b =>                 // given a and b
  a == b |                // if a equals b, force success right away
  !(g = k =>              // g = recursive function taking k
    a % --k ?             //   decrement k; if k doesn't divide a:
      g(k)                //     recursive calls until it does
    :                     //   else:
      k < 2 ||            //     if k = 1: a is prime -> return true (failure)
      a - b &&            //     if a equals b: neither the original input integers nor
                          //     any integer between them are prime -> return 0 (success)
      g(a += a < b || -1) //     else: recursive call with a moving towards b
  )(a)                    // initial call to g()
\$\endgroup\$
2
\$\begingroup\$

R, 63 46 bytes

-17 by Giuseppe

function(a,b)!sd(range(numbers::isPrime(a:b)))

Try it online!

Pretty simple application of ETHProductions' Jelly solution. Main interesting takeaway is was that with R boolean vectors any(x)==all(x) is equivalent to min(x)==max(x).

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

C (gcc), 153 146 bytes

i,B;n(j){for(B=i=2;i<j;)B*=j%i++>0;return!B;}
#define g(l,m,o)for(l=o;n(--l););for(m=o;n(++m););
a;b;c;d;h(e,f){g(a,b,e)g(c,d,f)return!(a-c|b-d);}

-7 from Jonathan Frech

Defines a function h which takes in two ints and returns 1 for truthy and 0 for falsey

Try it online!

n is a function that returns 1 if its argument is not prime.

g is a macro that sets its first and second arguments to the next prime less than and greater than (respectively) it's third argument

h does g for both inputs and checks whether the outputs are the same.

\$\endgroup\$
  • \$\begingroup\$ return a==c&&b==d; can be return!(a-c|b-d);. \$\endgroup\$ – Jonathan Frech Nov 6 '17 at 21:46
  • \$\begingroup\$ 146 bytes. \$\endgroup\$ – Jonathan Frech Nov 6 '17 at 21:53
  • \$\begingroup\$ @JonathanFrech Fixed the TIO link. \$\endgroup\$ – pizzapants184 Nov 7 '17 at 22:15
1
\$\begingroup\$

Jelly, 6 bytes

ÆpżÆnE

Try it online!

-2 thanks to Dennis.

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

APL (Dyalog Unicode), 18+16 = 34 24 bytes

⎕CY'dfns'
∧/=/4 ¯4∘.pco⎕

Try it online!

Thanks to Adám for 10 bytes.

The line ⎕CY'dfns' (COPY) is needed to import the dfns (dynamic functions) collection, included with default Dyalog APL installs.

How it works:

∧/=/4 ¯4∘.pco⎕ ⍝ Main function. This is a tradfn body.
             ⎕ ⍝ The 'quad' takes the input (in this case, 2 integers separated by a comma.
          pco  ⍝ The 'p-colon' function, based on p: in J. Used to work with primes.
    4 ¯4∘.     ⍝ Applies 4pco (first prime greater than) and ¯4pco (first prime smaller than) to each argument.
  =/           ⍝ Compares the two items on each row
∧/             ⍝ Applies the logical AND between the results.
               ⍝ This yields 1 iff the prime clusters are equal.
\$\endgroup\$
1
\$\begingroup\$

Python 2, 87 86 bytes

lambda*v:v[0]==v[1]or{1}-{all(v%i for i in range(2,v))for v in range(min(v),max(v)+1)}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I like your set usage, even though it is not required for 87 bytes. \$\endgroup\$ – Jonathan Frech Nov 7 '17 at 21:19
  • \$\begingroup\$ @JonathanFrech I got it to 86 using sets \$\endgroup\$ – ovs Nov 7 '17 at 21:41
1
\$\begingroup\$

C (gcc), 103 bytes 100 bytes

i,j,p,s;f(m,n){s=1;for(i=m>n?i=n,n=m,m=i:m;i<=n;i++,p?s=m==n:0)for(p=j=2;j<i;)p=i%j++?p:0;return s;}

Try it online!

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

Haskell, 81 bytes

A straightforward solution:

p z=[x|x<-z,all((0/=).mod x)[2..x-1]]!!0
c x=(p[x-1,x-2..],p[x+1..])
x!y=c x==c y

Try it online!

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

Mathematica, 39 27 26 bytes

Equal@@#~NextPrime~{-1,1}&

Expanded:

                         &  # pure function, takes 2-member list as input
       #~NextPrime~{-1,1}   # infix version of NextPrime[#,{-1,1}], which
                            # finds the upper and lower bounds of each
                              argument's prime clusters
Equal@@                     # are those bounds pairs equal?

Usage:

Equal@@#~NextPrime~{-1,1}& [{8, 10}]
(*  True  *)

Equal@@#~NextPrime~{-1,1}& [{6, 8}]
(*  False  *)

Equal@@#~NextPrime~{-1,1}& /@ {{8, 10}, {20, 22}, {65, 65}, 
    {73, 73}, {86, 84}, {326, 318}, {513, 518}}
(*  {True, True, True, True, True, True, True}  *)

Equal@@#~NextPrime~{-1,1}& /@ {{4, 5}, {6, 8}, {409, 401}, 
    {348, 347}, {419, 418}, {311, 313}}
(*  {False, False, False, False, False, False}  *)

Contributions: -12 bytes by Jenny_mathy, -1 byte by Martin Ender

\$\endgroup\$
  • \$\begingroup\$ This only checks next prime. Try NextPrime[#,{-1,1}] \$\endgroup\$ – J42161217 Nov 6 '17 at 20:10
  • \$\begingroup\$ @Jenny_mathy : I see you are correct. Caught by the "348, 347" test case, which is now demonstrated to pass. \$\endgroup\$ – Eric Towers Nov 6 '17 at 23:28
  • \$\begingroup\$ 27 bytes: Equal@@NextPrime[#,{-1,1}]& takes as input [{N,M}] or if you want to keep the original input use this 30 bytes: Equal@@NextPrime[{##},{-1,1}]& \$\endgroup\$ – J42161217 Nov 7 '17 at 1:18
  • \$\begingroup\$ @Jenny_mathy : Well, ..., the specified input is two integers, not a list, so ... \$\endgroup\$ – Eric Towers Nov 7 '17 at 2:43
  • 1
    \$\begingroup\$ @EricTowers taking a list is fine. Also, you can save a byte by using infix notation #~NextPrime~{-1,1}. \$\endgroup\$ – Martin Ender Nov 7 '17 at 9:09
0
\$\begingroup\$

J, 15 bytes

-:&(_4&p:,4&p:)

How it works:

   &(           ) - applies the verb in the brackets to both arguments
            4&p:  - The smallest prime larger than y
      _4&p:       - The largest prime smaller than y
           ,      - append
 -:               - matches the pairs of the primes

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.