Splitting Into Two Primes

The fact that the number starts with $999...$ and ends with $...001$ suggests that the both factors are of the form $\overline{999xyx999}$ . Following this hunch, we can expand

$999415083136585001-\left( 999000999+101000a_1+10000a_2 \right) \left( 999000999+101000b_1+10000b_2) \right) =$

$1412087133587000 - 100899100899000 a_1 - 9990009990000 a_2$ $-100899100899000 b_1 - 10201000000 a_1 b_1 - 1010000000 a_2 b_1$ $- 9990009990000 b_2 - 1010000000 a_1 b_2 - 100000000 a_2 b_2$

From this we can deduce that $b_1=13-a_1$ and then $b_2=10-a_2$ , and then from those we end up with solving for $a_1$ :

$10c+2-3a_1+a_1^{2}=0$

where $c$ is an integer. From this, we find that $a_1=6, \; a_2=8, \; b_1=7,\; b_2=2$ , and the numbers are

$(999686999)(999727999)=999415083136585001$

I used Fermat's Factorization,here N = 999415083136585001. $N=a^{2}-b^{2}$ and so the two primes are $a+b$ and $a-b$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import math
def fermat(n):
    a = int(math.ceil(n**0.5))
    b2 = a*a - n
    b = int(b2**0.5)
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b =int(b2**0.5)
    p=a+b
    q=a-b
    print p+q


n=999415083136585001
fermat(n)

Almost immediately,the output.i.e: $\boxed{1999414998}$

There are only $5953$ palindromic primes less than $10^9$ (having a file listing the primes less than $10^9$ after solving one of Thaddeus' previous problems was useful!). Checking the two of these which multiplied together to get the right answer was elementary: $999686999 \times 999727999 \; = \; 999415083136585001 \;.$

I think optimal prime testing algorithms such as the Sieve of Eratosthenes would be appropriate for this problem. Since the number is a product of two palindromic prime numbers, it would be efficient to start from $\sqrt{999415083136585001}$ and try incrementing and decrementing from there.