# Finding Distant Primes

Let us call a prime $$\p\$$ an $$\(m,k)\$$-distant prime $$\(m \ge 0, k \ge 1, m,k \in\mathbb{Z})\$$ if there exists a power of $$\k\$$, say $$\k^x (x \ge 0, x \in\mathbb{Z})\$$, such that $$\|k^x-p| = m. \$$ For example, $$\23\$$ is a $$\(9,2)\$$-distant prime as $$\|2^5 - 23| = 9\$$. In other words, any prime which is at a distance of $$\m\$$ from some non-negative power of $$\k\$$ is an $$\(m,k)\$$-distant prime.

For this challenge, you can either:

• Take input three integers $$\n, m, k\; (n,k \ge1, m \ge0)\$$ and print the $$\n^{th}\$$ $$\(m,k)\$$-distant prime. You do not need to handle inputs where answer does not exist. You can take $$\n\$$ as zero-indexed if you want.
• Take $$\n, m, k\$$ as input and print the first $$\n\$$ $$\(m,k)\$$-distant primes.
• Or, take only $$\m\$$ and $$\k\$$ as input and print all $$\(m,k)\$$-distant primes. It is fine if your program runs infinitely and does not terminate if there aren't any $$\(m,k)\$$-distant primes, or all such primes have already been printed.

# Examples

m,k    -> (m,k)-distant primes
1,1    -> 2
0,2    -> 2
1,2    -> 2, 3, 5, 7, 17, 31, 127, 257, 8191, 65537, 131071, 524287, ...
2,2    -> 2, 3
2,3    -> 3, 5, 7, 11, 29, 79, 83, 241, 727, 6563, 19681, 59051
3,2    -> 5, 7, 11, 13, 19, 29, 61, 67, 131, 509, 1021, 4093, 4099, 16381, 32771, 65539, 262147, ...
20,2   -> None
33,6   -> 3
37,2   -> 41, 53, 101, 293, 1061, 2011, 4133, 16421, ...
20,3   -> 7, 23, 29, 47, 61, 101, 223, 263, 709, 2207, 6581, 59029, 59069, 177127, 177167
20,7   -> 29, 2381, 16787
110,89 -> 199, 705079


# Rules

• Standard loopholes are forbidden.
• You may choose to write functions instead of programs.
• This is , so the shortest code (in bytes) wins.

# Brachylog, 13 bytes

^ᵗ↙X≜ℕ₁ᵗ~ȧʰ+ṗ


Try it online!

^ᵗ↙X≜ℕ₁ᵗ~ȧʰ+ṗ  Given input [A,B]
^ᵗ↙X≜          Try every X: [A, B^X]
ℕ₁ᵗ       B^X ≥ 1
~ȧʰ    Try [A, B^X] and [-A, B^X]
+   Sum of A + B^X or -A + B^X
ṗ  is a prime.


# JavaScript (ES6), 103 bytes

Expects (m)(k)(n) and returns the $$\n\$$-th $$\(m,k)\$$-distant prime (1-indexed).

m=>k=>F=(n,p)=>(g=d=>p%--d?g(d):d^1)(p)|(g=(n,K=1)=>K>n||K<n&k>1&&g(n,K*k))(p+m)*g(p-m)||--n?F(n,-~p):p


Try it online!

### Commented

m => k =>            // outer functions taking m and k
F = (n, p) =>        // inner recursive function taking n
(                    // and using p = current prime candidate
g = d =>           // g is a recursive function taking a divisor d
p % --d ? g(d)   //   decrement d until it divides p
: d ^ 1  //   return a truthy value if p is composite
)(p) |               // initial call to g with d = p
(                    //
g = (n,            // g is a recursive function taking n = p + m or p - m
K = 1) =>  // and K = k ** x
K > n ||         //   if K is greater than n
K < n & k > 1 && //   or K is less than n and k is greater than 1:
g(n, K * k)    //     do a recursive call with k raised to the next exponent
)(p + m) *           // unless the above function is truthy for p + m ...
g(p - m)             // ... and for p - m (meaning that we don't have |k**x-p|=m)
// or p was composite:
|| --n               //   decrement n
?                    // if all of the above is truthy:
F(n, -~p)          //   try again with p + 1
:                    // else:
p                  //   success: return p


• Saved 8 bytes thanks to @ovs!
• Saved 18 bytes thanks to @Delfad0r!
m!k=[p|p<-[2..],all((>0).mod p)[2..p-1],elem m[abs$k^i-p|i<-[0..m+p]]]  Try it online! m!k= -- The function's called with m!k [p| -- Yield every p when p <- [2..], -- p is an integer >= 2 all((>0).mod p)[2..p-1], -- p is prime all -- For all [2..p-1] -- possible divisors of p, mod p -- p mod that number >0 -- is greater than 0 elem m[abs$k^i-p|i<-[0..m+p]] -- Make sure it's (m, k)-distant

• 88 bytes using a list comprehension instead of map(-p+)$iterate(k*)1 and <$> for map.
– ovs
Mar 22, 2021 at 22:24
• 70 bytes giving up some efficiency. Mar 23, 2021 at 0:14

# Jelly, 16 15 bytes

2Ẓȧ+,_ɗ⁴æḟƑƇɗɗ#


Try it online!

Takes three command line arguments $$\k\$$, $$\m\$$, $$\n\$$. Produces the first $$\n\$$ $$\(m, k)\$$-distant primes.

## Explanation

2Ẓȧ+,_ɗ⁴æḟƑƇɗɗ#   Main dyadic link
2                 Starting with 2
#   Find the first n numbers p such that
ɗ    (
Ẓ                  p is prime
ȧ                 and
ɗ       (
+,_ɗ⁴              p ± m
Ƈ          Filter items that
Ƒ             don't change when
æḟ                rounded down to the nearest power of k
ɗ       )
ɗ    )


# R, 79 bytes

function(m,k)repeat{while(sum(!(T=T+1)%%2:T)>1|all(abs(k^(0:T)-T)-m))1;show(T)}


Try it online!

Prints all (m,k)-distant primes.

# JavaScript (V8), 91 bytes

m=>k=>{for(i=1;;(g=v=>!v+!~-k+v%k?~-v:g(v/k))(i-m)*g(i+m)+~-j||print(i))for(j=++i;i%--j;);}


Try it online! (i<1000 is added so you can test it with multiple testcases.)

This function takes only $$\m\$$ and $$\k\$$ as input, and prints all $$\\left(m,k\right)\$$-distant primes (in language supported integer range).