# Yo boy, must it sum

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.

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

## Examples

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

• mmm, pun in the title Oct 23, 2017 at 15:54
• 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.)
– Lynn
Oct 23, 2017 at 20:55
• @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... Oct 23, 2017 at 21:07
• @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. Oct 24, 2017 at 15:03
• 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. Oct 25, 2017 at 18:44

# Brachylog, 7 bytes

~+ℕᵐ.↔ᵐ


Try it online!

Surprisingly not that slow.

### Explanation

(?)~+  .          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

• What's with the random .'s in the explanation, and the (.)? Don't really know Brachylog. Oct 24, 2017 at 18:09
• @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". Oct 25, 2017 at 6:26
• Very good at last the input could be >10000
– user58988
Nov 20, 2017 at 12:59

# Python 2, 82 79 bytes

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


Try it online!

# Jelly, 12109 8 bytes

ŒṗDfU$ṪḌ  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.  • I just wanted to submit a solution with ~140 bytes, then I see 8 bytes and I'm like: "Nope, not gonna post mine". Oct 24, 2017 at 8:05 • 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. Oct 24, 2017 at 12:23 # Python 2, 117 bytes def f(n):p=[x for x in range(n+1)ifx==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. • -9 bytes switching to function, replacing c with subtractions and using filter – Rod Oct 23, 2017 at 17:24 • @Rod Thanks! filter(None hit me as well while I was making dinner, haha. c → n-a-b is cool :) – Lynn Oct 23, 2017 at 20:52 # JavaScript (ES6), 115 ... 84 83 bytes Always returns a three-element array, where unused entries are padded with zeros. f=(n,b=a=0)=>(r=[b,a%=n,n-a-b]).some(a=>a-[...a+''].reverse().join)?f(n,b+!a++):r  ### Test cases f=(n,b=a=0)=>(r=[b,a%=n,n-a-b]).some(a=>a-[...a+''].reverse().join)?f(n,b+!a++):r console.log(JSON.stringify(f(5))) console.log(JSON.stringify(f(15))) console.log(JSON.stringify(f(21))) console.log(JSON.stringify(f(42))) console.log(JSON.stringify(f(132))) console.log(JSON.stringify(f(345))) console.log(JSON.stringify(f(1022))) console.log(JSON.stringify(f(9265))) # R, 126 bytes 145 bytes Thanks to Giuseppe for golfing off 19 bytes function(n){a=paste(y<-0:n) x=combn(c(0,y[a==Map(paste,Map(rev,strsplit(a,"")),collapse="")]),3) unique(x[,colSums(x)==n],,2)}  Try it online! Explanation 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. • 128 bytes. +1, though, nice use of Map to generate palindromes! Nov 21, 2017 at 20:40 • oops, found a 126 byter Nov 21, 2017 at 20:41 # Jelly, 14 bytes L<4aŒḂ€Ạ ŒṗÇÐf  Try it online! Very, very inefficient. • Seems too much slow, even if the target is code length, for me it is not only the length – user58988 Nov 20, 2017 at 13:23 • @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. Nov 20, 2017 at 13:47 # Jelly, 17 bytes RŒḂÐfṗ3R¤YS⁼³$$Ðf  Try it online! -6 bytes thanks to HyperNeutrino. Outputs all ways. However the output consists of some duplicates. • There's an is palindrome builtin lol Oct 23, 2017 at 16:18 • Also, if you use normal (raised) range, you can remove your last 4 bytes Oct 23, 2017 at 16:18 • 15 bytes Oct 23, 2017 at 23:42 • @cairdcoinheringaahing Still can beat neither Dennis nor Erik. Anyway am I going to decrypt truncated Deflate-compressed Base64-encoded URL? Oct 24, 2017 at 0:07 • @user202729 Huh, must not have copied the link correctly. The code was RŒḂÐfṗ3R¤YS⁼¥Ðf Oct 24, 2017 at 0:54 # Ohm v2, 1312 10 bytes #Dð*3ç⁇Σ³E  Try it online! # Mathematica, 49 bytes #~IntegerPartitions~3~Select~AllTrue@PalindromeQ&  Try it online! returns all solutions -2~MartinEnder~bytes • #~IntegerPartitions~3~Select~AllTrue@PalindromeQ&, I think? Oct 24, 2017 at 7:00 # Haskell, 9086 79 bytes -7 bytes thanks to Laikoni! f=filter 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. • 79 bytes with mapM and declaring f=filter: Try it online! Oct 23, 2017 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. • This in my opinion it is better than all one other solution posted until now – user58988 Nov 20, 2017 at 13:10 • @RosLuP Why is that, if I may ask? Nov 20, 2017 at 14:09 • Because at last give answers for input > 500000 (if I remember well) – user58988 Nov 20, 2017 at 18:29 • Suggest i++<--j instead of ++i<=--j May 9, 2019 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 • 920 as input not return the output in 1 min in tio... I not speak of 364757698688 but only 920 – user58988 Nov 20, 2017 at 13:20 • @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. Nov 20, 2017 at 13:29 # Pyth, 16 12 10 bytes ef_I#MT./  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 LʒÂQ}U4GXNãDO¹QÏ=  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 d:=1+b-a for i in 1..n repeat r:=concat(r,a+random(d)$INT)
r

