# The Most Wanted Prime Numbers

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.

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

• In other words, the subsequnce of A173426 filtered by primality. Dec 19 '21 at 12:34
• Two questions: 1. Is the output format flexible? 2. Is a probabilistic primality test ok, or is a deterministic test required? Dec 23 '21 at 0:31
• @cubiclettuce Use standard sequence output formats (click the tag for more info). I'd say that a deterministic test is required. Dec 24 '21 at 9:07

# 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})\$$.

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

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

• I may be misunderstanding something, but where is i updated? It seems that we will always print A(5)... Dec 18 '21 at 20:22
• no, infinite loop because the i don't increment. Dec 18 '21 at 21:50

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

• Welcome to Code Golf! This site is for competitive programming, so we require answers to make a serious attempt at golfing. Make sure to read our tips questions if you want some hints! Also, since this only seems to approximate whether a number is prime, it's wouldn't be valid (it's cool though!). Dec 21 '21 at 6:09