Certains nombres, comme $14241$ , sont des palindromes en base 10: si vous écrivez les chiffres dans l'ordre inverse, vous obtenez le même nombre.

Certains nombres sont la somme de 2 palindromes; par exemple, ou .$110=88+22$$2380=939+1441$

Pour les autres nombres, 2 palindromes ne suffisent pas; par exemple, 21 ne peut pas être écrit comme la somme de 2 palindromes, et le mieux que vous puissiez faire est de 3: .$21=11+9+1$

Écrivez une fonction ou un programme qui prend une entrée entière net sort le nnombre e qui ne peut pas être décomposé comme la somme de 2 palindromes. Cela correspond à OEIS A035137 .

Les chiffres uniques (dont 0) sont des palindromes.

Les règles standard pour les séquences s'appliquent:

• l'entrée / sortie est flexible
• vous pouvez utiliser l'indexation 0 ou 1
• vous pouvez sortir le ne terme, ou les premiers ntermes, ou une séquence infinie

(En guise de note: tous les nombres entiers peuvent être décomposés comme la somme d'au plus 3 palindromes.)

Cas de test (1 indexé):

1 -> 21
2 -> 32
10 -> 1031
16 -> 1061
40 -> 1103

C'est le golf de code, donc la réponse la plus courte l'emporte.

JavaScript (ES6),  93 83 80  79 octets

1 octet enregistré grâce à @tsh

Renvoie le $n$ ^ième terme, indexé sur 1.

i=>eval("for(n=k=1;k=(a=[...k+[n-k]+k])+''!=a.reverse()?k-1||--i&&++n:++n;);n")

Essayez-le en ligne!

Comment?

Étant donné $n$ , nous testons s'il existe un $1\le k\le n$ tel que $k$ et $n-k$ soient des palindromes. Si nous trouvons un tel $k$ , alors $n$ est la somme de deux palindromes.

L'astuce consiste ici à traiter $k$ et $n-k$ en même temps en testant une seule chaîne constituée de la concaténation de $k$ , $n-k$ et $k$ .

Exemple:

Pour $n=2380$ :

• on atteint finalement $k=1441$ et $n-k=939$
• nous testons la chaîne " $1441\color{red}{939}1441$ " et découvrons qu'il s'agit d'un palindrome

Commenté

NB: Il s'agit d'une version sans eval()lisibilité.

i => {                       // i = index of requested term (1-based)
  for(                       // for loop:
    n = k = 1;               //   start with n = k = 1
    k =                      //   update k:
      ( a =                  //     split and save in a[] ...
        [...k + [n - k] + k] //     ... the concatenation of k, n-k and k
      ) + ''                 //     coerce it back to a string
      != a.reverse() ?       //     if it's different from a[] reversed:
        k - 1                //       decrement k; if the result is zero:
          || --i             //         decrement i; if the result is not zero:
            && ++n           //           increment n (and update k to n)
                             //         (otherwise, exit the for loop)
      :                      //     else:
        ++n;                 //       increment n (and update k to n)
  );                         // end of for
  return n                   // n is the requested term; return it
}                            //

Gelée ,  16 10  9 octets

-1 octet grâce à Erik l'Outgolfer . Génère les $n$ premiers termes.

2_ŒḂƇ⁺ṆƲ#

Essayez-le en ligne!

J'ai essayé de proposer une idée différente de mon approche d'origine. Passons en revue le processus de réflexion:

• Initialement, le test a fonctionné comme suit: il a généré les partitions entières de ce nombre, puis a filtré celles qui contenaient également des non-palindromes, puis a compté le nombre de listes admissibles de longueur 2. Ce n'était évidemment pas trop efficace en termes de longueur de code.

• La génération des partitions entières de $N$ puis le filtrage présentaient 2 inconvénients principaux: l'efficacité en temps et en temps. Pour résoudre ce problème, j'ai pensé que je trouverais d'abord une méthode pour générer uniquement les paires d'entiers $(x, y)$ qui totalisent $N$ (pas toutes les listes de longueur arbitraire) à condition que les deux nombres soient palindromes.

• Mais quand même, je n'étais pas satisfait de la "manière classique" de procéder. J'ai changé d'approches: au lieu de générer des paires , concentrons le programme sur des palindromes individuels . De cette façon, on peut simplement calculer tous les palindromes $x$ dessous de $N$ , et si $N-x$ est également palindrome, alors nous avons terminé.

Explication du code

2_ŒḂƇ⁺ṆƲ # - Lien monadique ou programme complet. Argument: n.
2 # - A partir de 2 * , trouvez les n premiers entiers qui satisfont ...
 _ŒḂƇ⁺ṆƲ - ... le lien d'aide. Répartition (appelez l'entier courant N):
    Ƈ - Filtre. Crée la plage [1 ... N] et ne conserve que ceux qui ...
  ŒḂ - ... sont des palindromes. Exemple: 21 -> [1,2,3,4,5,6,7,8,9,11]
 _ - Soustrayez chacun de ces palindromes de N. Exemple: 21 -> [20,19, ..., 12,10]
     ⁺ - Dupliquez le lien précédent (pensez-y comme s'il y avait un ŒḂƇ supplémentaire
            au lieu de ⁺). Cela ne conserve que les palindromes dans cette liste.
            Si la liste n'est pas vide, cela signifie que nous avons trouvé une paire (x, Nx) qui
            contient deux palindromes (et évidemment x + Nx = N donc ils se résument à N).
      Ṇ - NON logique (nous recherchons les entiers pour lesquels cette liste est vide).
       Ʋ - Regroupez les 4 derniers liens (faites en sorte que _ŒḂƇ⁺Ṇ agisse comme une seule monade).

