[Question]
  [
Some numbers, such as \$14241\$, are palindromes in base 10: if you write the digits in reverse order, you get the same number.
Some numbers are the sum of 2 palindromes; for example, \$110=88+22\$, or \$2380=939+1441\$.
For other numbers, 2 palindromes are not enough; for example, 21 cannot be written as the sum of 2 palindromes, and the best you can do is 3: \$21=11+9+1\$.
Write a function or program which takes integer input `n` and outputs the `n`th number which cannot be decomposed as the sum of 2 palindromes. This corresponds to [OEIS A035137](https://oeis.org/A035137).
Single digits (including 0) are palindromes.
Standard rules for sequences apply:
* input/output is flexible
* you may use 0- or 1- indexing
* you may output the `n`th term, or the first `n` terms, or an infinite sequence
*(As a sidenote: all integers [can be decomposed](https://arxiv.org/abs/1602.06208) as the sum of at most 3 palindromes.)*
Test cases (1-indexed):
```
1 -> 21
2 -> 32
10 -> 1031
16 -> 1061
40 -> 1103
```
This is code-golf, so the shortest answer wins.
  
[Answer]
# JavaScript (ES6), ~~93 83 80~~ 79 bytes
*Saved 1 byte thanks to @tsh*
Returns the \$n\$th term, 1-indexed.
```
i=>eval("for(n=k=1;k=(a=[...k+[n-k]+k])+''!=a.reverse()?k-1||--i&&++n:++n;);n")
```
[Try it online!](https://tio.run/##XcuxDoMgFEDRvV9hHRRCQJ82DjWv/RDjQCw2FgMNNEz@OzUxLgx3OrkfGaSf3PL9cWNfKs4YF3yoIFeSz9YRgxqh10gkDkIIzQbD9cj0SFlZXlEKp4JyXhH61By2jfOlKBgz972e9iancbLG21WJ1b7JTDKgNKuqrIFLAs0BbZMA1AdA3aYPdCd1Kd3Oa9/iHw "JavaScript (Node.js) – Try It Online")
### How?
Given \$n\$, we test whether there exists any \$1\le k\le n\$ such that both \$k\$ and \$n-k\$ are palindromes. If we do find such a \$k\$, then \$n\$ is the sum of two palindromes.
The trick here is to process \$k\$ and \$n-k\$ at the same time by testing a single string made of the concatenation of \$k\$, \$n-k\$ and \$k\$.
*Example:*
For \$n=2380\$:
* we eventually reach \$k=1441\$ and \$n-k=939\$
* we test the string "\$1441\color{red}{939}1441\$" and find out that it is a palindrome
### Commented
*NB: This is a version without `eval()` for readability.*
```
i => {                       // i = index of requested term (1-based)
  for(                       // for loop:
    n = k = 1;               //   start with n = k = 1
    k =                      //   update k:
      ( a =                  //     split and save in a[] ...
        [...k + [n - k] + k] //     ... the concatenation of k, n-k and k
      ) + ''                 //     coerce it back to a string
      != a.reverse() ?       //     if it's different from a[] reversed:
        k - 1                //       decrement k; if the result is zero:
          || --i             //         decrement i; if the result is not zero:
            && ++n           //           increment n (and update k to n)
                             //         (otherwise, exit the for loop)
      :                      //     else:
        ++n;                 //       increment n (and update k to n)
  );                         // end of for
  return n                   // n is the requested term; return it
}                            //
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~16 10~~ 9 bytes
-1 byte thanks to [Erik the Outgolfer](https://codegolf.stackexchange.com/users/41024/erik-the-outgolfer). Outputs the first \$n\$ terms.
```
2_ŒḂƇ⁺ṆƲ#
```
[Try it online!](https://tio.run/##y0rNyan8/98o/uikhzuajrU/atz1cGfbsU3K/4GCAA "Jelly – Try It Online")
I tried to come up with different idea compared to my original approach. Let's review the thinking process:
* Initially, the test worked as follows: It generated the integer partitions of that number, then filtered out those that also contained non-palindromes, then counted how many length-2 eligible lists there were. This was obviously not too efficient in terms of code length.
* Generating the integer partitions of \$N\$ and then filtering had 2 main disadvantages: length and time efficiency. To solve that issue, I thought I shall first come up with a method to generate *only* the pairs of integers \$(x, y)\$ that sum to \$N\$ (not all arbitrary-length lists) with the condition that both numbers must be palindrome.
* But still, I wasn't satisfied with the "classic way" of going about this. I switched approaches: instead of generating *pairs*, let's have the program focus on *idividual palindromes*. This way, one can simply compute all the palindromes \$x\$ below \$N\$, and if \$N-x\$ is also palindrome, then we're done.
### Code Explanation
```
2_ŒḂƇ⁺ṆƲ# – Monadic link or Full program. Argument: n.
2       # – Starting at 2\*, find the first n integers that satisfy...
 _ŒḂƇ⁺ṆƲ  – ... the helper link. Breakdown (call the current integer N):
    Ƈ     – Filter. Creates the range [1 ... N] and only keeps those that...
  ŒḂ      – ... are palindromes. Example: 21 -> [1,2,3,4,5,6,7,8,9,11]
 _        – Subtract each of those palindromes from N. Example: 21 -> [20,19,...,12,10]
     ⁺    – Duplicate the previous link (think of it as if there were an additional ŒḂƇ
            instead of ⁺). This only keeps the palindromes in this list.
            If the list is non-empty, then that means we've found a pair (x, N-x) that
            contains two palindromes (and obviously x+N-x=N so they sum to N).
      Ṇ   – Logical NOT (we're looking for the integers for which this list is empty).
       Ʋ  – Group the last 4 links (basically make _ŒḂƇ⁺Ṇ act as a single monad).
```
\* Any other non-zero digit works, for that matter.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 11 bytes
```
⁵ŻŒḂ€aṚ$EƲ#
```
[Try it online!](https://tio.run/##ASIA3f9qZWxsef//4oG1xbvFkuG4guKCrGHhuZokRcayI////zQw "Jelly – Try It Online")
The full program roughly works like this:
1. Set **z** to the input.
2. Set **x** to **10**.
3. Set **R** to **[]**.
4. For every integer **k** from **0** up to and including **x**, check whether both **k** and **x - k** are palindromic.
5. If all elements of **L** are equal (that is, if either all possible pairs that sum to **x** have both their elements palindromic, or all such pairs have at most one of their elements be palindromic), set **z** to **z - 1** and append **x** to **R**.
6. If **z = 0**, return **R** and end.
7. Set **x** to **x + 1**.
8. Go to step 4.
You may suspect that step 5 doesn't actually do the job it should. We should really not decrement **z** if all pairs that sum to **x** are palindromic. However, we can prove that this will never happen:
Let's first pick an integer \$k\$ so that \$10\le k\le x\$. We can always do so, because, at step 2, we initialize **x** to be **10**.
If \$k\$ isn't a palindrome, then we have the pair \$(k,x-k)\$, where \$k+(x-k)=x\$, therefore not all pairs have two palindromes.
If, on the other hand, \$k\$ is a palindrome, then we can prove that \$k-1\$ isn't a palindrome. Let the first and last digits of \$k\$ be \$D\_F\$ and \$D\_L\$ respectively. Since \$k\$ is a palindrome, \$D\_F=D\_L>0\$. Let the first and last digits of \$k-1\$ be \$D'\_F\$ and \$D'\_L\$ respectively. Since \$D\_L>0\$, \$D'\_L=D'\_F-1\ne D'\_F\$. Therefore, \$k-1\$ isn't a palindrome, and we have the pair \$(k-1,x-(k-1))\$, where \$(k-1)+(x-(k-1))=k-1+x-k+1=x\$.
We conclude that, if we start with setting **x** to a value greater than or equal to **10**, we can never have all pairs of non-negative integers that sum to **x** be pairs of palindromes.
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), ~~135~~ 102 bytes
```
K`0
"$+"{0L$`\d+
*__
L$`
<$.'>$.`>
/<((.)*.?(?<-2>\2)*(?(2)$)>){2}/{0L$`\d+
*__
))L$`
<$.'>$.`>
0L`\d+
```
[Try it online!](https://tio.run/##K0otycxLNPz/3zvBgEtJRVup2sBHJSEmRZtLKz6eC8jkslHRU7dT0Uuw49K30dDQ09TSs9ewt9E1sosx0tTSsNcw0lTRtNOsNqrVR9GqqYmq2cAHJPX/vyUA "Retina – Try It Online") Too slow for `n` of 10 or more. Explanation:
```
K`0
```
Start off by trying 0.
```
"$+"{
```
Repeat `n` times.
```
0L$`\d+
*__
```
Convert the current trial value to unary and increment it.
```
L$`
<$.'>$.`>
```
Create all pairs of non-negative integers that sum to the new trial value.
```
/<((.)*.?(?<-2>\2)*(?(2)$)>){2}/{
```
Repeat while there exists at least one pair containing two palindromic integers.
```
0L$`\d+
*__
))L$`
<$.'>$.`>
```
Increment and expand the trial value again.
```
0L`\d+
```
Extract the final value.
[Answer]
## Haskell, ~~68~~ ~~67~~ 63 bytes
```
[n|n<-[1..],and[p a||p(n-a)|a<-[0..n]]]
p=((/=)=<<reverse).show
```
Returns an infinite sequence.
Collect all `n` where either `a` or `n-a` is not a palindrome for all `a <- [0..n]`. 
[Try it online!](https://tio.run/##DcmxDsIgEADQ3a@4wQESOdsdvgQZLhVsUzwv0OjCt3v61rdS33OtWsJNIw/2Ls6I6UJ8jwI0hhh2ZAf9Y0LklNJJgjHXYIP3Lb9z69liX18ffdLGEEDaxgec4aA9wzxB0e9SKj26ukXkBw "Haskell – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/) `-MList::Util=any -p`, ~~59~~ 55 bytes
*-3 bytes thanks to @NahuelFouilleul*
```
++$\while(any{$\-reverse($\-$_)==reverse}0..$\)||--$_}{
```
[Try it online!](https://tio.run/##K0gtyjH9/19bWyWmPCMzJ1UjMa@yWiVGtyi1LLWoOFUDyFSJ17S1hfJrDfT0VGI0a2p0gcK11f//mxj8yy8oyczPK/6v62uqZ2BoAKR9MotLrKxCSzJzbIHG/dctAAA "Perl 5 – Try It Online")
Note: `any` could be replaced by `grep` and avoid the `-M` command line switch, but under the current scoring rules, that would cost one more byte.
[Answer]
# [R](https://www.r-project.org/), ~~115~~ 111 bytes
*-4 thanks to Giuseppe*
```
function(n,r=0:(n*1e3))r[!r%in%outer(p<-r[Map(Reduce,c(x<-paste0),Map(rev,strsplit(a<-x(r),"")))==a],p,'+')][n]
```
[Try it online!](https://tio.run/##FcixCsMgEADQvX/RQMhde4K2nYp@Qpeu4iBWQShGLqbk7y0ub3jck@lpL6HltUAhNvIJ5aLiHZHtmedc5nVvkaFqwfblK7zjZw@RAhxaVL@1KJHGc/zR1nir39zAa3EAI00TIhrjHVVargs6W1xPoPCU4DZQcviQ2P8 "R – Try It Online")
Most of the work is packed into the function arguments to remove the `{}` for a multi-statement function call, and to reduce the brackets needed in defining the object `r`
Basic strategy is to find all palindromes up to a given bound (including 0), find all pairwise sums, and then take the n-th number not in that output.
The bound of `n*1000` was chosen purely from an educated guess, so I encourage anyone proving/disproving it as a valid choice.
`r=0:(n*1e3)`can probably be improved with a more efficient bound.
`Map(paste,Map(rev,strsplit(a,"")),collapse="")`is ripped from Mark's answer [here](https://codegolf.stackexchange.com/questions/146084/yo-boy-must-it-sum/146256#146256), and is just incredibly clever to me.
`r[!r%in%outer(p,p,'+')][n]`reads a little inefficient to me.
[Answer]
# [C# (Visual C# Interactive Compiler)](http://www.mono-project.com/docs/about-mono/releases/5.0.0/#csc), 124 bytes
```
n=>{int a=0;for(string m;n>0;)if(Enumerable.Range(0,++a).All(x=>!(m=x+""+(a-x)+x).Reverse().SequenceEqual(m)))n--;return a;}
```
[Try it online!](https://tio.run/##Fc2xCoNADIDhvU9hnRJO5ZzTEzrYqZMdOl8lSkBTPL0ilD671eGHf/vaOW9n2W5R24voku1VndvUVd99E@8sde8A8xJE@2QkrSyhdFBrHDn418BF47VnsJkxHovrMMDqqjOMbjVpasDnK5oVi4Y/HGYGLB48RdaW6yn6AUZE1DynwEsMmnj6bXQ6yIMXV5JcXGktiTH4DLLwXZShA0Gk7Q8 "C# (Visual C# Interactive Compiler) – Try It Online")
[Answer]
# [J](http://jsoftware.com/), 57/60 bytes
```
0(](>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~]
```
[Try it online!](https://tio.run/##JcUxCoAwDADArwSFkAwNrYhDwH5EWgcpqIvtLv16HLzlbrO2qqdEUbNSwCIViiRXV6Wxk9NXGAfFyHgJRuWsO/9vPVk5zgcjNAgwQfAQFpi9fQ "J – Try It Online")
The linked version adds 3 bytes for a total of 60 in order to save as a function that the footer can call.
In the REPL, this is avoided by calling directly:
```
   0(](>:^:(1 e.q e.]-q=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~] 1 2 10 16 40
21 32 1031 1061 1103
```
## Explanation
The general structure is that of this technique from an [answer](https://codegolf.stackexchange.com/a/91176/87770) by [Miles](https://codegolf.stackexchange.com/users/6710/miles):
```
(s(]f)^:[~]) n
          ]  Gets n
 s           The first value in the sequence
         ~   Commute the argument order, n is LHS and s is RHS
        [    Gets n
      ^:     Nest n times with an initial argument s
  (]f)         Compute f s
         Returns (f^n) s
```
This saved a few bytes over my original looping technique, but since the core function is my first attempt at writing J, there is likely still a lot that can be improved.
```
0(](>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~]
0(]                                                 ^:[~] NB. Zero as the first term switches to one-indexing and saves a byte.
   (>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)      NB. Monolithic step function.
                                                 >:       NB. Increment to skip current value.
   (>:^: <predicate>                        ^:_)          NB. Increment current value as long as predicate holds.
                   p=:(#~(-:|.)&":&>)&i.&>:               NB. Reused: get palindromes in range [0,current value].
                       #~(-:|.)&":&>                      NB. Coerce to strings keeping those that match their reverse.
                 ]-p                                      NB. Subtract all palindromes in range [0,current value] from current value.
    >:^:(1&e.p e.]-p                                      NB. Increment if at least one of these differences is itself a palindrome.
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~15~~ 12 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
°ÝDʒÂQ}ãOKIè
```
-3 bytes thanks to *@Grimy*.
0-indexed.  
Very slow, so times out for most test cases.
[Try it online](https://tio.run/##AR0A4v9vc2FiaWX//8Kww51EypLDglF9w6NPS0nDqP//Mw) or [verify the first few cases by removing the `Iè`](https://tio.run/##yy9OTMpM/f//0IbDc11OTTrcFFh7eLG/9///xgA).
**Much faster previous 15 byter version:**
```
µNÐLʒÂQ}-ʒÂQ}g_
```
1-indexed.
[Try it online](https://tio.run/##yy9OTMpM/f//0Fa/wxN8Tk063BRYqwuh0uP//zcGAA) or [output the first \$n\$ values](https://tio.run/##yy9OTMpM/f//0Fa/wxN8Tk063BRYqwuh0uMzdQ7t@f/fEgA).
**Explanation:**
```
°Ý              # Create a list in the range [0, 10**input]
  D             # Duplicate this list
   ʒÂQ}         # Filter it to only keep palindromes
       ã        # Take the cartesian product with itself to create all possible pairs
        O       # Sum each pair
         K      # Remove all of these sums from the list we duplicated
          Iè    # Index the input-integer into it
                # (after which the result is output implicitly)
µ               # Loop until the counter variable is equal to the (implicit) input-integer
 NÐ             #  Push the loop-index three times
   L            #  Create a list in the range [1, N] with the last copy
    ʒÂQ}        #  Filter it to only keep palindromes
        -       #  Subtract each from N
         ʒÂQ}   #  Filter it again by palindromes
             g_ #  Check if the list is empty
                #   (and if it's truthy: increase the counter variable by 1 implicitly)
                # (after the loop: output the loop-index we triplicated implicitly as result)
```
[Answer]
# [Red](http://www.red-lang.org), 142 bytes
```
func[n][i: 1 until[i: i + 1 r: on repeat k i[if all[(to""k)= reverse
to""k(s: to""i - k)= reverse copy s][r: off break]]if r[n: n - 1]n < 1]i]
```
[Try it online!](https://tio.run/##TU27CsMwENvzFcJTSik0QxfT/kTX44Y0seFwuISLE@jXu06H0kUPJCQLY3mGkbiJvsRNB1Im8eiwaZbpkIJzteYxKywsoc9IEJKIfpqozbNz6fSo0R5sDc3Xt6vHIQQX/IUY5uWNlelYixEvC31irlNG6qG13bHiXlG4/M5uVxAWE82VE5x3iJUZXD4 "Red – Try It Online")
Returns n-th term, 1-indexed
[Answer]
# [Python 3](https://docs.python.org/3/), 107 bytes
```
p=lambda n:str(n)!=str(n)[::-1]
def f(n):
 m=1
 while n:m+=1;n-=all(p(k)+p(m-k)for k in range(m))
 return m
```
[Try it online!](https://tio.run/##PU7LboMwELz7K6a5xBZQxVDl4MpfkubggkkQ2FjGUVtZfDu1i9LTzs7OY91PuM@22TYnJ2U@OwUrluCpZS9ynxchKn4lne7Rp1UQGMkJvu7DpJPYFJK/20qqaaKOjqxw1FQj62ePEYOFV/amqWGMwOvw8BZma9WiF0hEAi5qXhLUoqnT4CfBT00m@Dmhc0ZviUtkQishOTa7S@hvp9ugu9zxl/c6BG0Wmh@EasNDTamhp/mWuuH8YAPtD/FYFcfL0y3lLr2uiFm5CnyE/@j4RGuJ2xwQd/F6YNsv "Python 3 – Try It Online")
Inverting the palindrome checking saved 2 bytes :)
For reference the straight forward positive check (109 bytes):
```
p=lambda n:str(n)==str(n)[::-1]
def f(n):
 m=1
 while n:m+=1;n-=1-any(p(k)*p(m-k)for k in range(m))
 return m
```
[Answer]
# APL(NARS), 486 bytes
```
r←f w;p;i;c;P;m;j
p←{k≡⌽k←⍕⍵}⋄i←c←0⋄P←r←⍬
:while c<w
    i+←1
    :if   p i⋄P←P,i⋄:continue⋄:endif
    m←≢P⋄j←1
    :while j≤m
         :if 1=p i-j⊃P⋄:leave⋄:endif
         j+←1
    :endwhile
    :if j=m+1⋄c+←1⋄r←i⋄:endif
:endwhile
```
What is the word for break the loop? It seems it is ":leave", right?
`{k≡⌽k←⍕⍵}` in p is the test for palindrome.
This above function in the loop store all the palindrome found in the set P,
if for some element w of P is such that i-w is in P too
this means that the i is not right and we have increment i. Results:
```
  f 1
21
  f 2
32
  f 10
1031
  f 16
1061
  f 40
1103
  f 1000
4966
  f 1500
7536
```
]