Finding Distant Primes

Question

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 code-golf, so the shortest code (in bytes) wins.

Answer 1

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.

Answer 2

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

Answer 3

Haskell, 96 88 70 bytes

• 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

Answer 4

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

Answer 5

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.

Answer 6

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