Finding Lonely Primes

Question

Lonely primes (as I call them) are primes, where given a number grid with width w ≥ 3, are primes which do not have any other primes adjacent to them orthogonally or diagonally.

For example, if we take this grid where w = 12 (primes highlighted in bold):

1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16 17 18 19 20 21 22 23...
 ...86 87 88 89 90 91 92 93 94 95 96
97 98 99 100 101 102 103 104 105 106 107 108
109 110 111 112 113 114 115 116 117 118 119 120

You can see that only the two primes 103 and 107 have no primes orthogonally or diagonally adjecant whatsoever. I've skipped over a section because there's no lonely primes there. (except 37, actually)

Your task is to, given two inputs w ≥ 3 and i ≥ 1, determine the first lonely prime in a number grid with width w, where said lonely prime must be greater than or equal to i. Inputs may be taken in any reasonable format (including taking them as strings). It is guaranteed there will be a lonely prime for width w.

The grid doesn't wrap around.

Examples:

w i output
11 5 11
12 104 107
12 157 157
9 1 151
12 12 37

As this is code-golf, shortest code wins!

• Jonathan Frech: Why is for w=12 not 37 a lonely prime? None of the numbers surrounding it -- {25, 26, 38, 49, 50} -- are prime.
• Okx: @JonathanFrech Yes, a test case includes that.

Answer 1

C (gcc), (削除) 159 (削除ここまで) (削除) 158 (削除ここまで) (削除) 149 (削除ここまで) 145 bytes

• Saved a byte thanks to xanoetux; removing one newline character.
• Saved (削除) nine (削除ここまで) thirteen bytes thanks to ceilingcat; golfing a break condition.

P(n,d,b){for(d=b=1<n;n>++d;)b*=n%d>0;n=b;}F(w,i){w=P(i)&!(P(i-w)|P(i+w)|i%w>1&(P(--i)|P(i-w)|P(i+w))|++i%w>0&(P(++i)|P(i-w)|P(i+w)))?i-1:F(w,i);}

Try it online!

• caylee: You may save one byte skipping the newline. Try it online!
• Jonathan Frech: @ceilingcat Fine suggestion, thanks.
• Jonathan Frech: @ceilingcat Thank you.

Answer 2

JavaScript (ES6), (削除) 116 (削除ここまで) 104 bytes

Takes input in currying syntax (w)(i).

w=>g=i=>!(C=(k,n=d=i+k)=>n>0?n%--d?C(k,n):d>1:1)(0)&[i,x=1,i-1].every(j=>C(x-w)&C(w+x--)|j%w<1)?i:g(i+1)

Test cases

let f =
w=>g=i=>!(C=(k,n=d=i+k)=>n>0?n%--d?C(k,n):d>1:1)(0)&[i,x=1,i-1].every(j=>C(x-w)&C(w+x--)|j%w<1)?i:g(i+1)
console.log(f(11)( 5)) // 11
console.log(f(12)(104)) // 107
console.log(f(12)(157)) // 157
console.log(f( 9)( 1)) // 151
console.log(f(12)( 12)) // 37

Commented

w => // main function, taking w
 g = i => // g = recursive function, taking i
 !( //
 C = ( // define C:
 k, // a function taking an offset k
 n = d = i + k // and using n and d, initialized to i + k
 ) => //
 n > 0 ? // if n is strictly positive:
 n % --d ? // decrement d; if d does not divide n:
 C(k, n) // do a recursive call
 : // else:
 d > 1 // return true if d > 1 (i.e. n is composite)
 : // else:
 1 // return true (n is beyond the top of the grid)
 )(0) & // !C(0) tests whether i is prime (or equal to 1, but this is safe)
 [ // we now need to test the adjacent cells:
 i, // right side: i MOD w must not be equal to 0
 x = 1, // middle : always tested (1 MOD w is never equal to 0)
 i - 1 // left side : (i - 1) MOD w must not be equal to 0
 ] // for each value j defined above,
 .every(j => // and for x = 1, 0 and -1 respectively:
 C(x - w) & // test whether i - w + x is composite
 C(w + x--) | // and i + w + x is composite
 j % w < 1 // or j MOD w equals 0, so that the above result is ignored
 ) ? // if all tests pass:
 i // return i
 : // else:
 g(i + 1) // try again with i + 1

Answer 3

Python 2, 144 bytes

