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
  • 28
    mmm, pun in the title – Erik the Outgolfer Oct 23 '17 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 '17 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... – Luis Mendo Oct 23 '17 at 21:07
  • 1
    @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. – Darrel Hoffman Oct 24 '17 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. – Magic Octopus Urn Oct 25 '17 at 18:44

18 Answers 18

up vote 16 down vote accepted

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
  • 2
    What's with the random .'s in the explanation, and the (.)? Don't really know Brachylog. – Magic Octopus Urn Oct 24 '17 at 18:09
  • 3
    @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". – Fatalize Oct 25 '17 at 6:26
  • Very good at last the input could be >10000 – 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

Œṗ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.
  • 5
    I just wanted to submit a solution with ~140 bytes, then I see 8 bytes and I'm like: "Nope, not gonna post mine". – Y U NO WORK Oct 24 '17 at 8:05
  • 15
    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. – 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.

  • -9 bytes switching to function, replacing c with subtractions and using filter – Rod Oct 23 '17 at 17:24
  • 1
    @Rod Thanks! filter(None hit me as well while I was making dinner, haha. c → n-a-b is cool :) – 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.

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.

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 – RosLuP Nov 20 '17 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. – Erik the Outgolfer Nov 20 '17 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.

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

Ohm v2, 13 12 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? – Martin Ender Oct 24 '17 at 7:00

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 – RosLuP Nov 20 '17 at 13:10
  • @RosLuP Why is that, if I may ask? – Olivier Grégoire Nov 20 '17 at 14:09
  • Because at last give answers for input > 500000 (if I remember well) – RosLuP Nov 20 '17 at 18:29

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 – RosLuP Nov 20 '17 at 13:20
  • 1
    @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. – HyperNeutrino Nov 20 '17 at 13:29

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.

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

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!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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