Every positive integer can be expressed as the sum of at most three palindromic positive integers in any base b≥5.   Cilleruelo et al., 2017

A positive integer is palindromic in a given base if its representation in that base, without leading zeros, reads the same backwards. In the following, only base b=10 will be considered.

The decomposition as a sum of palindromic numbers is not unique. For example, 5 can be expressed directly as 5, or as the sum of 2, 3. Similarly, 132 can be decomposed as 44, 44, 44 or as 121, 11.

The challenge

Given a positive integer, produce its sum decomposition into three or fewer positive integers that are palindromic in base 10.

Additional rules

  • The algorithm used should work for arbitrarily large inputs. However, it is acceptable if the program is limited by memory, time or data type restrictions.

  • Input and output can be taken by any reasonable means. Input and output format is flexible as usual.

  • You can choose to produce one or more valid decompositions for each input, as long as the output format is unambiguous.

  • Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

  • Shortest code in bytes wins.


Since an input can have many decompositions, these are examples rather than test cases. Each decomposition is shown on a different line.

Input  ->  Output

5     ->   5
           2, 3

15    ->   1, 3, 11
           9, 6

21    ->   11, 9, 1
           7, 7, 7

42    ->   22, 11, 9
           2, 7, 33

132   ->   44, 44, 44
           121, 11

345   ->   202, 44, 99
           2, 343

1022  ->   989, 33
           999, 22, 1

9265  ->   9229, 33, 3
           8338, 828, 99
  • 33
    \$\begingroup\$ mmm, pun in the title \$\endgroup\$ – Erik the Outgolfer Oct 23 '17 at 15:54
  • \$\begingroup\$ I wonder: is there any integer that must be composed into two palindromes? This would make a nice test case (if not, hey, golfers can use this fact and only check k=1 and k=3.) \$\endgroup\$ – Lynn Oct 23 '17 at 20:55
  • \$\begingroup\$ @Lynn Seems "unlikely", as there turn out to be quite a few decompositions for each input. But as we know, intuition in maths can be so misleading... \$\endgroup\$ – Luis Mendo Oct 23 '17 at 21:07
  • 1
    \$\begingroup\$ @Lynn If you're allowing k=1 (as in the original number is already a palindrome), that means you're assuming the other 2 numbers are both 0. So if 0 is acceptable as one of the numbers, any number which must be done with k=2 would also work for k=3 if one of the three numbers is 0. \$\endgroup\$ – Darrel Hoffman Oct 24 '17 at 15:03
  • \$\begingroup\$ I don't think there's any numbers that can ONLY be expressed as a sum of 2. Therefore, you can just cover the 3 and 1 case and ignore 2. \$\endgroup\$ – Magic Octopus Urn Oct 25 '17 at 18:44

23 Answers 23


Brachylog, 7 bytes


Try it online!

Surprisingly not that slow.


(?)~+  .          Output is equal to the Input when summed
     ℕᵐ.          Each element of the Output is a positive integer
       .↔ᵐ(.)     When reversing each element of the Output, we get the Output
  • 2
    \$\begingroup\$ What's with the random .'s in the explanation, and the (.)? Don't really know Brachylog. \$\endgroup\$ – Magic Octopus Urn Oct 24 '17 at 18:09
  • 3
    \$\begingroup\$ @MagicOctopusUrn . is the output variable. ~+, ℕᵐ, and ↔ᵐ are predicates which have a left and right variable. The duplication of those . simply indicates that the output is involved directly in each of those 3 predicate calls. The final (.) is here to display that the output variable is implicitely the last variable of the program. Therefore, the last stated relationship is really .↔ᵐ. which means "mapping reverse on the output results in the output". \$\endgroup\$ – Fatalize Oct 25 '17 at 6:26
  • \$\begingroup\$ Very good at last the input could be >10000 \$\endgroup\$ – RosLuP Nov 20 '17 at 12:59

Python 2, 82 79 bytes

f=lambda n:min([f(n-k)+[k]for k in range(1,n+1)if`k`==`k`[::-1]]or[[]],key=len)

Try it online!


Jelly, 12 10 9 8 bytes


Try it online!

How it works

ŒṗDfU$ṪḌ  Main link. Argument: n (integer)