f=lambda w,i,p=lambda n:all(n%j for j in range(2,n))*(n>1):i*(any(map(p,~-i%w*(i+~w,i-1,i+w-1)+(i-w,i+w)+i%w*(i-w+1,i+1,i-~w)))<p(i))or f(w,i+1)

Try it online!

Arguments in order: w, i.

No external modules used here.

Python 2 + sympy, 127 bytes

import sympy
f=lambda w,i,p=sympy.isprime:i*(any(map(p,~-i%w*(i+~w,i-1,i+w-1)+(i-w,i+w)+i%w*(i-w+1,i+1,i-~w)))<p(i))or f(w,i+1)

Try it online!

Not worthy of a different post, since the only difference here is that it uses sympy.isprime instead of a manually implemented prime check function.

Answer 4

MATL, 38 bytes

xx`@1G*:5MeZpt3Y6Z+>3LZ)ft2G<~)X<a~}2M

Try it online! Or verify all test cases.

Explanation

The code essentially consists of a loop that keeps enlarging the grid as described in the challenge by one row at each iteration.

After creating the grid at each iteration, the last row is removed (we cannot know if those primes are lonely or not) and the remaining numbers are tested to see if at least one lonely prime exists. This is done via 2D convolution.

If there is some lonely prime we exit the loop and output the first such prime. Else we proceed with the next iteration, which will try a larger grid.

(The code actually uses a transposed version of the grid, which is enlarged by columns instead of by rows.)

xx % Take two inputs (implicit): w, i. Delete them. They get copied
 % into clipboard G
` % Do...while
 @ % Push iteration index (1-based)
 1G % Push w
 * % Multiply
 : % Range from 1 to that
 5M % Push w again (from automatic clipboard M)
 e % Reshape into a matrix with w rows in column-major order
 Zp % Is prime? Element-wise
 t % Duplicate
 3Y6 % Push neighbour mask: [1 1 1; 1 0 1; 1 1 1]
 Z+ % 2D convolution, maintaining size
 > % Greater than? Element-wise. Gives true for lonely primes
 3LZ) % Remove the last column
 f % Find linear indices of nonzeros
 t % Duplicate
 2G % Push i
 <~ % Not less than?
 ) % Use as logical index: this removes lonle primes less than i
 X< % Minimum. This gives either empty or a nonzero value
 a~ % True if empty, false if nonzero. This is the loop condition.
 % Thus the loop proceeds if no lonely prime was found
} % Finally (execute on loop exit)
 2M % Push the first found lonely prime again
 % End (implicit). Display (implicit)

Answer 5

Julia 0.6, 135 bytes

using Primes
f(w,i,p=isprime)=findfirst(j->(a=max(j-1,0);b=min(j+1,w);c=a:b;!any(p,v for v=[c;c+w;c-w]if v>0&&v!=j)&&p(j)&&j>=i),1:w*w)

TIO doesn't have the Primes package. It's 5 bytes shorter if I'm allowed to return all lonely primes (findfirst becomes find). Julia's attempt to move functionality out of Base is hurting golfing (not a goal of Julia), Primes was included in 0.4.

Ungolfed (mostly)

function g(w,i)
 for j=i:w*w
 a,b=max(j-1,0),min(j+1,w)
 c=a:b
 !any(isprime,v for v=[c;c+w;c-w]if v>0&&v!=j)&&isprime(j)&&return j
 end
end

Answer 6

Jelly, 20 bytes

+‘ÆRœ^ḷ,ḷ’dạ/Ṁ€ṂḊð1#

Try it online!

How it works

+‘ÆRœ^ḷ,ḷ’dạ/Ṁ€ṂḊð1# Main link. Left argument: i. Right argument: w.
 ð Combine the links to the left into a chain and begin a new,
 dyadic chain with arguments i and w.
 1# Call the chain to the left with left argument n = i, i+1, ...
 and right argument w until 1 of them returns a truthy value.
 Return the match.
+ Yield n+w.
 ‘ Increment, yielding n+w+1.
 ÆR Yield all primes in [1, ..., n+w+1].
 ḷ Left; yield n.
 œ^ Multiset OR; if n belongs to the prime range, remove it; if
 it does not, append it.
 ,ḷ Wrap the resulting array and n into a pair.
 ’ Decrement all involved integers.
 d Divmod; map each integer k to [k/w, k%w].
 ạ/ Reduce by absolute difference, subtracting [n/w, n%w] from
 each [k/w, k%w] and taking absolute values.
 Ṁ€ Take the maximum of each resulting pair.
 A maximum of 0 means that n is not prime.
 A maximum of 1 means that n has a prime neighbor.
 Ṃ Take the minimum of the maxima.
 Ḋ Dequeue; map the minimum m to [2, ..., m].
 This array is non-empty/truthy iff m > 1.

