Некоторые числа, такие как , являются палиндромами в базе 10: если вы напишите цифры в обратном порядке, вы получите тот же номер.$14241$

Некоторые числа являются суммой 2 палиндромов; например, или .$110=88+22$$2380=939+1441$

Для других чисел 2 палиндромов недостаточно; например, 21 нельзя записать как сумму 2 палиндромов, и лучшее, что вы можете сделать, это 3: $21=11+9+1$ .

Напишите функцию или программу, которая принимает целочисленный ввод nи выводит nчисло, которое не может быть разложено как сумма 2 палиндромов. Это соответствует OEIS A035137 .

Однозначные числа (включая 0) являются палиндромами.

Стандартные правила для последовательностей применяются:

• Ввод / вывод является гибким
• Вы можете использовать 0- или 1- индексацию
• Вы можете вывести nth-й термин, или первые nтермины, или бесконечную последовательность

(В качестве обозначения: все целые числа можно разложить как сумму не более 3 палиндромов.)

Контрольные примеры (1-индексированные):

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

Это код-гольф, поэтому выигрывает самый короткий ответ.

JavaScript (ES6),  93 83 80  79 байтов

Сохранено 1 байт благодаря @tsh

Возвращает ^й член, 1-индексированный.$n$

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

Попробуйте онлайн!

Как?

Учитывая , мы проверяем, существует ли такой, что и являются палиндромами. Если мы найдем такое , то будет суммой двух палиндромов.$n$$1\le k\le n$$k$$n-k$$k$$n$

Хитрость в том, чтобы обрабатывать и одновременно, проверяя одну строку, состоящую из конкатенации , и .$k$$n-k$$k$$n-k$$k$

Пример:

Для :$n=2380$

• в итоге мы достигаем и$k=1441$$n-k=939$
• мы проверяем строку « $1441\color{red}{939}1441$ » и выясняем, что это палиндром

комментарии

NB: это версия без eval()читабельности.

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

Желе ,  16 10  9 байт

-1 байт благодаря Эрику Аутгольферу . Выводит первые $n$ членов.

2_ŒḂƇ⁺ṆƲ#

Попробуйте онлайн!

Я пытался придумать другую идею по сравнению с моим первоначальным подходом. Давайте рассмотрим процесс мышления:

• Первоначально тест работал следующим образом: он генерировал целочисленные разделы этого числа, затем отфильтровывал те, которые также содержали непалиндромы, а затем подсчитывал, сколько существует списков, подходящих для длины 2. Это было явно не слишком эффективно с точки зрения длины кода.

• Генерация целочисленных разделов $N$ и последующая фильтрация имели 2 основных недостатка: длительность и эффективность по времени. Чтобы решить эту проблему, я подумал, что сначала придумаю метод, который генерирует только пары целых чисел $(x, y)$ которые суммируют с $N$ (не все списки произвольной длины), с условием, что оба числа должны быть палиндромами.

• Но, тем не менее, я не был удовлетворен «классическим подходом» к этому. Я поменял подходы: вместо генерации пар , давайте сосредоточим программу на отдельных палиндромах . Таким образом, можно просто вычислить все палиндромы $x$ ниже $N$ , и если $N-x$ также палиндром, то мы закончили.

Код Объяснение

2_ŒḂƇ⁺ṆƲ # - Монадическая ссылка или Полная программа. Аргумент: н.
2 # - Начиная с 2 * , найти первые n целых чисел, которые удовлетворяют ...
 _ŒḂƇ⁺ṆƲ - ... вспомогательная ссылка. Разбивка (назовите текущее целое число N):
    Filter - Фильтр. Создает диапазон [1 ... N] и сохраняет только те, которые ...
  ŒḂ - ... палиндромы. Пример: 21 -> [1,2,3,4,5,6,7,8,9,11]
 _ - Вычтите каждый из этих палиндромов из N. Пример: 21 -> [20,19, ..., 12,10]
     ⁺ - продублируйте предыдущую ссылку (подумайте, как будто есть дополнительная ŒḂƇ
            вместо ⁺). Это только сохраняет палиндромы в этом списке.
            Если список не пустой, это означает, что мы нашли пару (x, Nx), которая
            содержит два палиндрома (и, очевидно, x + Nx = N, поэтому они суммируются с N).
      Log - Логическое НЕ (мы ищем целые числа, для которых этот список пуст).
       Group - Сгруппировать последние 4 ссылки (в основном, заставить _ŒḂƇ⁺Ṇ выступать в качестве одной монады).

^{* Любая другая ненулевая цифра работает, в этом отношении.}

Желе , 11 байт

⁵ŻŒḂ€aṚ$EƲ#

Попробуйте онлайн!

