# Two palindromes are not enough

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 nth number which cannot be decomposed as the sum of 2 palindromes. This corresponds to OEIS 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 nth term, or the first n terms, or an infinite sequence

(As a sidenote: all integers can be decomposed 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.

• Isn't infinite output also a standard option for sequences? – Unrelated String Jun 27 '19 at 0:30
• @UnrelatedString Yes, I'll allow that as well. – Robin Ryder Jun 27 '19 at 6:26
• Related – Luis Mendo Jun 27 '19 at 7:02
• @Abigail Given positive integer n, print n-th member of sequence OEIS An? Sounds promising... – val is still with Monica Jun 27 '19 at 17:15
• @Nit let's define a new OEIS sequence as a(n) = the nth OEIS sequence that can be expressed in less characters than the most golfed Jelly function that generates that sequence. – agtoever Jun 29 '19 at 17:21

# 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!

### 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
}                            //

• i=>eval("for(n=k=1;k=(s=[...k+[n-k]+k])+''!=s.reverse()?k-1||i--&&++n:++n;);n") 79 bytes – tsh Jun 27 '19 at 6:26
• Instead of i=>eval("..."), ES6 allows you to use i=>eval..., saving 2 bytes – VFDan Jun 30 '19 at 2:51
• Also, if no return is specified, eval defaults to the last expression evaluated, so you can remove the ;n at the end. – VFDan Jun 30 '19 at 2:55
• @VFDan The back-tick trick doesn't work with eval() because it doesn't coerce its argument to a string. Removing ;n would lead to a syntax error and removing just n would cause the function to return undefined. – Arnauld Jun 30 '19 at 7:02

# Jelly,  16 10  9 bytes

-1 byte thanks to Erik the Outgolfer. Outputs the first $$\n\$$ terms.

2_ŒḂƇ⁺ṆƲ#


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. # Jelly, 11 bytes ⁵ŻŒḂ€aṚEƲ#  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. • Ah, beat me too it - first n terms saves 1 byte (I went for STDIN and ŻŒḂ€aṚṀ¬µ# – Jonathan Allan Jun 26 '19 at 23:11 • @JonathanAllan Oh LOL didn't expect that. Anyway, somebody beat us both. :D – Erik the Outgolfer Jun 26 '19 at 23:12 • For the proof, couldn't you just take the pair $(10, x-10)$, and use the fact that $10$ is not a palindrome? Then the proof is one line. – Robin Ryder Jun 27 '19 at 6:32 • @RobinRyder Yes, that's also possible. My proof is a generalization that contains this case as well ($11$ is a palindrome). – Erik the Outgolfer Jun 27 '19 at 9:06 # Retina, 135 102 bytes K0 "+"{0L\d+ *__ L <.'>.> /<((.)*.?(?<-2>\2)*(?(2))>){2}/{0L\d+ *__ ))L <.'>.> 0L\d+  Try it online! Too slow for n of 10 or more. Explanation: K0  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. ## Haskell, 6867 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! # Perl 5-MList::Util=any -p, 59 55 bytes -3 bytes thanks to @NahuelFouilleul ++\while(any{\-reverse(\-_)==reverse}0..$$||--\$_}{


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.

• small improvement, -3bytes, using while instead of redo – Nahuel Fouilleul Jun 27 '19 at 7:15
• And took one more off of that by eliminating the + after the while. – Xcali Jun 27 '19 at 16:30

# R, 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!

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, and is just incredibly clever to me.

r[!r%in%outer(p,p,'+')][n]reads a little inefficient to me.

• 111 bytes just by rearranging a couple things. – Giuseppe Jun 28 '19 at 14:00

# C# (Visual C# Interactive Compiler), 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!

# J, 57/60 bytes

0(](>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~]


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


# 05AB1E, 15 12 bytes

°ÝDʒÂQ}ãOKIè


-3 bytes thanks to @Grimy.

0-indexed.
Very slow, so times out for most test cases.

Much faster previous 15 byter version:

µNÐLʒÂQ}-ʒÂQ}g_


1-indexed.

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)

• 12: °LDʒÂQ}ãOKIè (there's probably a better upper bound than 10^x for speed). I guess ∞DʒÂQ}ãOK is technically a 9, but it times out before the first output. – Grimmy Jul 3 '19 at 11:32
• @Grimy Not sure if cartesian product works lazy-loaded on infinite lists. Anyway, as for the 12-byter, it's unfortunately incorrect. It does filter out integers that can be formed by summing 2 palindromes, but not integers that are palindromes themselves. Your sequence (without the trailing Iè) goes like: [1,21,32,43,54,65,76,87,98,111,131,141,151,...] but is supposed to go like [*,21,32,43,54,65,76,87,98,201,1031,1041,1051,1052,...] (the first 1/* can be ignored since we use 1-indexed input). – Kevin Cruijssen Jul 3 '19 at 11:45
• @Grimy Hmm, I guess a straight-forward fix is changing the 1-based list L to 0-based.. :) – Kevin Cruijssen Jul 3 '19 at 11:46

# Red, 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!

Returns n-th term, 1-indexed

# Python 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!

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


# 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