Niektóre liczby, takie jak , są palindromami w podstawie 10: jeśli napiszesz cyfry w odwrotnej kolejności, otrzymasz ten sam numer.$14241$

Niektóre liczby są sumą 2 palindromów; na przykład lub .$110=88+22$$2380=939+1441$

W przypadku innych liczb 2 palindromy nie wystarczą; na przykład 21 nie można zapisać jako sumy 2 palindromów, a najlepsze, co możesz zrobić, to 3: .$21=11+9+1$

Napisz funkcję lub program, który pobiera liczby całkowite ni wyprowadza nliczbę, której nie można rozłożyć na sumę 2 palindromów. Odpowiada to OEIS A035137 .

Pojedyncze cyfry (w tym 0) to palindromy.

Obowiązują standardowe zasady dotyczące sekwencji:

• wejście / wyjście jest elastyczne
• możesz użyć indeksowania 0 lub 1
• możesz nwypisać termin, pierwsze nterminy lub nieskończoną sekwencję

(Na marginesie: wszystkie liczby całkowite można rozłożyć jako sumę co najwyżej 3 palindromów.)

Przypadki testowe (indeksowane 1):

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

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź.

JavaScript (ES6),  93 83 80  79 bajtów

Zapisano 1 bajt dzięki @tsh

Zwraca ^ty termin, 1-indeksowany.$n$

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

Wypróbuj online!

W jaki sposób?

Biorąc pod uwagę , testujemy, czy istnieje jakikolwiek taki, że zarówno jak i są palindromami. Jeśli znajdziemy takie , to jest sumą dwóch palindromów.$n$$1\le k\le n$$k$$n-k$$k$$n$

Sztuczka polega na jednoczesnym przetwarzaniu i przez testowanie pojedynczego łańcucha utworzonego z połączenia , i .$k$$n-k$$k$$n-k$$k$

Przykład:

Dla :$n=2380$

• ostatecznie osiągamy i$k=1441$$n-k=939$
• testujemy ciąg „ ” i dowiadujemy się, że jest to palindrom$1441\color{red}{939}1441$

Skomentował

Uwaga: To jest wersja bez eval()czytelności.

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
}                            //

Galaretka ,  16 10  9 bajtów

-1 bajt dzięki Erik the Outgolfer . Wyprowadza pierwsze wyrażeń.$n$

2_ŒḂƇ⁺ṆƲ#

Wypróbuj online!

Próbowałem wymyślić inny pomysł niż moje oryginalne podejście. Przyjrzyjmy się procesowi myślenia:

• Początkowo test działał w następujący sposób: wygenerował całkowite partycje o tej liczbie, a następnie odfiltrował te, które również zawierały nie-palindromy, a następnie policzył, ile było dopuszczalnych list o długości 2. Nie było to oczywiście zbyt wydajne pod względem długości kodu.

• Generowanie całkowitych partycji a następnie filtrowanie miało 2 główne wady: efektywność długości i czasu. Aby rozwiązać ten problem, pomyślałem, że najpierw wymyślę metodę generowania tylko par liczb całkowitych które sumują się do (nie wszystkich list o dowolnej długości), pod warunkiem, że obie liczby muszą być palindromem.$N$( x , y ) N$(x, y)$$N$

• Ale nadal nie byłem zadowolony z „klasycznego sposobu” tego. Zmieniłem podejście: zamiast generować pary , skupmy się na programie na indywidualnych palindromach . W ten sposób można po prostu obliczyć wszystkie palindromy poniżej , a jeśli jest również palindromem, to skończymy.$x$$N$$N-x$

Objaśnienie kodu

2_ŒḂƇ⁺ṆƲ # - Monadyczny link lub Pełny program. Argument: n.
2 # - Począwszy od 2 * , znajdź pierwsze n liczb całkowitych, które spełniają ...
 _ŒḂƇ⁺ṆƲ - ... link pomocnika. Podział (nazwij bieżącą liczbę całkowitą N):
    Ƈ - Filtruj. Tworzy zakres [1 ... N] i zachowuje tylko te, które ...
  ŒḂ - ... są palindromami. Przykład: 21 -> [1,2,3,4,5,6,7,8,9,11]
 _ - Odejmij każdą z tych palindromów od N. Przykład: 21 -> [20,19, ..., 12,10]
     ⁺ - Zduplikuj poprzedni link (pomyśl o tym, jakby istniał dodatkowy ŒḂƇ
            zamiast ⁺). To tylko utrzymuje palindromy na tej liście.
            Jeśli lista nie jest pusta, oznacza to, że znaleźliśmy parę (x, Nx), która
            zawiera dwie palindromy (i oczywiście x + Nx = N, więc sumują się do N).
      Ṇ - Logiczne NIE (szukamy liczb całkowitych, dla których ta lista jest pusta).
       Ʋ - Grupuj 4 ostatnie linki (w zasadzie spraw, aby _ŒḂƇ⁺Ṇ działał jak pojedyncza monada).

^{* W tym przypadku działa każda inna niezerowa cyfra.}

Galaretka , 11 bajtów

⁵ŻŒḂ€aṚ$EƲ#

Wypróbuj online!

Pełny program działa mniej więcej tak:

1. Ustaw z na wartość wejściową.
2. Ustaw x na 10 .
3. Ustaw R na [] .
4. Dla każdej liczby całkowitej k od 0 do x włącznie , sprawdź, czy zarówno k, jak i x - k są palindromiczne.
5. Jeśli wszystkie elementy L są równe (to znaczy, jeśli albo wszystkie możliwe pary sumujące się do x mają oba swoje elementy palindromiczne, lub wszystkie takie pary mają co najwyżej jeden z ich elementów palindromicznych), ustaw z na z - 1 i dołącz x do R .
6. Jeśli z = 0 , zwróć R i zakończ.
7. Ustaw x na x + 1 .
8. Przejdź do kroku 4.

