Jede positive ganze Zahl kann als die Summe von höchstens drei positiven palindromen ganzen Zahlen in jeder Basis b ≥ 5 ausgedrückt werden.   Cilleruelo et al., 2017

Eine positive ganze Zahl ist in einer gegebenen Basis palindromisch , wenn ihre Darstellung in dieser Basis ohne führende Nullen dasselbe rückwärts liest. Im Folgenden wird nur die Basis b = 10 berücksichtigt.

Die Zerlegung als Summe palindromischer Zahlen ist nicht eindeutig . Beispielsweise 5kann direkt als 5oder als die Summe von ausgedrückt werden 2, 3. Ebenso 132kann als 44, 44, 44oder als zerlegt werden 121, 11.

Die Herausforderung

Bei einer positiven Ganzzahl wird die Summe in drei oder weniger positive Ganzzahlen zerlegt, die in Basis 10 palindrom sind.

Zusätzliche Regeln

• Der verwendete Algorithmus sollte für beliebig große Eingaben funktionieren. Es ist jedoch akzeptabel, wenn das Programm durch Speicher-, Zeit- oder Datentypbeschränkungen eingeschränkt ist.

• Eingabe und Ausgabe können mit jedem vernünftigen Mittel erfolgen . Das Eingabe- und Ausgabeformat ist wie gewohnt flexibel.

• Sie können für jede Eingabe eine oder mehrere gültige Dekompositionen erstellen, sofern das Ausgabeformat eindeutig ist.

• Programme oder Funktionen sind in jeder Programmiersprache zulässig . Standardlücken sind verboten.

• Kürzester Code in Bytes gewinnt.

Beispiele

Da eine Eingabe viele Zerlegungen aufweisen kann, handelt es sich hierbei eher um Beispiele als um Testfälle. Jede Zerlegung wird in einer anderen Zeile angezeigt.

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

Brachylog , 7 Bytes

~+ℕᵐ.↔ᵐ

Probieren Sie es online!

Überraschenderweise nicht so langsam.

Erläuterung

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

Probieren Sie es online!

Jelly , 12 10 9 8 Bytes

ŒṗDfU$ṪḌ

Probieren Sie es online!

Wie es funktioniert

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

Probieren Sie es online!

Druckt eine Liste mit Listen, von denen jede eine Lösung darstellt. Rod sparte 9 Bytes.

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

Gibt immer ein Array mit drei Elementen zurück, bei dem nicht verwendete Einträge mit Nullen aufgefüllt werden.

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

Testfälle

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

Vielen Dank an Giuseppe für das Abschlagen von 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)}

Probieren Sie es online!

Erläuterung

R bietet keine systemeigene Möglichkeit, Zeichenfolgen umzukehren, und viele Standardzeichenfolgenoperationen funktionieren nicht mit Zahlen. Also konvertieren wir zuerst die Reihe positiver Ganzzahlen (plus 0) in Zeichen.

Als nächstes erzeugen wir einen Vektor von 0 und allen Palindromen. Die Umkehrung der Zeichenfolge erfordert das Aufteilen jeder Zahl nach Zeichen, das Umkehren der Reihenfolge des Vektors und das lückenlose Einfügen derselben.

Als nächstes möchte ich alle Dreiergruppen überprüfen (hier sind die Nullen wichtig). Glücklicherweise hat R eine eingebaute Kombinationsfunktion, die eine Matrix zurückgibt, jede Spalte in einer Kombination.

Ich wende die colSumsFunktion auf die Matrix an und behalte nur die Elemente, die dem angegebenen Ziel entsprechen.

Da es schließlich zwei Nullen gibt, wird jeder Satz von zwei positiven Ganzzahlen dupliziert, sodass ich eine eindeutige Funktion für die Spalten verwende.

Die Ausgabe ist eine Matrix, in der jede Spalte eine Reihe positiver pallindromischer Ganzzahlen ist, die sich zum Zielwert addieren. Es ist faul und gibt Nullen zurück, wenn weniger als 3 Elemente verwendet werden.

Jelly , 14 Bytes

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

Probieren Sie es online!

Sehr, sehr ineffizient.

Gelee , 17 Bytes

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

Probieren Sie es online!

-6 Bytes dank HyperNeutrino.

Ausgänge in alle Richtungen. Die Ausgabe besteht jedoch aus einigen Duplikaten.

Ohm v2 , 13 12 10 Bytes

#Dð*3ç⁇Σ³E

Probieren Sie es online!

Mathematica, 49 Bytes

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

