# 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.
• Apr 21, 2017 at 0:52
• Should 11 be included? It's not semiprime.
– xnor
Apr 21, 2017 at 4:53
• @xnor 11 is defined as the start of the sequence. You are correct that it is not a semiprime, but the 1 is not a Fibonacci number by definition either :) Apr 21, 2017 at 17:51

# Python 2, 7673727069 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.

• I have to say, your primality test is truly brilliant. I can't compete with this answer. Apr 21, 2017 at 4:40
• This is promising but skips 121.
– xnor
Apr 21, 2017 at 5:04
• @xnor Managed to include 121 at the cost of an extra byte. Thanks! Apr 21, 2017 at 16:15

# Jelly, 18 13 bytes

ṬÆẸ×©11ŒḂµ#ṛ®


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

Try it online!

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.  # 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. ## 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 216 primes apart, at which point //. will fail to attempt a sufficient number of substitutions. # Python 2, 1111071031021011009190 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! # 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  # 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  # 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! • You don't need parentheses around div n h. Also, it only affects efficiency, but the first 2# can probably be h#. Apr 24, 2017 at 5:40 • (==)=<<reverse$show n is shorter. Apr 24, 2017 at 5:49

# 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! • in "try it online" where i have to write the input? if i write 1 in the box "input" it return 395593 – user58988 Apr 21, 2017 at 16:00 • @RosLuP Normally it runs from the command line with the -R option. In the Online Version you have limits and $argn=81; is the input variable which is available in a command line version Apr 21, 2017 at 16:20
• so one has just to write input variable in the "$argn=81" so for example if input is 10 just rewrite it "$argn=10" ok, Thank you
– user58988
Apr 21, 2017 at 16:34
• @RosLuP Yes replace the number 81 with the input you wish Apr 21, 2017 at 16:39

# 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()