Yo boy, must it sum

Question

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.

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

Answer 1

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

Answer 2

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!

Answer 3

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.

Answer 4

Jelly, 12 10 9 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.

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

Jelly, 14 bytes

L<4aŒḂ€Ạ
ŒṗÇÐf

Try it online!

Very, very inefficient.

Answer 9

Ohm v2, 13 12 10 bytes

#Dð*3ç⁇Σ³E

Try it online!

Answer 10

Mathematica, 49 bytes

#~IntegerPartitions~3~Select~AllTrue@PalindromeQ&

Try it online!

returns all solutions

-2~MartinEnder~bytes

Answer 11

Haskell, 90 86 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.

Answer 12

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.

Answer 13

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

Answer 14

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.

Answer 15

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.

Answer 16

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

Answer 17

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!

Answer 18

APL (Dyalog), 51 bytes

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

Try it online!

Answer 19

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

Answer 20

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.

Answer 21

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.

Answer 22

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!

Answer 23

Add++, 62 bytes

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.