Œṗ        Find all integer partitions of n.
  D       Convert each integer in each partition to base 10.
     $    Combine the two links to the left into a chain.
    U     Upend; reverse all arrays of decimal digits.
   f      Filter the original array by the upended one.
      Ṫ   Take the last element of the filtered array.
          This selects  the lexicographically smallest decomposition of those with
          the minimal amount of palindromes.
       Ḍ  Undecimal; convert all arrays of decimal digits to integers.
  • 5
    \$\begingroup\$ I just wanted to submit a solution with ~140 bytes, then I see 8 bytes and I'm like: "Nope, not gonna post mine". \$\endgroup\$ – Y U NO WORK Oct 24 '17 at 8:05
  • 15
    \$\begingroup\$ Comparing scores across languages is pretty much meaningless. I've posted a Python answer myself, not because it has a chance to beat this answer, but because it's the shortest Python answer I can think of. \$\endgroup\$ – Dennis Oct 24 '17 at 12:23

Python 2, 117 bytes

def f(n):p=[x for x in range(n+1)if`x`==`x`[::-1]];print[filter(None,[a,b,n-a-b])for a in p for b in p if n-a-b in p]

Try it online!

Prints a list of lists, each of which is a solution. Rod saved 9 bytes.

  • \$\begingroup\$ -9 bytes switching to function, replacing c with subtractions and using filter \$\endgroup\$ – Rod Oct 23 '17 at 17:24
  • 1
    \$\begingroup\$ @Rod Thanks! filter(None hit me as well while I was making dinner, haha. c → n-a-b is cool :) \$\endgroup\$ – Lynn Oct 23 '17 at 20:52

JavaScript (ES6), 115 ... 84 83 bytes

Always returns a three-element array, where unused entries are padded with zeros.


Test cases




R, 126 bytes 145 bytes

Thanks to Giuseppe for golfing off 19 bytes


Try it online!


R does not have a native way to reverse strings and many default string operations don't work on numbers. So first we convert the series of positive integers (plus 0) to characters.

Next we produce a vector of 0 and all palindromes. The string reversal requires splitting each number up by characters, reversing the order of the vector and pasting them back together with no gap.

