Do we share the prime cluster?

Question

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 code-golf, 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

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? — Jonathan Frech
– Jonathan Frech, Commented Nov 7, 2017 at 22:53
@JonathanFrech Truthy/Falsy per decision-problem definition, not necessarily consistent but distict and truthy/falsy — Mr. Xcoder
– Mr. Xcoder, Commented Nov 8, 2017 at 5:03

ETHproductions · Accepted Answer · 2017-11-06 20:10:46Z

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

\$\begingroup\$ Your programs source doesn’t look friendly... \$\endgroup\$

Stan Strum
– Stan Strum

2017-11-07 21:05:37 +00:00
Commented Nov 7, 2017 at 21:05 — Stan Strum
– Stan Strum, Commented Nov 7, 2017 at 21:05

Brad Gilbert b2gills · Accepted Answer · 2017-11-06 18:11:59Z

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 } }

score 2 · Accepted Answer · 2017-11-06 18:38:31Z

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!

Reinstate Monica -- notmaynard · Accepted Answer · 2017-11-06 20:07:23Z

Ruby, ₅₇ 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.

At that rate it is likely n². You know, 100001! = 2824257650254427477772164512240315763832679701040485762827423875723843380680572028502730496931545301922349718873479336571104510933085749261906300669827923360329777024436472705878118321875571799283167659071802605510878659379955675120386166847407407122463765792082065493877636247683663198828626954833262077780844919163487776145463353109634071852657157707925315037717734498612061347682956332369235999129371094504360348686870713719732258380465223614176068 ... (Warning: The output exceeded 128 KiB and was truncated.) which will take millenia to run. — user202729
– user202729, Commented Nov 7, 2017 at 1:10

Neil · Accepted Answer · 2017-11-06 21:35:20Z

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.

Jeppe Stig Nielsen · Accepted Answer · 2017-11-07 12:54:47Z

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.

Arnauld · Accepted Answer · 2017-11-07 13:38:32Z

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

CriminallyVulgar · Accepted Answer · 2017-11-07 15:15:06Z

2

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

edited Nov 7, 2017 at 15:15

answered Nov 7, 2017 at 9:07

CriminallyVulgar

5212 silver badges5 bronze badges

\$\begingroup\$ this tip for golfing in R is applicable here; and TIO has numbers installed instead \$\endgroup\$

Giuseppe
– Giuseppe

2017-11-07 15:05:41 +00:00
Commented Nov 7, 2017 at 15:05
\$\begingroup\$ Also, since min(x)==max(x) is equivalent to checking that all elements in is_prime(a:b) are equal, we can use this last trick to get it down to 46 bytes with either the primes or the numbers package. \$\endgroup\$

Giuseppe
– Giuseppe

2017-11-07 15:08:45 +00:00
Commented Nov 7, 2017 at 15:08

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

\$\begingroup\$ return a==c&&b==d; can be return!(a-c|b-d);. \$\endgroup\$

Jonathan Frech
– Jonathan Frech

2017-11-06 21:46:57 +00:00
Commented Nov 6, 2017 at 21:46 — Jonathan Frech
– Jonathan Frech, Commented Nov 6, 2017 at 21:46
\$\begingroup\$ 146 bytes. \$\endgroup\$

Jonathan Frech
– Jonathan Frech

2017-11-06 21:53:05 +00:00
Commented Nov 6, 2017 at 21:53 — Jonathan Frech
– Jonathan Frech, Commented Nov 6, 2017 at 21:53
\$\begingroup\$ @JonathanFrech Fixed the TIO link. \$\endgroup\$

pizzapants184
– pizzapants184

2017-11-07 22:15:29 +00:00
Commented Nov 7, 2017 at 22:15 — pizzapants184
– pizzapants184, Commented Nov 7, 2017 at 22:15

Erik the Outgolfer · Accepted Answer · 2017-11-06 20:16:08Z

1

Jelly, 6 bytes

ÆpżÆnE

Try it online!

-2 thanks to Dennis.

edited Nov 6, 2017 at 20:16

answered Nov 6, 2017 at 17:57

Erik the Outgolfer

40.8k5 gold badges46 silver badges125 bronze badges

