8
\$\begingroup\$

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.
Improve this question
\$\endgroup\$
0

6 Answers 6

Reset to default
4
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 88 bytes using a list comprehension instead of map(-p+)$iterate(k*)1 and <$> for map. \$\endgroup\$
    – ovs
    Mar 22, 2021 at 22:24
  • 1
    \$\begingroup\$ 70 bytes giving up some efficiency. \$\endgroup\$
    – Delfad0r
    Mar 23, 2021 at 0:14
3
\$\begingroup\$

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
            ɗ       )
             ɗ    )
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.