Palindromic Primes without 11

Question

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.

Answer 1

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

Answer 2

Jelly, 18 13 bytes

ṬÆẸש11ŒḂµ#ṛ®

For some reason, this is much slower than my initial revision, despite doing exactly the same.

Try it online!

N = 127

dennis-home:~$ time jelly eun 'ṬÆẸש11ŒḂµ#ṛ®' <<< 127
997799

real    1m43.745s
user    1m43.676s
sys     0m0.113s

How it works

ṬÆẸש11ŒḂµ#ṛ®  Main link. No arguments.

         µ     Combine all links to the left into a chain.
          #    Read an integer n from STDIN and call the chain monadically, with
               argument k = 0, 1, 2, ... until n values of k result in a truthy
               output. Return the array of all matching values of k.
Ṭ                Untruth; yield [0, 0, 0, ..., 1] (k-1 zeroes followed by a 1) or
                 [] if k = 0.
 ÆẸ              Unexponents; consider the resulting array as exponents of the
                 sequence of primes and yield the corresponding integer. For k = 0,
                 this yields 1. For k > 0, it yields the k-th prime.
   ש11          Multiply the result by 11 and copy the product to the register.
       ŒḂ        Test if the product is a palindrome.
           ṛ®  Replace the resulting array with the integer in the register.

Answer 3

Brachylog, 17 bytes

:I{11|ṗ×₁₁≜.↔}ᶠ⁽t

Try it online!

This is 1-indexed.

Explanation

:I{          }ᶠ⁽t    Find the Input'th result of the following:
   11                  Output = 11
     |                 Or
          ≜.           Output is an integer…
      ṗ×₁₁             …which is the result of multiplying a prime by 11…
           .↔          …and Output reversed is still the Output

Two realizations with this answer:

• I need to fix the fact that superscript passing to metapredicates (with ⁽) does not work if there is no input to pass (which is why I have to add :I).
• I need to add a metapredicate to get the Nth result of a predicate (which would avoid using ᶠ⁽t and instead e.g. ⁿ⁽).

Implementing both changes would make that answer 14 bytes.

Answer 4

Mathematica, 65 60 bytes

n=NextPrime;11Nest[n@#//.x_/;!PalindromeQ[11x]:>n@x&,1,#-1]&

Iterates directly through primes using NextPrime and checks whether 11 times the prime is a palindrome. Works up to N = 528. The results 528 and 529 are more than 2¹⁶ primes apart, at which point //. will fail to attempt a sufficient number of substitutions.

Answer 5

Python 2, 111 107 103 102 101 100 91 90 89 bytes

Dennis has me beaten here, so go check out his answer.

This answer is zero indexed

n=input()
r=1
while n:r+=1;c=`r*11`;n-=all(r%x for x in range(2,r))*c==c[::-1]
print r*11

Try it online!

One byte saved thanks to math junkie

Explanation

First we take input and set it to n we also make a new variable r=1. We will count up r searching for palindromes that are the product of a prime and 11. Each time we find one we will decrement n until it reaches 0.

So we start a the loop:

while n:

The first thing we do is increment r

r+=1

We also predefine a variable c as the string representation of r*11

c=`r*11`

Now we want to decrement n if we have found such a number. We will simply subtract a boolean representing if r*11 fits the pattern from r. If this is False we will subtract zero and if it is True it will subtract 1.

To calculate the boolean we do:

all(r%x for x in range(2,r))*c==c[::-1]

The first part all will determine if r is prime. We multiply the result by c if r is prime this will just be c but if r is composite it will be "", the empty string. We then compare this to c[::-1] which is the reverse of c. If r is prime and c is a palindrome this will be True, if either fails the whole thing will evaluate as false.

When n is zero we simply print c.

83 bytes

Here is a recursive solution that is shorter but unfortunately doesn't meet the specs because it hits python's recursion cap too fast.

f=lambda n,r=1:n and f(n-all(r%x*(`r*11`==`r*11`[::-1])for x in range(2,r)),r+1)+11

Try it online!

Answer 6

05AB1E, 15 bytes

0-indexed.

11Iµ11N*DÂQNp*½

Try it online!

Explanation

11               # initialize stack with 11
  Iµ             # loop over N in [1 ... inf] until counter equals input
    11N*         # multiply N by 11
        D        # duplicate
         ÂQ      # check if the copy equals its reverse
           Np    # check if N is prime
             *   # multiply the results of the checks together
              ½  # if 1, increase counter

Answer 7

Husk, 12 bytes

!:11foṗ/11İ↔

Try it online!

!               # get element at input-th index of
 :11            # prepend 11 to
          İ↔    # palindromic numbers
    fo          # that satisfy
       /11      # when they're divided by 11
      ṗ         # the result is a prime

Answer 8

Haskell, 94 90 bytes

h#n|n<2=0|mod n h<1=1+h#div n h|j<-h+1=j#n
([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!)

Try it online! Example usage: ([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127.

[0,11..] constructs the infinite list [0,11,22,33, ...] (the zero is needed to make the sequence 1-indexed). For each n in this list we check n==(read.reverse.show)n, that is whether n is a palindrome. 3>2#n checks if n has at most two prime divisors. Because n is always divisible by 11, we don't get any real primes but only semiprimes.

Edit: Thanks to Ørjan Johansen for golfing 4 bytes!

Answer 9

PHP, 82 Bytes

for(;$d<$argn;$i>1||($p=11*$n)!=strrev($p)?:$d++)for($i=++$n;--$i&&$n%$i;);echo$p;

Try it online!

Answer 10

Axiom, 105 bytes

g(n)==(i:=c:=1;repeat(c=n=>break;i:=i+1;if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1)));i*11)

ungolf, test code and results

f(n)==
   i:=c:=1
   repeat
      c=n=>break
      i:=i+1
      if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1))
   i*11


(5) -> [[i,g(i)]  for i in 1..23]
   (5)
   [[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]]
                                          Type: List List PositiveInteger
(6) -> [[i,g(i)]  for i in [26,31,41,101,151,200]]
   (6)
   [[26,91619], [31,103301], [41,139931], [101,772277], [151,3739373],
    [200,11744711]]

Here g(700)=92511529 so the limit would be >700; ww(1000)=703999307 but using nextPrime()