The Most Wanted Prime Numbers

Question

Output a sequence of all the primes that are of the following form: 123...91011...(n-1)n(n-1)..11109...321. That is, ascending decimal numbers up to some n, followed by a descending tail, all concatenated.

Background

Recently, Numberphile posted a video about primes that follow this pattern.

Output

1 -> 12345678910987654321 (n=10)
2 -> 123...244524462445...321 (n=2446)

No more terms are known, but it's likely that there are infinitely many.

Answer 1

05AB1E, 7 bytes

∞η€ûJʒp

Try it online! Times out on TIO without printing a single number because the primality test is too slow. Takes 77 seconds locally for the first number and will never† get to the second number.

∞η       Prefixes of [1, 2, 3, ...]
  €û     Palindromize each prefix
    J    Join each into a number
     ʒp  Filter: keep primes

Local output:

05AB1E git:master ❯ ./osabie programs/mwp.abe
["12345678910987654321"

† in the lifetime of the universe, the test is \$\mathcal{O(\sqrt{n} \log{}n})\$.

Answer 2

Jelly, 8 bytes

ŒḄV©ẒƊ#®

Try it online!

By default sequence I/O rules, this inputs a value k and outputs the prime corresponding to k.

This is a monadic link f(k) that returns the prime. It also outputs the n value for that prime as a side effect - this should be considered a function that returns the prime. I've included a 9 byte version that doesn't output anything extra below.

ŒḄV©ẒƊ#ṛ®

Try it online!

---

Both can handle \$k = 1\$ on TIO, can't handle \$k = 2\$ or above.

How they work

ŒḄV©ẒƊ#® - Main link. Takes k on the left
     Ɗ#  - Find the first n such that the following is true:
ŒḄ       -   Bounced range of n; [1, 2, ..., n, ..., 2, 1]
  V      -   Evaluated as an integer: 12...n...21
   ©     -   Save this in the register
    Ẓ    -   Is this prime?
       ® - Print n and return the register

The second uses ṛ® instead of ®. The ṛ causes the program to discard the value of n rather than printing it, and then ® returns the register.

Answer 3

Python 3, 213 bytes

def A(n):return int(''.join(str(d)for d in range(1,n+1))+''.join(str(d)for d in range(n-1,0,-1)))
i=5
w=0
y=int(input())
while 1:
	p=n=1;exec("p*=n*n;n+=1;"*~-A(i))
	if p%n==1:w+=1
	if w==y:print(A(i));break
	i+=1

Try it online!

Probably should be correct. If you find bugs then comment the answer.

Upvote Lynn solution of prime checking!

Answer 4

Here I used the Miller-Rabin Primality Test to approximate if the number is in fact prime.

import math
import random

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification

    # If number is even, it's a composite number

    if n == 2 or n == 3:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            print(_)
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def constructNumber(n):
    numberArray = []
    for i in range(n):
        numberArray.append(str(i+1))
    for i in range(n-1):
        numberArray.append(str((n-1)-i))
    return int(''.join(numberArray))

if __name__ == "__main__":
    print(miller_rabin((constructNumber(10)),40))

Miller-Rabin Python Source