test()==
a:=randList(20,1,12345678901234)
[[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
o:=p(-1,o)
-- aggiustamento di b come l'insieme delle palindromi tra 1..a-o compresa
w:=0;c:=#b
if c>0 then w:=b.1 --in w la massima palindrome presente in b
e:=a-o
output["e=",e,"w=",w,"o=",o,"#b=",#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
repeat(w:=p(1,w);w>e=>break;b:=cons(w,b))
-- 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)
--output["g=",g,b]
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
[]

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



results:

(7) -> [[i,D(i)] for i in [5,15,21,42,132,345,1022,9265] ]
(7)
[[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()
(8)
[[7497277417019,[7497276727947,624426,64646]],
[11535896626131,[11535888853511,7738377,34243]],
[2001104243257,[2001104011002,184481,47774]],
[3218562606454,[3218561658123,927729,20602]],
[6849377785598,[6849377739486,45254,858]],
[375391595873,[375391193573,324423,77877]],
[5358975936064,[5358975798535,136631,898]],
[7167932760123,[7167932397617,324423,38083]],
[11779002607051,[11779000097711,2420242,89098]],
[320101573620,[320101101023,472274,323]],
[5022244189542,[5022242422205,1766671,666]],
[5182865851215,[5182864682815,1158511,9889]],
[346627181013,[346626626643,485584,68786]],
[9697093443342,[9697092907969,443344,92029]],
[1885502599457,[1885502055881,542245,1331]], [10995589034484,[]],
[1089930852241,[1089930399801,375573,76867]],
[7614518487477,[7614518154167,246642,86668]],
[11859876865045,[11859866895811,9968699,535]],
[2309879870924,[2309879789032,81418,474]]]
Type: List List Any
Time: 0.25 (IN) + 115.17 (EV) + 0.13 (OT) + 28.83 (GC) = 144.38 sec


# 05AB1E, 8 bytes

ÅœR.ΔDíQ


Try it online!

Explanation:

Åœ          # 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


# Husk, 13 bytes

ḟo=⁰Σfo<4LṖİ↔


Try it online!

## Explanation

ḟo=⁰Σfo<4LṖİ↔
İ↔ all base 10 palindromes
Ṗ   power set
fo<4L    keep length<4 subsets
ḟo            first set which satisfies:
=⁰Σ         sum equals input

• @LuisMendo should be correct now, Dec 7, 2020 at 14:03

# 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

{w/⍨⍵=+/¨w←(,y∘.,z),,(z←,∘.,⍨y),y←,x/⍨(⌽≡⊢)¨⍕¨x←⍳⍵}


Try it online!

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

->n{a=(0..n).select{|x|x.to_s==x.to_s.reverse};a.product(a,a).find{|x|x.sum==n}-[0]}


Try it online!

# 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.
• You can save a byte by not reversing the xx 3.
– Jo King
May 9, 2019 at 22:41

D,g,@,BDdbR=
D,l,@@,$b+= D,k,@@*, L,RÞgdVBcB]Gd‽kdG‽k€bF++A$Þl


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:

BcB]
Gd‽k
dG‽k€bF


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:

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

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

# Lua, 334 bytes

m=math.floor function p(a)a=tostring(a)return a:reverse()==a end
s=io.read()function g(s) for i=s,1,-1 do if(p(m(i)))then
t=i for j=s-i,1,-1 do if (p(m(j)))then u=j for k=t-j,0,-1 do
if(p(m(k))and(k~=0)and((t+u+k)==tonumber(s)))then
print(m(t))print(m(u))print(m(k))return end end end end end end end
if(p(s))then print(s)else g(s)end
`

Try it online!