Add a comment |

Adám · Accepted Answer · 2017-11-07 20:57:47Z

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.

ovs · Accepted Answer · 2017-11-07 21:40:40Z

1

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!

edited Nov 7, 2017 at 21:40

answered Nov 7, 2017 at 15:08

ovs

61.2k3 gold badges49 silver badges164 bronze badges

\$\begingroup\$ I like your set usage, even though it is not required for 87 bytes. \$\endgroup\$

Jonathan Frech
– Jonathan Frech

2017-11-07 21:19:33 +00:00
Commented Nov 7, 2017 at 21:19
\$\begingroup\$ @JonathanFrech I got it to 86 using sets \$\endgroup\$

ovs
– ovs

2017-11-07 21:41:07 +00:00
Commented Nov 7, 2017 at 21:41

Add a comment |

gastropner · Accepted Answer · 2017-11-09 20:07:54Z

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!

user28667 · Accepted Answer · 2017-11-07 11:26:53Z

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!

Eric Towers · Accepted Answer · 2017-11-07 13:42:57Z

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

@Jenny_mathy : I see you are correct. Caught by the "348, 347" test case, which is now demonstrated to pass. — Eric Towers
– Eric Towers, Commented Nov 6, 2017 at 23:28
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}]& — ZaMoC
– ZaMoC, Commented Nov 7, 2017 at 1:18
@Jenny_mathy : Well, ..., the specified input is two integers, not a list, so ... — Eric Towers
– Eric Towers, Commented Nov 7, 2017 at 2:43
@EricTowers taking a list is fine. Also, you can save a byte by using infix notation #~NextPrime~{-1,1}. — Martin Ender
– Martin Ender, Commented Nov 7, 2017 at 9:09

Galen Ivanov · Accepted Answer · 2017-11-07 16:52:16Z

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!

Razetime · Accepted Answer · 2021-01-17 08:23:52Z

0

Stax, 9 bytes

α╖ª»º√π├╔

Run and debug it

answered Jan 17, 2021 at 8:23

Razetime

27.6k3 gold badges31 silver badges77 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2021-01-18 09:37:48Z

05AB1E, 3 bytes

ŸpË

Port of @ETHproductions's Jelly answer, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

Ÿ # Create an inclusive ranged list of the (implicit) input-pair p # Check for each value in the list whether it's a prime (1 if truthy; 0 if falsey) Ë # Check if all values are the same (so either all truthy or all falsey) # (after which the result is output implicitly)

Stack Exchange Network

Do we share the prime cluster?

Task

Test cases / Examples

18 Answers 18

Jelly, 6 4 3 5 4 bytes

How it works

Perl 6, 52 bytes

Expanded:

Python 3, 103 95 91 bytes

Ruby, ₅₇ 54 bytes

Retina, 58 bytes

PARI/GP, 28 bytes

JavaScript (ES6), 57 56 bytes

Test cases

How?

R, 63 46 bytes

C (gcc), 153 146 bytes

Jelly, 6 bytes

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

How it works:

Python 2, 87 86 bytes

C (gcc), 103 bytes 100 bytes

Haskell, 81 bytes

Mathematica, 39 27 26 bytes

J, 15 bytes

Stax, 9 bytes

05AB1E, 3 bytes

Linked

Hot Network Questions

Do we share the prime cluster?

Task

Test cases / Examples

18 Answers 18

Jelly, 6 4 3 5 4 bytes

How it works

Perl 6, 52 bytes

Expanded:

Python 3, 103 95 91 bytes

Ruby, 57 54 bytes

Retina, 58 bytes

PARI/GP, 28 bytes

JavaScript (ES6), 57 56 bytes

Test cases

How?

R, 63 46 bytes

C (gcc), 153 146 bytes

Jelly, 6 bytes

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

How it works:

Python 2, 87 86 bytes

C (gcc), 103 bytes 100 bytes

Haskell, 81 bytes

Mathematica, 39 27 26 bytes

J, 15 bytes

Stax, 9 bytes

05AB1E, 3 bytes

Linked

Related

Hot Network Questions

Ruby, ₅₇ 54 bytes