Możesz podejrzewać, że krok 5 tak naprawdę nie wykonuje pracy, którą powinien. Naprawdę nie powinniśmy zmniejszać wartości z, jeśli wszystkie pary sumujące do x są palindromiczne. Możemy jednak udowodnić, że tak się nigdy nie stanie:

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

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

Jeśli natomiast $k$ jest palindromem, możemy udowodnić, że $k-1$ nie jest palindromem. Niech pierwsze i ostatnie cyfry $k$ być $D_F$ i $D_L$ odpowiednio. Ponieważ $k$ jest palindromem, $D_F=D_L>0$ . Niech pierwsze i ostatnie cyfry $k-1$ BE $D'_F$ i $D'_L$ odpowiednio. Ponieważ $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$

Dochodzimy do wniosku, że jeśli zaczniemy od ustawienia x na wartość większą lub równą 10 , nigdy nie możemy mieć wszystkich par liczb całkowitych nieujemnych, które sumują się jako x par palindromów.

Siatkówka , 135 102 bajtów

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

Wypróbuj online! Zbyt wolny dla n10 lub więcej. Wyjaśnienie:

K`0

Zacznij od wypróbowania 0.

"$+"{

Powtórz nczasy.

0L$`\d+
*__

Konwertuj bieżącą wartość próbną na jednostkową i zwiększ ją.

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

Utwórz wszystkie pary nieujemnych liczb całkowitych, które sumują się do nowej wartości próbnej.

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

Powtarzaj, dopóki istnieje co najmniej jedna para zawierająca dwie liczby całkowite palindromiczne.

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

Zwiększ i ponownie rozwiń wartość próby.

0L`\d+

Wyodrębnij wartość końcową.

Haskell, 68 67 63 bajtów

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

Zwraca nieskończoną sekwencję.

Zbierz wszystkie ngdzie albo aczy n-anie jest palindrom dla wszystkich a <- [0..n].

Wypróbuj online!

Perl 5 -MList::Util=any -p , 59 55 bajtów

-3 bajty dzięki @NahuelFouilleul

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

Wypróbuj online!

Uwaga: anymożna go zastąpić grepi unikać -Mprzełączania wiersza poleceń, ale przy obecnych regułach punktacji kosztowałoby to jeszcze jeden bajt.

R , 115 111 bajtów

-4 dzięki 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]

Wypróbuj online!

Większość pracy jest zapakowana w argumenty funkcji, aby usunąć {}wywołanie funkcji dla wielu instrukcji i zmniejszyć nawiasy potrzebne do zdefiniowania obiektur

Podstawową strategią jest znalezienie wszystkich palindromów do danej granicy (w tym 0), znalezienie wszystkich par par, a następnie pobranie n-tej liczby nie znajdującej się w tym wyniku.

Granica n*1000została wybrana wyłącznie z domysłów wykształconych, więc zachęcam każdego, kto udowodni / potępi ją jako słuszny wybór.

r=0:(n*1e3)prawdopodobnie można go poprawić za pomocą bardziej wydajnego wiązania.

Map(paste,Map(rev,strsplit(a,"")),collapse="")został zerwany z odpowiedzi Marka tutaj i jest dla mnie niesamowicie sprytny.

r[!r%in%outer(p,p,'+')][n]czyta mi to trochę nieefektywnie.

C # (interaktywny kompilator Visual C #) , 124 bajty

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

Wypróbuj online!

J , 57/60 bajtów

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

Wypróbuj online!

Połączona wersja dodaje 3 bajty w sumie 60, aby zapisać jako funkcję, którą stopka może wywołać.

W REPL można tego uniknąć, dzwoniąc bezpośrednio:

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

Wyjaśnienie

Ogólna struktura jest taka, że od tej techniki z odpowiedzią przez 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

Pozwoliło to zaoszczędzić kilka bajtów w porównaniu z moją oryginalną techniką zapętlania, ale ponieważ podstawową funkcją jest moja pierwsza próba napisania J, prawdopodobnie nadal można wiele poprawić.

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 bajtów

°ÝDʒÂQ}ãOKIè

-3 bajty dzięki @Grimy .

0-indeksowane.
Bardzo wolno, więc limit czasu dla większości przypadków testowych.

Wypróbuj online lub sprawdź kilka pierwszych przypadków, usuwającIè .

Znacznie szybsza poprzednia 15 bajtowa wersja:

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

1-indeksowany.

$n$

Wyjaśnienie:

°Ý              # 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)

Czerwony , 142 bajty

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]

Wypróbuj online!

Zwraca n-ty termin, 1-indeksowany

Python 3 , 107 bajtów

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

Wypróbuj online!

Odwrócenie sprawdzania palindromu zapisało 2 bajty :)

Dla porównania: bezpośrednia kontrola dodatnia (109 bajtów):

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 bajtów

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

Jakie jest słowo „przerwać pętlę”? Wygląda na to, że to „: zostaw”, prawda? {k≡⌽k←⍕⍵}w p jest testem na palindrom. Ta powyższa funkcja w pętli przechowuje cały palindrom znaleziony w zbiorze P, jeśli dla jakiegoś elementu w P jest również taki, że iw jest również w P, oznacza to, że i nie jest poprawne i mamy przyrost i. Wyniki:

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