Полная программа примерно работает так:

1. Установите z на вход.
2. Установите х в 10 .
3. Установите R в [] .
4. Для каждого целого числа k от 0 до x включительно проверьте, являются ли k и x - k палиндромными.
5. Если все элементы L равны (то есть, если либо все возможные пары, суммирующие с x, имеют оба палиндромных элемента, либо все такие пары имеют не более одного из своих элементов, являющегося палиндромным), установите z в z - 1 и добавьте x к р .
6. Если z = 0 , вернуть R и закончить.
7. Установите х в х + 1 .
8. Переходите к шагу 4.

Вы можете подозревать, что шаг 5 на самом деле не выполняет работу, которую должен. Мы действительно не должны уменьшать z, если все пары, которые суммируют с x, являются палиндромными. Однако мы можем доказать, что этого никогда не произойдет:

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

Мы заключаем, что, если мы начнем с установки значения x, равного или превышающего 10 , у нас никогда не будет всех пар неотрицательных целых чисел, сумма которых равна x, является парами палиндромов.

Сетчатка , 135 102 байта

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

Попробуйте онлайн! Слишком медленно для n10 или более. Объяснение:

K`0

Начните с попытки 0.

"$+"{

Повторите nраз.

0L$`\d+
*__

Преобразуйте текущее пробное значение в унарное и увеличьте его.

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

Создайте все пары неотрицательных целых чисел, которые суммируются с новым пробным значением.

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

Повторите, пока существует хотя бы одна пара, содержащая два палиндромных целых числа.

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

Увеличьте и снова увеличьте пробную стоимость.

0L`\d+

Извлеките окончательное значение.

Haskell, 68 67 63 байта

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

Возвращает бесконечную последовательность.

Собирать все , nгде либо aили n-aне палиндром для всех a <- [0..n].

Попробуйте онлайн!

Perl 5 -MList::Util=any -p , 59 55 байт

-3 байта благодаря @NahuelFouilleul

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

Попробуйте онлайн!

Примечание: anyможно заменить grepи избежать -Mпереключения командной строки, но в соответствии с текущими правилами оценки, это будет стоить еще один байт.

R , 115 111 байтов

-4 благодаря Джузеппе

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]

Попробуйте онлайн!

Большая часть работы упакована в аргументы функции, чтобы убрать {}вызов функции для нескольких операторов и уменьшить скобки, необходимые для определения объектаr

Основная стратегия состоит в том, чтобы найти все палиндромы до заданной границы (включая 0), найти все попарные суммы, а затем взять n-е число, не входящее в этот вывод.

Граница n*1000была выбрана исключительно из обоснованного предположения, поэтому я призываю всех, кто доказывает / опровергает ее, как правильный выбор.

r=0:(n*1e3)вероятно, может быть улучшено с помощью более эффективной границы.

Map(paste,Map(rev,strsplit(a,"")),collapse="")оторван от ответа Марка здесь , и это просто невероятно умно для меня.

r[!r%in%outer(p,p,'+')][n]читает немного неэффективно для меня.

C # (интерактивный компилятор Visual C #) , 124 байта

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

Попробуйте онлайн!

J , 57/60 байт

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

Попробуйте онлайн!

Связанная версия добавляет 3 байта в общей сложности 60 для сохранения в качестве функции, которую может вызвать нижний колонтитул.

В REPL этого можно избежать, вызвав напрямую:

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

объяснение

Общая структура является то , что этой техникой от ответа по 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

Это сэкономило несколько байтов по сравнению с моей первоначальной техникой зацикливания, но поскольку основная функция - моя первая попытка написать J, вероятно, многое еще можно улучшить.

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 байт

°ÝDʒÂQ}ãOKIè

-3 байта благодаря @Grimy .

0 индексированные.
Очень медленно, поэтому время ожидания для большинства тестовых случаев.

Попробуйте онлайн или проверьте первые несколько случаев, удаливIè .

Намного быстрее предыдущей 15-ти битной версии:

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

1-индексироваться.

$n$

Объяснение:

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

Красный , 142 байта

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]

Попробуйте онлайн!

Возвращает n-й член, 1-индексированный

Python 3 , 107 байт

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

Попробуйте онлайн!

Инвертирование проверки палиндрома сэкономило 2 байта :)

Для справки: прямая положительная проверка (109 байт):

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 байтов

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

Какое слово для разрыва цикла? Кажется, это "уйти", верно? {k≡⌽k←⍕⍵}в п - тест на палиндром. Эта функция выше в цикле хранит весь палиндром, найденный в множестве P, если для некоторого элемента w из P такой, что iw также находится в P, это означает, что i не верно, и мы имеем приращение i. Полученные результаты:

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