Two palindromes are not enough

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

• Unrelated String: Isn't infinite output also a standard option for sequences?
• Robin Ryder: @UnrelatedString Yes, I'll allow that as well.
• Luis Mendo: Related
• val - disappointed in SE: @Abigail Given positive integer n, print n-th member of sequence OEIS An? Sounds promising...
• agtoever: @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.

Answer 1

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

• tsh: i=>eval("for(n=k=1;k=(s=[...k+[n-k]+k])+''!=s.reverse()?k-1||i--&&++n:++n;);n") 79 bytes
• Luvexina: Instead of i=>eval("..."), ES6 allows you to use i=>eval`...`, saving 2 bytes
• Luvexina: Also, if no return is specified, eval defaults to the last expression evaluated, so you can remove the ;n at the end.
• Arnauld: @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.

Answer 2

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

Answer 3

Jelly, 11 bytes

5ŻŒḂ€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.

• Jonathan Allan: Ah, beat me too it - first n terms saves 1 byte (I went for STDIN and ŻŒḂ€aṚ$Ṁ¬µ#
• Erik the Outgolfer: @JonathanAllan Oh LOL didn't expect that. Anyway, somebody beat us both. :D
• Robin Ryder: 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.
• Erik the Outgolfer: @RobinRyder Yes, that's also possible. My proof is a generalization that contains this case as well (\11ドル\$ is a palindrome).

Answer 4

Retina, (削除) 135 (削除ここまで) 102 bytes

K`0
"$+"{0L$`\d+
*__
L$`
<$.'>$.`>
/<((.)*.?(?<-2>2円)*(?(2)$)>){2}/{0L$`\d+
*__
))L$`
<$.'>$.`>
0L`\d+

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 5

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!

Answer 6

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.

• Nahuel Fouilleul: small improvement, -3bytes, using while instead of redo
• Xcali: And took one more off of that by eliminating the + after the while.

Answer 7

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.

• Giuseppe: 111 bytes just by rearranging a couple things.

Answer 8

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!

Answer 9

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.

• miles: That's an old format of mine, combining other tricks I learned since then produces a 41 char solution: 1&(_:1&((e.((*&(-:|.)&":"0>:)&i.-))+])+)*

Answer 10

05AB1E, (削除) 15 (削除ここまで) 12 bytes

°ÝDʒÂQ}ãOKIè

-3 bytes thanks to @Grimy.

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

Try it online or verify the first few cases by removing the Iè.

Much faster previous 15 byter version:

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

1-indexed.

Try it online or output the first \$n\$ values.

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)

• Grimmy: 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.
• Kevin Cruijssen: @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: @Grimy Hmm, I guess a straight-forward fix is changing the 1-based list L to 0-based.. :)

Answer 11

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

Answer 12

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

Answer 13

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