Palindromic Primes without 11 Every palindrome with an even number of digits is divisible by 11, so 11 is the only [palindromic prime] with an even number of digits. - David Wasserman, OEIS


I learned this today the manual way, before I did my research, when my program skipped numbers with an even number of digits (except 11) when calculating palindromic primes. Your task: create a program or function that when given an integer input N, outputs the Nth term in Stephen's Palindromic Sequence™.

Stephen's Palindromic Sequence™

Stephen's Palindromic Sequence™ starts with 11, and continues with palindromic semiprimes divisible by 11. Basically, all of the semiprimes that would be primes if 11 didn't "count." The upside is that this list contains numbers with an even number of digits! Yay. And, a lot of numbers with an odd number of digits are skipped, since they were already prime.

The beginning of the sequence:

1   : 11
2   : 22
3   : 33
4   : 55
5   : 77
6   : 121
7   : 737
8   : 979
9   : 1111
10  : 1441
11  : 1661
12  : 1991
13  : 3113
14  : 3223
15  : 3443
16  : 3883
17  : 7117
18  : 7447
19  : 7997
20  : 9119
21  : 9229
22  : 9449
23  : 10901


*Although 1331 (11^3) and similar fit the spirit of this sequence, they do not fit the rules.

Longer test cases:

26  : 91619
31  : 103301
41  : 139931
51  : 173371
61  : 305503
71  : 355553
81  : 395593
91  : 725527
101 : 772277
127 : 997799
128 : 1099901
141 : 3190913
151 : 3739373
161 : 7589857
171 : 9460649
200 : 11744711
528 : 39988993


Input

Integer N, >= 1. You can use a 0-indexed N (be sure to adjust test cases) if you specify so in your answer. Trailing newlines allowed.

Output

The Nth term in Stephen's Palindromic Sequence™. Trailing newlines allowed.

Rules


The only input your program/function can take is N. Your program cannot, for example, fetch a sequence from OEIS (aka standard loopholes apply).
You must be able to print an output up to six digits (N=127). Time is not a factor - however, if your program/function gets very long very fast, you must prove that the algorithm works. If your language naturally allows longer outputs, it you can let it expand naturally up to its limit, or cap it at ten digits, whichever you prefer. Output/termination beyond your limit does not matter, as long as it does not appear to be a valid output.
Program/function function on invalid input is irrelevant.
Python 2, 76 73 72 70 69 68 bytes



n=input();c=k=m=11
while n:m*=k/c;k+=c;n-=`k`==`k`[::~m%k-c]
print k


Thanks to @WheatWizard for golfing off 3 bytes!

Thanks to @ØrjanJohansen for golfing off 1 byte!

Thanks to @xnor and @ØrjanJohansen for paving the way to 68 bytes!

Input is 0-indexed. Try it online! or verify the first 31 test cases.

Background

Recall that Wilson's theorem states that for all integers p > 1,



meaning that (p - 1)! + 1 is evenly divisible by p if and only if p is prime.

If p > 1 is not prime, it is composite; let q be the smallest prime divisor of p. Clearly, q &leq; p/q. There are two cases:


If q = p/q, we have that p = q².

If q = 2, (p - 1)! = 3! = 6, so (p - 1)! is congruent to 2 modulo p.

If p/q = q > 2, so 2q &lt; p. This way, q and 2q are both among 1, …, p - 1, whose product is the factorial of p - 1, so 2p = 2q² = q · 2q divides (p - 1)! evenly.
If q &lt; p/q, q and p/q are both among 1, …, p - 1, so p = q · p/q divides (p - 1)! evenly.


Summing up,



for all integers p > 1.

Now, for all integer congruences and all integers a, b, and c, the following holds.



When a = -1, b = 11, and c = -1, we follow that



and, since 21 and -23 are congruent modulo 44 and -1 and 11p-1 are congruent modulo 11p, we arrive at the following conclusion.



For all possible values of p, the outcome (11, 21, or 11p - 1) will fall in the range 0, …, 11p - 1, so these values match those that will be returned by Python's % operator.

How it works

We initialize c, k, and m to 11 after the saving the input in n. c will be constant for the remainder of the program. Since there are three occurrences of c on the following line and assigning c costs only two bytes, this saves a byte. k can be thought of 11p using the meaning of p from the previous paragraph; initially, k = 11 = 11 · 1!. m takes the place of 11 · (p - 1)!; initially, m = 11 = 11 · 0!. k and m will satisfy the relationship m = 11 · (k/11)! at all times.

n represents the number of “Stephen's palindromes” we have to find. Since k = 11 initially, we can output k verbatim without further computation. However, when n is positive, we enter the while loop. The loop begins by multiplying m by k/c = p, then adding 11 to k, thus incrementing p. If k is a member of the sequence, we subtract 1 from n and start over. Once n reaches 0, we found the sequence member at the desired index and break out of the loop, then print the last value of k.

The expression

`k`==`k`[::~m%k-c]


performs the actual test, and it's result (True / 1 for sequence members, 0 / False otherwise) is subtracted from n. As seen before, ~m % k = (-m - 1) % k = (-11 · (p - 1)! - 1) % 11p equals 10 if p is prime, 21 if p = 4, and 11p - 1 > 43 if p > 4 is composite. Thus, after subtracting c = 11, we're left with -1 for prime p and a positive integer larger than 9 otherwise.

For prime p, ​`k`[::-1] gives us the string representation of k with reversed digit order, so comparing it to ​`k`​ checks whether k is a palindrome. If it is, all conditions are fulfilled and k is a sequence member. However, if p is not prime, the large range step and the fact that k will always have more than one digit mean that ​`k`[::-1] cannot have the same number of digits as ​`k`​, let alone be equal to it.