Todo número inteiro positivo pode ser expresso como a soma de no máximo três números inteiros positivos palindrômicos em qualquer base b ≥5.   Cilleruelo et al., 2017

Um número inteiro positivo é palíndrico em uma determinada base se sua representação nessa base, sem zeros à esquerda, lê o mesmo para trás. A seguir, apenas a base b = 10 será considerada.

A decomposição como uma soma dos números palindrômicos não é única . Por exemplo, 5pode ser expresso diretamente como 5, ou como a soma de 2, 3. Da mesma forma, 132pode ser decomposto como 44, 44, 44ou como 121, 11.

O desafio

Dado um número inteiro positivo, produza sua decomposição de soma em três ou menos números inteiros positivos que são palíndricos na base 10.

Regras adicionais

• O algoritmo usado deve funcionar para entradas arbitrariamente grandes. No entanto, é aceitável se o programa estiver limitado por restrições de memória, hora ou tipo de dados.

• A entrada e a saída podem ser obtidas por qualquer meio razoável . O formato de entrada e saída é flexível, como de costume.

• Você pode optar por produzir uma ou mais decomposições válidas para cada entrada, desde que o formato de saída seja inequívoco.

• Programas ou funções são permitidos, em qualquer linguagem de programação . As brechas padrão são proibidas.

• O menor código em bytes vence.

Exemplos

Como uma entrada pode ter muitas decomposições, esses são exemplos e não casos de teste. Cada decomposição é mostrada em uma linha diferente.

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

Braquilog , 7 bytes

~+ℕᵐ.↔ᵐ

Experimente online!

Surpreendentemente, não é tão lento.

Explicação

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

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)

Experimente online!

Gelatina , 12 10 9 8 bytes

ŒṗDfU$ṪḌ

Experimente online!

Como funciona

Œṗ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.

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]

Experimente online!

Imprime uma lista de listas, cada uma das quais é uma solução. Rod salvou 9 bytes.

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

Sempre retorna uma matriz de três elementos, na qual entradas não utilizadas são preenchidas com zeros.

f=(n,b=a=0)=>(r=[b,a%=n,n-a-b]).some(a=>a-[...a+''].reverse().join``)?f(n,b+!a++):r

Casos de teste

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

Agradecimentos a Giuseppe por jogar fora 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)}

Experimente online!

Explicação

R não possui uma maneira nativa de reverter seqüências de caracteres e muitas operações de sequência padrão não funcionam com números. Então, primeiro convertemos a série de números inteiros positivos (mais 0) em caracteres.

Em seguida, produzimos um vetor 0 e todos os palíndromos. A reversão de string requer dividir cada número por caracteres, revertendo a ordem do vetor e colando-os novamente sem espaços.

Em seguida, quero verificar todos os grupos de três (aqui é onde os 0s são importantes). Felizmente, R possui uma função de combinação integrada que retorna uma matriz, cada coluna em uma combinação.

Aplico a colSumsfunção à matriz e mantenho apenas os elementos que são iguais ao alvo fornecido.

Finalmente, como existem dois 0s, qualquer conjunto de dois números inteiros positivos será duplicado, então eu uso uma função exclusiva nas colunas.

A saída é uma matriz em que cada coluna é um conjunto de números inteiros palindrômicos positivos que somam ao valor alvo. É lento e retorna 0 quando menos de 3 elementos são usados.

Gelatina , 14 bytes

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

Experimente online!

Muito, muito ineficiente.

Gelatina , 17 bytes

RŒḂÐfṗ3R¤YS⁼³$$Ðf

Experimente online!

-6 bytes graças ao HyperNeutrino.

Produz todas as formas. No entanto, a saída consiste em algumas duplicatas.

Ohm v2 , 13 12 10 bytes

#Dð*3ç⁇Σ³E

Experimente online!

Mathematica, 49 bytes

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

Experimente online!

retorna todas as soluções