^{* Tout autre chiffre non nul fonctionne, d'ailleurs.}

Gelée , 11 octets

⁵ŻŒḂ€aṚ$EƲ#

Essayez-le en ligne!

Le programme complet fonctionne à peu près comme ceci:

1. Réglez z sur l'entrée.
2. Réglez x sur 10 .
3. Réglez R sur [] .
4. Pour chaque entier k de 0 à x inclus , vérifiez si k et x - k sont tous deux palindromiques.
5. Si tous les éléments de L sont égaux (c'est-à-dire si toutes les paires possibles totalisant x ont leurs deux éléments palindromiques, ou si toutes ces paires ont au plus un de leurs éléments palindromiques), définissez z sur z - 1 et ajoutez x à R .
6. Si z = 0 , retournez R et terminez.
7. Réglez x sur x + 1 .
8. Passez à l'étape 4.

Vous pouvez soupçonner que l'étape 5 ne fait pas vraiment le travail qu'elle devrait. Nous ne devrions vraiment pas décrémenter z si toutes les paires qui totalisent x sont palindromiques. Cependant, nous pouvons prouver que cela ne se produira jamais:

$k$$10\le k\le x$

$k$$(k,x-k)$$k+(x-k)=x$

$k$$k-1$$k$$D_F$$D_L$$k$$D_F=D_L>0$$k-1$$D'_F$$D'_L$$D_L>0$$D'_L=D'_F-1\ne D'_F$$k-1$$(k-1,x-(k-1))$$(k-1)+(x-(k-1))=k-1+x-k+1=x$

Nous concluons que, si nous commençons par fixer x à une valeur supérieure ou égale à 10 , nous ne pouvons jamais avoir toutes les paires d'entiers non négatifs qui totalisent x x paires de palindromes.

Rétine , 135 102 octets

K`0
"$+"{0L$`\d+
*__
L$`
<$.'>$.`>
/<((.)*.?(?<-2>\2)*(?(2)$)>){2}/{0L$`\d+
*__
))L$`
<$.'>$.`>
0L`\d+

Essayez-le en ligne! Trop lent pour n10 ou plus. Explication:

K`0

Commencez par essayer 0.

"$+"{

Répétez nfois.

0L$`\d+
*__

Convertissez la valeur d'essai actuelle en unaire et incrémentez-la.

L$`
<$.'>$.`>

Créez toutes les paires d'entiers non négatifs qui totalisent la nouvelle valeur d'essai.

/<((.)*.?(?<-2>\2)*(?(2)$)>){2}/{

Répétez pendant qu'il existe au moins une paire contenant deux nombres entiers palindromiques.

0L$`\d+
*__
))L$`
<$.'>$.`>

Augmentez et augmentez à nouveau la valeur d'essai.

0L`\d+

Extraire la valeur finale.

Haskell, 68 67 63 octets

[n|n<-[1..],and[p a||p(n-a)|a<-[0..n]]]
p=((/=)=<<reverse).show

Renvoie une séquence infinie.

Rassemblez tout noù soit aou n-an'est pas un palindrome pour tous a <- [0..n].

Essayez-le en ligne!

Perl 5 -MList::Util=any -p , 59 55 octets

-3 octets grâce à @NahuelFouilleul

++$\while(any{$\-reverse($\-$_)==reverse}0..$\)||--$_}{

Essayez-le en ligne!

Remarque: anypourrait être remplacé par grepet éviter le -Mcommutateur de ligne de commande, mais selon les règles de notation actuelles, cela coûterait un octet de plus.

R , 115 111 octets

-4 merci à Giuseppe

function(n,r=0:(n*1e3))r[!r%in%outer(p<-r[Map(Reduce,c(x<-paste0),Map(rev,strsplit(a<-x(r),"")))==a],p,'+')][n]

Essayez-le en ligne!

La plupart du travail est intégré dans les arguments de fonction pour supprimer {} pour un appel de fonction à instructions multiples et pour réduire les crochets nécessaires à la définition de l'objetr

La stratégie de base consiste à trouver tous les palindromes jusqu'à une limite donnée (y compris 0), à trouver toutes les sommes par paire, puis à prendre le nième nombre qui ne figure pas dans cette sortie.

La limite de n*1000 été choisie uniquement à partir d'une supposition éclairée, donc j'encourage quiconque à le prouver / le réfuter comme un choix valide.

r=0:(n*1e3)peut probablement être amélioré avec une limite plus efficace.

Map(paste,Map(rev,strsplit(a,"")),collapse="")est arraché de la réponse de Mark ici , et est juste incroyablement intelligent pour moi.

r[!r%in%outer(p,p,'+')][n]me lit un peu inefficace.

C # (Visual C # Interactive Compiler) , 124 octets

n=>{int a=0;for(string m;n>0;)if(Enumerable.Range(0,++a).All(x=>!(m=x+""+(a-x)+x).Reverse().SequenceEqual(m)))n--;return a;}

Essayez-le en ligne!

J , 57/60 octets

0(](>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~]

Essayez-le en ligne!

La version liée ajoute 3 octets pour un total de 60 afin d'enregistrer en tant que fonction que le pied de page peut appeler.

Dans le REPL, cela est évité en appelant directement:

   0(](>:^:(1 e.q e.]-q=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~] 1 2 10 16 40
21 32 1031 1061 1103

Explication

La structure générale est celle de cette technique à partir d'une réponse de Miles :

(s(]f)^:[~]) n
          ]  Gets n
 s           The first value in the sequence
         ~   Commute the argument order, n is LHS and s is RHS
        [    Gets n
      ^:     Nest n times with an initial argument s
  (]f)         Compute f s
         Returns (f^n) s

Cela a permis d'économiser quelques octets par rapport à ma technique de boucle d'origine, mais comme la fonction principale est ma première tentative d'écriture de J, il y a probablement encore beaucoup à améliorer.

0(](>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~]
0(]                                                 ^:[~] NB. Zero as the first term switches to one-indexing and saves a byte.
   (>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)      NB. Monolithic step function.
                                                 >:       NB. Increment to skip current value.
   (>:^: <predicate>                        ^:_)          NB. Increment current value as long as predicate holds.
                   p=:(#~(-:|.)&":&>)&i.&>:               NB. Reused: get palindromes in range [0,current value].
                       #~(-:|.)&":&>                      NB. Coerce to strings keeping those that match their reverse.
                 ]-p                                      NB. Subtract all palindromes in range [0,current value] from current value.
    >:^:(1&e.p e.]-p                                      NB. Increment if at least one of these differences is itself a palindrome.

05AB1E , 15 12 octets

°ÝDʒÂQ}ãOKIè

-3 octets grâce à @Grimy .

0 indexé.
Très lent, expire donc pour la plupart des cas de test.

Essayez-le en ligne ou vérifiez les premiers cas en supprimant leIè .

Version 15 octets beaucoup plus rapide:

µNÐLʒÂQ}-ʒÂQ}g_

1 indexé.

Essayez-le en ligne ou sortez le premier$n$ valeurs .

Explication:

°Ý              # Create a list in the range [0, 10**input]
  D             # Duplicate this list
   ʒÂQ}         # Filter it to only keep palindromes
       ã        # Take the cartesian product with itself to create all possible pairs
        O       # Sum each pair
         K      # Remove all of these sums from the list we duplicated
          Iè    # Index the input-integer into it
                # (after which the result is output implicitly)

µ               # Loop until the counter variable is equal to the (implicit) input-integer
 NÐ             #  Push the loop-index three times
   L            #  Create a list in the range [1, N] with the last copy
    ʒÂQ}        #  Filter it to only keep palindromes
        -       #  Subtract each from N
         ʒÂQ}   #  Filter it again by palindromes
             g_ #  Check if the list is empty
                #   (and if it's truthy: increase the counter variable by 1 implicitly)
                # (after the loop: output the loop-index we triplicated implicitly as result)

Rouge , 142 octets

func[n][i: 1 until[i: i + 1 r: on repeat k i[if all[(to""k)= reverse
to""k(s: to""i - k)= reverse copy s][r: off break]]if r[n: n - 1]n < 1]i]

Essayez-le en ligne!

Renvoie le nième terme, 1 indexé

Python 3 , 107 octets

p=lambda n:str(n)!=str(n)[::-1]
def f(n):
 m=1
 while n:m+=1;n-=all(p(k)+p(m-k)for k in range(m))
 return m

Essayez-le en ligne!

Inverser la vérification du palindrome a sauvé 2 octets :)

Pour référence, le contrôle positif simple (109 octets):

p=lambda n:str(n)==str(n)[::-1]
def f(n):
 m=1
 while n:m+=1;n-=1-any(p(k)*p(m-k)for k in range(m))
 return m

APL (NARS), 486 octets

r←f w;p;i;c;P;m;j
p←{k≡⌽k←⍕⍵}⋄i←c←0⋄P←r←⍬
:while c<w
    i+←1
    :if   p i⋄P←P,i⋄:continue⋄:endif
    m←≢P⋄j←1
    :while j≤m
         :if 1=p i-j⊃P⋄:leave⋄:endif
         j+←1
    :endwhile
    :if j=m+1⋄c+←1⋄r←i⋄:endif
:endwhile

Quel est le mot pour rompre la boucle? Il semble que ce soit ": partir", non? {k≡⌽k←⍕⍵}en p est le test du palindrome. Cette fonction ci-dessus dans la boucle stocke tout le palindrome trouvé dans l'ensemble P, si pour un élément w de P est tel que iw est aussi dans P, cela signifie que le i n'est pas correct et nous avons l'incrément i. Résultats:

  f 1
21
  f 2
32
  f 10
1031
  f 16
1061
  f 40
1103
  f 1000
4966
  f 1500
7536