Smallest prime q such that concatenation (p+q)"q is a prime

Question

Let p, q, and c := (p + q)"q (where " denotes concatenation) be positive integers such that p and c are primes and q is the smallest prime such that c is prime.

Such a prime triple (p, q, (p + q)"q) is for example (9721, 101, 9822101).

In natural order, the results start 3, 7, 3, 3, 19, 3, 31, ...

Challenge

Write a function that, given p, returns q that satisfies the above conditions.

Make sure that the program can calculate the given example in a reasonable time (say in 99 seconds).

Rules

Standard I/O rules apply and no standard loopholes.

This is code-golf, so shortest code in bytes wins.

---

---

Postscript

This sequence has an interesting addition: if you run through the sequence and pick out a number as it first appears, you get a sequence that the author of A375552 conjectures to be a permutation of the prime numbers.

Answer 1

Vyxal gr, 45 bits^v2, 5.625 bytes

Þp'⁰+Jæ

Try it Online!

Bitstring:

001010110100000101000111110000010010001101100

Þp'⁰+Jæ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎⁠⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌­
Þp        # ‎⁡a list of infinite primes
  '       # ‎⁢filtered by
   ⁰+     # ‎⁣(p+q)
     J   # ‎⁤(p+q)"q
       æ  # ‎⁢⁡is prime
💎

Created with the help of Luminespire. Try it Online!

Bitstring:

00101011010000010100011111000101000101101101110110

7 bytes without vyncode, some filter magic.

-1 from r flag

Answer 2

JavaScript (ES6), 59 bytes

p=>eval("for(d=q=1;q<d--|q%d&&n%d?1:d=n=d-1&&[++q+p]+q;)q")

Try it online!

faster / more readable, 61 bytes

p=>{for(d=q=1;q<d--|q%d&&n%d?1:d=n=d-1&&[++q+p]+q;);return q}

Try it online!

p => {              // p = input prime
  for(              // loop:
    d =             //   d = divisor
    q = 1;          //   q = the prime we're looking for
    q < d-- |       //   if q is less than d (decrement d afterwards)
    q % d           //   or d is not a divisor of q
    &&              //   AND
    n % d ?         //   q is not a divisor of n:
      1             //     keep searching
    :               //   else:
      d = n =       //     update d and n:
        d - 1       //       if d is not equal to 1 (meaning that
        &&          //       either q or n is composite):
        [++q + p] + //         increment q and build the new
        q;          //         candidate number
  );                // end of for()
  return q          // return q
}                   //

recursive, 55 bytes

p=>(g=d=>q<d--|q%d&&n%d?g(d):d-1?g(n=[++q+p]+q):q)(q=1)

Try it online!

Answer 3

Japt, 13 11 bytes

@°s+X*j)j}a

Try it, run all test cases or check the first 1000 terms

@°s+X*j)j}a     :Implicit input of integer U
@               :Function taking an integer X as argument
 °              :  Postfix increment U
  s+            :  Convert to string and append
    X*          :    X multiplied by
      j         :      Is X prime?
       )        :  End string conversion and convert back to int
        j       :  Is result prime?
         }      :End function
          a     :Get the first integer >=0 that returns truthy

Answer 4

Python, 97 bytes

g=lambda x:all(x%i for i in range(2,x))
f=lambda p,q=2:q if g(q)*g(int(f'{p+q}{q}'))else f(p,q+1)

Attempt This Online!

Answer 5

05AB1E, 8 bytes

∞Ø.Δ+y«p

Try it online or verify all test cases.

Explanation:

∞        # Push an infinite positive list: [1,2,3,...]
 Ø       # Map each to their 0-based n'th prime number: [3,5,7,...]
  .Δ     # Find the first prime in this list that's truthy for:
    +    #  Add it to the (implicit) input-integer
     y«  #  Append the current prime to this sum
       p #  Check if that is a prime itself
         # (after which the found result is output implicitly)

Although we skip prime 2 in the infinite list, since the infinite list starts at 1 and the n'th prime builtin is 0-based, it doesn't matter for the challenge, since appending a 2 to the sum will always result in an even number, and therefore never a prime.

Answer 6

Charcoal, 36 bytes

Ｎθ≔³ηＷ⊙⟦ηＩ⁺Ｉ⁺ηθＩη⟧⊙…¹÷견﹪κ⊕⊗μ≧⁺²ηＩη

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input p.

≔³η

Start with q=3.

Ｗ⊙⟦ηＩ⁺Ｉ⁺ηθＩη⟧⊙…¹÷견﹪κ⊕⊗μ

Check that both p and (q+p)&q are prime by trial division of all odd numbers.

≧⁺²η

If not then add 2 to q and try again.

Ｉη

Output the found value of q.

The golfiest code I could find was to switch to Wilson's theorem for prime checking but this is even slower than odd divisor checking, however it does at least let me save a further byte (and cause even more slowdown) by checking all integers rather than odd ones:

Ｎθ≔³ηＷ⊙⟦ηＩ⁺Ｉ⁺ηθＩη⟧﹪⊕Π…²κκ≦⊕ηＩη

Try it online! Link is to verbose version of code. Only shows an input of p=11 as the given test case would take too much time to compute (even p=419 is too slow).

Answer 7

Rust, 167 159 158 157 bytes

-1 byte thanks to ceilingcat

let g=|n|{if n==2{return 1}for i in 2..n{if n%i<1{return 0}}1};let f=|p:i32|{for q in 2..{if g(q)>0&&g(format!("{}{q}",p+q).parse().unwrap())>0{return q}}0};

Attempt This Online!

Answer 8

Ruby, 69 bytes

->p{2.step.find{|q|(2...r="#{q+p}#{q}".to_i).all?{|x|r*q%x>0||x==q}}}

Try it online!

Answer 9

Brachylog, 9 bytes

;.+;.cṗ∧ṗ

Try it online!

Explanation

;.+         Input + Output…
   ;.c      …concatenated with Output…
      ṗ     …is prime…
       ∧ṗ   …and Output itself is prime

Answer 10

SageMath, 130 bytes

def g(p): 
 for q in Primes(): 
  if is_prime(q+(p+q)*10^(1+int(log(q)/log(10)))):return q
print([g(p) for p in prime_range(100)])