Probieren Sie es online!

gibt alle Lösungen zurück

-2 ~ MartinEnder ~ Bytes

Haskell , 90 86 79 Bytes

-7 Bytes dank Laikoni!

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

Probieren Sie es online!

Gibt eine Liste aller Lösungen mit einigen Duplikaten zurück.

Java (OpenJDK 8) , 185 Byte

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

Probieren Sie es online!

Entfernen Sie 1 Byte aus TIO, um die richtige Menge zu erhalten, da die Übermittlung das ;After-Lambda nicht enthält .

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]

Probieren Sie es online!

Gibt eine Lösung aus

Pyth ,  16 12  10 Bytes

ef_I#`MT./

Probieren Sie es hier aus!

Wie es funktioniert

ef_I # `MT. / ~ Volles Programm.

        ./ ~ Integer-Partitionen.
 f ~ Filter mit einer Variablen T.
     `MT ~ Ordne jedes Element von T einer Zeichenfolgendarstellung zu.
    # ~ Filter.
  Ist Palindrom? (dh invariant über umgekehrt?)
e ~ Letztes Element holen.

05AB1E , 17 Bytes

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

Probieren Sie es online!

Gibt das Ergebnis in drei Listen wie folgt aus:

• Palindromic Listen der Länge 1 (die ursprüngliche Nummer IFF ist palindromic).

• Palindrome Listen der Länge 2.

• Palindrome Listen der Länge 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);[])

Testcode

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

Wenn dieser Code die Zahl X in 1, 2, 3 Palindrom zerlegen muss, was dieser Code tut, wird es in der Nähe von Palindrom N <X versucht und XN in 2 Palindrom zerlegt; Wenn diese Zersetzung von XN erfolgreich ist, werden 3 Palindrome gefunden. wenn es fehlschlägt, versuche es das vorhergehende Palindrom G <N <X und zerlege XG in 2 Palindrome usw. Ungolf Code (aber es ist ein Fehler möglich)

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

Ergebnisse:

(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 Byte

Druckt Dupes, aber sie sind afaik nicht verboten

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

Probieren Sie es online!

APL (Dyalog) , 51 Bytes

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

Probieren Sie es online!

05AB1E , 8 Bytes

ÅœR.ΔDíQ

Probieren Sie es online!

Erläuterung:

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

Probieren Sie es online!

• grep { $_ eq .flip }, 1 .. $_ Erzeugt eine Liste aller palindromischen Zahlen von 1 bis zur eingegebenen Zahl.
• 3 Rxx repliziert diese Liste dreimal.
• [X]Reduziert diese Liste der Listen mit dem produktübergreifenden Operator X, was zu einer Liste aller 3 Tupel von Palindrominc-Zahlen von 1 bis zur eingegebenen Nummer führt.
• first *.sum == $_ findet das erste solche 3-Tupel, das zur eingegebenen Zahl summiert.

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]

Probieren Sie es online!

In der TIO-Verknüpfung habe ich eine schnellere (aber 1 Byte längere) Version verwendet, die das erste gültige Ergebnis als Generator verwendet, anstatt die gesamte Liste der möglichen Kombinationen zu erstellen und die erste zu verwenden.

Ruby , 84 Bytes

Erstellt eine Liste aller möglichen Kombinationen von 3 Palindromen von 0 bis n, findet die erste, deren Summe übereinstimmt, und schneidet dann die Nullen ab.

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

Probieren Sie es online!

Add ++ , 62 Bytes

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

Probieren Sie es online!

~ 50 Bytes wurden beim Verfassen einer Erklärung abgelegt. Definiert eine Lambda-Funktion, die eine Liste von Listen mit den Lösungen zurückgibt.

Wie es funktioniert

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

$1, 2, ..., n$gRÞgg$A$ für später.

Der nächste Abschnitt kann in drei weitere Teile unterteilt werden:

BcB]
Gd‽k
dG‽k€bF

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

D,k,@@*,

Diese Funktion macht im Grunde nichts. Es empfängt zwei Argumente und umschließt sie in einem Array. Der schnelle Tisch ‽ist hier jedoch der Zaubertrick. Es nimmt zwei Listen und generiert jedes Elementpaar zwischen diesen beiden Listen. Also [1 2 3]und [4 5 6]erzeugt [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]. Es nimmt dann sein funktionales Argument (in diesem Fallk ) und führt diese Funktion über jedes Paar aus, das in diesem Fall die Paare einfach so zurückgibt, wie sie sind.

$A$€bF

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