25
\$\begingroup\$

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.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Isn't infinite output also a standard option for sequences? \$\endgroup\$ – Unrelated String Jun 27 '19 at 0:30
  • \$\begingroup\$ @UnrelatedString Yes, I'll allow that as well. \$\endgroup\$ – Robin Ryder Jun 27 '19 at 6:26
  • \$\begingroup\$ Related \$\endgroup\$ – Luis Mendo Jun 27 '19 at 7:02
  • 2
    \$\begingroup\$ @Abigail Given positive integer n, print n-th member of sequence OEIS An? Sounds promising... \$\endgroup\$ – val is still with Monica Jun 27 '19 at 17:15
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – agtoever Jun 29 '19 at 17:21

13 Answers 13

13
\$\begingroup\$

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
}                            //
\$\endgroup\$
4
  • \$\begingroup\$ i=>eval("for(n=k=1;k=(s=[...k+[n-k]+k])+''!=s.reverse()?k-1||i--&&++n:++n;);n") 79 bytes \$\endgroup\$ – tsh Jun 27 '19 at 6:26
  • \$\begingroup\$ Instead of i=>eval("..."), ES6 allows you to use i=>eval`...`, saving 2 bytes \$\endgroup\$ – VFDan Jun 30 '19 at 2:51
  • \$\begingroup\$ Also, if no return is specified, eval defaults to the last expression evaluated, so you can remove the ;n at the end. \$\endgroup\$ – VFDan Jun 30 '19 at 2:55
  • \$\begingroup\$ @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. \$\endgroup\$ – Arnauld Jun 30 '19 at 7:02
12
\$\begingroup\$

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.

\$\endgroup\$
0
7
\$\begingroup\$

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.

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

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

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

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.

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

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!

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
1
\$\begingroup\$

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 .

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)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Grimmy Jul 3 '19 at 11:32
  • \$\begingroup\$ @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 ) 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). \$\endgroup\$ – Kevin Cruijssen Jul 3 '19 at 11:45
  • 1
    \$\begingroup\$ @Grimy Hmm, I guess a straight-forward fix is changing the 1-based list L to 0-based.. :) \$\endgroup\$ – Kevin Cruijssen Jul 3 '19 at 11:46
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.