-2 ~ MartinEnder ~ bytes

Haskell , 90 86 79 bytes

-7 bytes graças a Laikoni!

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

Experimente online!

Retorna uma lista de todas as soluções com alguma duplicação.

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());}

Experimente online!

Remova 1 byte do TIO para obter a quantia correta, pois o envio não contém o ;após o lambda.

Próton , 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]

Experimente online!

Produz uma solução

Pitão ,  16 12  10 bytes

ef_I#`MT./

Experimente aqui!

Como funciona

ef_I # `MT. / ~ Programa completo.

        ./ ~ Partições Inteiras.
 f ~ Filtre com uma variável T.
     `MT ~ Mapeie cada elemento de T para uma representação de string.
    # ~ Filtro.
  _I ~ É palíndromo? (ie Invariante ao contrário?)
e ~ Obtenha o último elemento.

05AB1E , 17 bytes

LʒÂQ}U4GXNãDO¹QÏ=

Experimente online!

Produz o resultado em três listas da seguinte maneira:

• Listas palindrômicas de comprimento 1 (o número original IFF é palindrômico).

• Listas palindrômicas de comprimento 2.

• Listas palindrômicas de comprimento 3.

Axioma, 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);[])

código de teste

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

Se esse código precisar decompor o número X no palíndromo 1,2,3, o que esse código faz, tente próximo ao palíndromo N <X e decomponha XN no palíndromo 2; se esta decomposição de XN tiver sucesso, retorne 3 palíndromo encontrado; se falhar, tente o palíndromo anterior G <N <X e tente decompor o XG em 2 palíndromo etc. Código Ungolf (mas é possível que haja algum 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
   []

resultados:

(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

Imprime enganos, mas eles não são proibidos

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]);}}}

Experimente online!

APL (Dyalog) , 51 bytes

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

Experimente online!

05AB1E , 8 bytes

ÅœR.ΔDíQ

Experimente online!

Explicação:

Ŝ          # 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..$_}

Experimente online!

• grep { $_ eq .flip }, 1 .. $_ produz uma lista de todos os números palíndricos de 1 ao número de entrada.
• 3 Rxx replica essa lista três vezes.
• [X]reduz essa lista de listas com o operador de produtos cruzados X, resultando em uma lista de todas as três tuplas de números de palindrominco de 1 para o número de entrada.
• first *.sum == $_ localiza a primeira dessas três tuplas que soma ao número de entrada.

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]

Experimente online!

No link TIO, usei uma versão mais rápida (mas com 1 byte de comprimento) que leva o primeiro resultado válido como gerador, em vez de criar a lista inteira de combinações possíveis e pegar a primeira.

Ruby , 84 bytes

Constrói uma lista de todas as combinações possíveis de 3 palíndromos de 0 a n, localiza o primeiro cuja soma corresponde e apaga os zeros.

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

Experimente online!

Adicionar ++ , 62 bytes

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

Experimente online!

~ 50 bytes jogavam golfe enquanto escrevia uma explicação. Define uma função lambda que retorna uma lista de listas contendo as soluções.

Como funciona

$1, 2$$3$$1$$n$$n$

$1, 2, ..., n$gRÞgg$A$

A próxima seção pode ser dividida em mais três partes:

BcB]
Gd‽k
dG‽k€bF

$A$[1 2 3 4 ...][[1] [2] [3] [4] ... ]$A$k

D,k,@@*,

Esta função basicamente não faz nada. Ele recebe dois argumentos e os agrupa em uma matriz. No entanto, a mesa rápida, ‽é o truque de mágica aqui. É preciso duas listas e gera cada par de elementos entre essas duas listas. Então [1 2 3]e [4 5 6]gera [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. Ele pega seu argumento funcional (nesse caso k) e executa essa função sobre cada par, que, nesse caso, simplesmente retorna os pares como estão.

$A$€bF

$1, 2$$3$$n$l$n$