Next I want to check all groups of three (here's where the 0s are important), luckily R has a built in combination function which returns a matrix, each column in a combination.

I apply the colSums function to the matrix and keep only the elements which equal the supplied target.

Finally, because there are two 0s, any set of two positive integers will be duplicated so I use a unique function on the columns.

The output is a matrix where each column is a set of positive, pallindromic integers that sum to the target value. It is lazy and returns 0's when fewer than 3 elements are used.

  • 1
    \$\begingroup\$ 128 bytes. +1, though, nice use of Map to generate palindromes! \$\endgroup\$ – Giuseppe Nov 21 '17 at 20:40
  • \$\begingroup\$ oops, found a 126 byter \$\endgroup\$ – Giuseppe Nov 21 '17 at 20:41

Jelly, 14 bytes


Try it online!

Very, very inefficient.

  • \$\begingroup\$ Seems too much slow, even if the target is code length, for me it is not only the length \$\endgroup\$ – RosLuP Nov 20 '17 at 13:23
  • \$\begingroup\$ @RosLuP Here you don't aim to keep the code efficient, here you aim to shorten the code as much as possible. It has to work in theory, not necessarily in practice, since this is a code-golf challenge, not a code-golf restricted-complexity or code-golf restricted-time challenge. \$\endgroup\$ – Erik the Outgolfer Nov 20 '17 at 13:47

Jelly, 17 bytes


Try it online!

-6 bytes thanks to HyperNeutrino.

Outputs all ways. However the output consists of some duplicates.

  • 1
    \$\begingroup\$ There's an is palindrome builtin lol \$\endgroup\$ – HyperNeutrino Oct 23 '17 at 16:18
  • \$\begingroup\$ Also, if you use normal (raised) range, you can remove your last 4 bytes \$\endgroup\$ – HyperNeutrino Oct 23 '17 at 16:18
  • \$\begingroup\$ 15 bytes \$\endgroup\$ – caird coinheringaahing Oct 23 '17 at 23:42
  • \$\begingroup\$ @cairdcoinheringaahing Still can beat neither Dennis nor Erik. Anyway am I going to decrypt truncated Deflate-compressed Base64-encoded URL? \$\endgroup\$ – user202729 Oct 24 '17 at 0:07
  • \$\begingroup\$ @user202729 Huh, must not have copied the link correctly. The code was RŒḂÐfṗ3R¤YS⁼¥Ðf \$\endgroup\$ – caird coinheringaahing Oct 24 '17 at 0:54

Ohm v2, 13 12 10 bytes


Try it online!


Mathematica, 49 bytes


Try it online!

returns all solutions


  • \$\begingroup\$ #~IntegerPartitions~3~Select~AllTrue@PalindromeQ&, I think? \$\endgroup\$ – Martin Ender Oct 24 '17 at 7:00

Haskell, 90 86 79 bytes

-7 bytes thanks to Laikoni!

h n=[f(>0)t|t<-mapM(\_->f(((==)<*>reverse).show)[0..n])"123",sum t==n]

Try it online!

Returns a list of all solutions with some duplication.

  • \$\begingroup\$ 79 bytes with mapM and declaring f=filter: Try it online! \$\endgroup\$ – Laikoni Oct 23 '17 at 19:38

Java (OpenJDK 8), 185 bytes

n->{for(int i=0,j=n,k;++i<=--j;)if(p(i))for(k=0;k<=j-k;k++)if(p(k)&p(j-k))return new int[]{j-k,k,i};return n;}
boolean p(int n){return(""+n).equals(""+new StringBuffer(""+n).reverse());}

Try it online!

Remove 1 byte from TIO to get the correct amount because the submission doesn't contain the ; after the lambda.

  • \$\begingroup\$ This in my opinion it is better than all one other solution posted until now \$\endgroup\$ – RosLuP Nov 20 '17 at 13:10
  • \$\begingroup\$ @RosLuP Why is that, if I may ask? \$\endgroup\$ – Olivier Grégoire Nov 20 '17 at 14:09
  • \$\begingroup\$ Because at last give answers for input > 500000 (if I remember well) \$\endgroup\$ – RosLuP Nov 20 '17 at 18:29
  • \$\begingroup\$ Suggest i++<--j instead of ++i<=--j \$\endgroup\$ – ceilingcat May 9 '19 at 23:18

Proton, 117 bytes

a=>filter(l=>all(p==p[by-1]for p:map(str,l)),(k=[[i,a-i]for i:1..a-1])+sum([[[i,q,j-q]for q:1..j-1]for i,j:k],[]))[0]

Try it online!

Outputs a solution

  • \$\begingroup\$ 920 as input not return the output in 1 min in tio... I not speak of 364757698688 but only 920 \$\endgroup\$ – RosLuP Nov 20 '17 at 13:20
  • 1
    \$\begingroup\$ @RosLuP That doesn't matter. Efficiency is not an important thing in code-golf. It will theoretically work for all sizes of input so that doesn't matter; given enough time, it will give the correct output for 920. \$\endgroup\$ – HyperNeutrino Nov 20 '17 at 13:29

Pyth,  16 12  10 bytes


Try it here!

How it works

ef_I#`MT./  ~ Full program.

        ./  ~ Integer Partitions.
 f          ~ Filter with a variable T.
     `MT    ~ Map each element of T to a string representation.
    #       ~ Filter.
  _I        ~ Is palindrome? (i.e Invariant over reverse?)
e           ~ Get last element.

05AB1E, 17 bytes


Try it online!

Outputs the result in three lists as follows:

  • Palindromic lists of length 1 (the original number IFF it's palindromic).

  • Palindromic lists of length 2.

  • Palindromic lists of length 3.


Axiom, 900 bytes

R(x)==>return x;p(r,a)==(n:=#(a::String);if r<0 then(a=0=>R a;n=1 or a=10^(n-1)=>R(a-1);a=10^(n-1)+1=>R(a-2));if r>0 then(n=1 and a<9=>R(a+1);a=10^n-1=>R(a+2));r=0 and n=1=>1;v:=a quo 10^(n quo 2);repeat(c:=v;w:=(n rem 2>0=>v quo 10;v);repeat(c:=10*c+w rem 10;w:=w quo 10;w=0=>break);r<0=>(c<a=>R c;v:=v-1);r>0=>(c>a=>R c;v:=v+1);R(c=a=>1;0));c)
b:List INT:=[];o:INT:=0
f(a:NNI):List INT==(free b,o;o:=p(-1,o);w:=0;c:=#b;if c>0 then w:=b.1;e:=a-o;e>10000000=>R[];if w<e then repeat(w:=p(1,w);w>e=>break;b:=cons(w,b));g:List INT:=[];for i in #b..1 by-1 repeat(b.i>e=>break;g:=cons(b.i,g));if o>e then g:=cons(o,g);n:=#g;for i in 1..n repeat(x:=g.i;x=a=>R[x];3*x<a=>break;for j in i..n repeat(y:=g.j;t:=x+y;t>a=>iterate;t=a=>R[x,y];t+y<a=>break;for k in j..n repeat(z:=t+g.k;z=a=>R[x,y,g.k];z<a=>break)));[])
D(a:NNI):List INT==(free o;p(0,a)=1=>[a];o:=a;for j in 1..10 repeat(t:=f(a);#t>0=>R t);[])

test code

--Lista random di n elmenti, casuali compresi tra "a" e "b"
randList(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b =>r
    for i in 1..n repeat

   [[i,D(i)] for i in a]

If this code has to decompose the number X in 1,2,3 palindrome, what this code does, it is try near palindrome N < X and decompose X-N in 2 palindrome; if this decomposition of X-N has success return 3 palindrome found; if it fail, it try the prev palindrome G < N < X and try decompose X-G in 2 palindrome etc. Ungolf code (but it is possible some bug)

 R(x)==>return x

-- se 'r'=0 ritorna 1 se 'a' e' palindrome altrimenti ritorna 0
-- se 'r'>0 ritorna la prossima palindrome >'a'
-- se 'r'<0 ritorna la prossima palindrome <'a'
p(r,a)==(n:=#(a::String);if r<0 then(a=0=>R a;n=1 or a=10^(n-1)=>R(a-1);a=10^(n-1)+1=>R(a-2));if r>0 then(n=1 and a<9=>R(a+1);a=10^n-1=>R(a+2));r=0 and n=1=>1;v:=a quo 10^(n quo 2);repeat(c:=v;w:=(n rem 2>0=>v quo 10;v);repeat(c:=10*c+w rem 10;w:=w quo 10;w=0=>break);r<0=>(c<a=>R c;v:=v-1);r>0=>(c>a=>R c;v:=v+1);R(c=a=>1;0));c)

b:List INT:=[]   -- the list of palindrome
o:INT:=0         -- the start value for search the first is a

--Decompose 'a' in 1 or 2 or 3 palindrome beginning with prev palindrome of o
--if error or fail return []
f(a:NNI):List INT==
    free b,o
    -- aggiustamento di o, come palindrome piu' piccola di o
    -- aggiustamento di b come l'insieme delle palindromi tra 1..a-o compresa
    if c>0 then w:=b.1 --in w la massima palindrome presente in b
    e>10000000=>R[]   --impongo che la palindrome massima e' 10000000-1
    if w<e then       --se w<a-o aggiungere a b tutte le palindromi tra w+1..a-o
                      -- g e' l'insieme dei b palindromi tra 1..a-o,o
    g:List INT:=[];for i in #b..1 by-1 repeat(b.i>e=>break;g:=cons(b.i,g))
    if o>e then g:=cons(o,g)
    for i in 1..n repeat
        x=a  =>R[x]
        for j in i..n repeat
           t>a   =>iterate
           t=a   =>R[x,y]
           t+y<a =>break
           for k in j..n repeat
                z=a =>R[x,y,g.k]
                z<a =>break

--Decompose 'a' in 1 or 2 or 3 palindrome
--if error or fail return []
dPal(a:NNI):List INT==
   free o
   o:=a                  -- at start it is o=a
   for j in 1..10 repeat -- try 10 start values only
        #t>0=>R t


(7) -> [[i,D(i)] for i in [5,15,21,42,132,345,1022,9265] ]
   [[5,[5]], [15,[11,4]], [21,[11,9,1]], [42,[33,9]], [132,[131,1]],
    [345,[343,2]], [1022,[999,22,1]], [9265,[9229,33,3]]]
                                                      Type: List List Any
                                   Time: 0.02 (IN) + 0.02 (OT) = 0.03 sec
(8) -> test()
    [1885502599457,[1885502055881,542245,1331]], [10995589034484,[]],
                                                      Type: List List Any
      Time: 0.25 (IN) + 115.17 (EV) + 0.13 (OT) + 28.83 (GC) = 144.38 sec

Java (OpenJDK 8), 605 bytes

Prints dupes but they aren't banned afaik

a->{int i=0,j,k,r[]=new int[a-1];for(;i<a-1;r[i]=++i);for(i=0;i<a-1;i++){if(r[i]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse()))System.out.println(r[i]);for(j=0;j<a-1;j++){if(r[i]+r[j]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse())&(""+r[j]).equals(""+new StringBuffer(""+r[j]).reverse()))System.out.println(r[i]+" "+r[j]);for(k=0;k<a-1;k++)if(r[i]+r[j]+r[k]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse())&(""+r[j]).equals(""+new StringBuffer(""+r[j]).reverse())&(""+r[k]).equals(""+new StringBuffer(""+r[k]).reverse()))System.out.println(r[i]+" "+r[j]+" "+r[k]);}}}

Try it online!


APL (Dyalog), 51 bytes


Try it online!


05AB1E, 8 bytes


Try it online!


Ŝ          # integer partitions of the input
  R         # reversed (puts the shortest ones first)
   .Δ       # find the first one that...
     D Q    # is equal to...
      í     # itself with each element reversed

Perl 6, 51 bytes

{first *.sum==$_,[X] 3 Rxx grep {$_ eq.flip},1..$_}

Try it online!

  • grep { $_ eq .flip }, 1 .. $_ produces a list of all palindromic numbers from 1 to the input number.
  • 3 Rxx replicates that list three times.
  • [X] reduces that list-of-lists with the cross-product operator X, resulting in a list of all 3-tuples of palindrominc numbers from 1 to the input number.
  • first *.sum == $_ finds the first such 3-tuple that sums to the input number.
  • \$\begingroup\$ You can save a byte by not reversing the xx 3. \$\endgroup\$ – Jo King May 9 '19 at 22:41

Python 3, 106 bytes

lambda n:[(a,b,n-a-b)for a in range(n)for b in range(n)if all(f'{x}'==f'{x}'[::-1]for x in(a,b,n-a-b))][0]

Try it online!

In the TIO link I used a faster (but 1 byte longer version) that takes the first valid result as a generator, rather than building the entire list of possible combinations and taking the first.


Ruby, 84 bytes

Builds a list of all possible combinations of 3 palindromes from 0 to n, finds the first one whose sum matches, then prunes the zeroes.


Try it online!


Add++, 62 bytes


Try it online!

~50 bytes golfed while writing up an explanation. Defines a lambda function which returns a list of lists containing the solutions.

How it works

The last line contains the main function and works by generating all sublists of lengths \$1, 2\$ and \$3\$ containing only palindromic numbers between \$1\$ and \$n\$, then discarding those whose sum does not match \$n\$.

The first section, and helper function, generates the range \$1, 2, ..., n\$, and filters out any number that isn't a palindrome. The helper function g is a palindrome checker and RÞg filters the range on g. We then save this filtered list as \$A\$ for later.

The next section can be split into three further parts:


The first part takes the array \$A\$ ([1 2 3 4 ...]) and wraps each element in an array, yielding [[1] [2] [3] [4] ... ]. We then push \$A\$ twice and run the table quick over the function k:


This function does basically nothing. It receives two arguments and wraps them in an array. However, the table quick, is the magic trick here. It takes two lists and generates every pair of elements between those two lists. So [1 2 3] and [4 5 6] generates [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. It then takes its functional argument (in this case k) and runs that function over each pair, which, in this case, simply returns the pairs as is.

After the first two parts are completed, the stack contains a list of wrapped palindromic integers (all palindromic numbers of list length 1), and a list of pairs of numbers that pair each palindromic number with every other palindromic number. The third section pushes the second array again, then pushes \$A\$, and runs the table function over the two arrays. This almost generates the list of triples we need, but annoyingly, each triple has a nested pair. To remove this, we run €bF over the list which flattens each sublist. Finally, we concatenate the three lists to form a list of all required sublists.

We've generated all sublists of length \$1, 2\$ and \$3\$ containing palindromic numbers, so all we need to do now is filter those whose sum is not the input. So, we push \$n\$ again and filter each sublist of l, which returns whether the sum of the array is equal to \$n\$. Finally, we return the list of lists.


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.