Answer 7

Perl 6, (削除) 113 (削除ここまで) 104 bytes

->\w,\i{first {is-prime $_&none $_ «+«flat -w,w,(-w-1,-1,w-1)xx!($_%w==1),(1-w,1,w+1)xx!($_%%w)},i..*}

Try it online!

Answer 8

Clean, (削除) 181 (削除ここまで) ... 145 bytes

import StdEnv
@w i=hd[x+y\\y<-[0,w..],x<-[1..w]|x+y>=i&&[x+y]==[a+b\\a<-[y-w,y,y+w]|a>=0,b<-[x-1..x+1]|0<b&&b<w&&all((<)0o(rem)(a+b))[2..a+b-1]]]

Try it online!

Ungolfed:

@ w i
 = hd [
 x+y
 \\ y <- [0, w..]
 , x <- [1..w]
 | x+y >= i && [x+y] == [
 a+b
 \\ a <- [y-w, y, y+w]
 | a >= 0
 , b <- [x-1..x+1]
 | 0 < b && b < w && all ((<) 0 o (rem) (a+b)) [2..a+b-1]
 ]
 ]

Answer 9

Jelly, (削除) 30 (削除ここまで) 29 bytes

_{My guess is this is probably beatable by a fair margin}

×ばつ\+©8’:9Ġ®ṁLÞṪFÆPS’¬ð1#

A dyadic link taking i on the left and w on the right which returns the lonely prime.

Try it online!

How?

×ばつ\+©8’:9Ġ®ṁLÞṪFÆPS’¬ð1# - Link: i, w e.g. 37, 12
 1# - find the 1st match starting at i and counting up of...
 ð - ...everything to the left as a dyadic link
 - (n = i+0; i+1; ... on the left and w on the right):
ÆP - is i prime: 1 if so, 0 if not 1
 ŒR - absolute range: [-1,0,1] or [0] [-1,0,1]
 \ - last two links as a dyad (w on the right):
 ×ばつ - multiply (vectorises) [-12,0,12]
 +€ - add for €ach [[-13,-1,11],[-12,0,12],[-11,1,13]]
 - - i.e. the offsets if including wrapping
 8 - chain's left argument, i
 + - add [[24,36,48],[25,37,49],[26,38,50]]
 - - i.e. the adjacents if including wrapping
 © - copy to the register
 ’ - decrement [[23,35,47],[24,36,48],[25,37,49]]
 9 - chain's right argument, w
 : - integer division [[1,2,3],[2,3,4],[2,3,4]]
 Ġ - group indices by value [[1],[2,3]]
 - - for a prime at the right this would be [[1,2],[3]]
 - - for a prime not at an edge it would be [[1,2,3]]
 ® - recall from register [[24,36,48],[25,37,49],[26,38,50]]
 ṁ - mould like [[24,36,48],[[25,37,49],[26,38,50]]]
 Þ - sort by:
 L - length [[24,36,48],[[25,37,49],[26,38,50]]]
 Ṫ - tail [[25,37,49],[26,38,50]]
 - - i.e the adjacents now excluding wrapping
 F - flatten [25,37,49,26,38,50]
 ÆP - is prime? (vectorises) [0,1,0,0,0,0]
 S - sum 1
 ’ - decrement 0
 ¬ - not 1 

• Erik the Outgolfer: My guess is this is probably beatable by a fair margin are you sure? It's not an easy thing for golfing languages.
• Jonathan Allan: No, but it's my guess that (even) in Jelly (if not husk!!) that there could be a few ways to save on my method, or even a better approach.

Answer 10

Java 8, (削除) 176 (削除ここまで) 165 bytes

w->i->{for(;!p(i)|p(i-w)|p(i+w)|i%w>1&(p(--i)|p(i-w)|p(i+w))|++i%w>0&(p(++i)|p(i-w)|p(i+w)););return~-i;}boolean p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n>1;}

Port of Jonathan Frech' C answer.
-11 bytes thanks to @ceilingcat.

Try it online.