Dois palíndromos não são suficientes

24

Alguns números, como , são palíndromos na base 10: se você escrever os dígitos na ordem inversa, obterá o mesmo número.14241

Alguns números são a soma de 2 palíndromos; por exemplo, ou .110=88+222380=939+1441

Para outros números, 2 palíndromos não são suficientes; por exemplo, 21 não pode ser escrito como a soma de 2 palíndromos, e o melhor que você pode fazer é 3: .21=11+9+1 1

Escreva uma função ou programa que receba uma entrada inteira ne emita o nnúmero th que não pode ser decomposto como a soma de 2 palíndromos. Isso corresponde ao OEIS A035137 .

Dígitos únicos (incluindo 0) são palíndromos.

As regras padrão para sequências se aplicam:

  • entrada / saída é flexível
  • você pode usar indexação 0 ou 1
  • você pode emitir o ntermo th, ou os primeiros ntermos, ou uma sequência infinita

(Como nota de rodapé: todos os números inteiros podem ser decompostos como a soma de no máximo três palíndromos.)

Casos de teste (indexados 1):

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

Isso é código-golfe, então a resposta mais curta vence.

Robin Ryder
fonte
2
A saída infinita também não é uma opção padrão para sequências?
String não relacionada
@UnrelatedString Sim, vou permitir isso também.
Robin Ryder
Related
Luis Mendo
2
@ Abigail Dado um número inteiro positivo n, imprima o n-ésimo membro da sequência OEIS An? Parece promissor ...
val diz Reinstate Monica
2
@Nit, vamos definir uma nova sequência OEIS como a (n) = a enésima sequência OEIS que pode ser expressa em menos caracteres do que a função Jelly com mais golfe que gera essa sequência.
agtoever 29/06

Respostas:

13

JavaScript (ES6),  93 83 80  79 bytes

Guardado 1 byte graças a @tsh

Retorna o º prazo, 1-indexados.n

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

Experimente online!

Quão?

Dado , testamos se existe tal que e são palíndromos. Se encontrarmos tal , então é a soma de dois palíndromos.n1 1knkn-kkn

O truque aqui é processar e ao mesmo tempo testando uma única string feita da concatenação de , e .kn-kkn-kk

Exemplo:

Para :n=2380

  • chegamos a ek=1441n-k=939
  • testamos a sequência " " e descobrimos que é um palíndromo14419391441

Comentado

Nota: Esta é uma versão sem eval()legibilidade.

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
}                            //
Arnauld
fonte
i=>eval("for(n=k=1;k=(s=[...k+[n-k]+k])+''!=s.reverse()?k-1||i--&&++n:++n;);n")79 bytes
tsh 27/06
Em vez de i=>eval("..."), o ES6 permite que você use i=>eval`...`, economizando 2 bytes
VFDan em
Além disso, se nenhum retorno for especificado, eval assume como padrão a última expressão avaliada, para que você possa remover o ;nno final.
VFDan 30/06
@VFDan O truque de back-tick não funciona eval()porque não coage seu argumento a uma string. A remoção ;nlevaria a um erro de sintaxe e a remoção ncausaria o retorno da função undefined.
Arnauld
12

Geléia ,  16 10  9 bytes

-1 byte graças a Erik, o Outgolfer . Produz os primeiros n termos.

2_ŒḂƇ⁺ṆƲ#

Experimente online!

Eu tentei ter uma ideia diferente em comparação com a minha abordagem original. Vamos revisar o processo de pensamento:

  • Inicialmente, o teste funcionou da seguinte forma: gerou as partições inteiras desse número, filtrou aquelas que também continham não-palíndromos e depois contou quantas listas elegíveis com o comprimento 2 existiam. Obviamente, isso não foi muito eficiente em termos de tamanho do código.

  • A geração das partições inteiras de N e a filtragem tiveram duas principais desvantagens: eficiência de duração e tempo. Para resolver esse problema, pensei em primeiro criar um método para gerar apenas os pares de números inteiros (x,y) que somam N (nem todas as listas de comprimento arbitrário) com a condição de que ambos os números sejam palíndromos.

  • Mas, ainda assim, eu não estava satisfeito com a "maneira clássica" de fazer isso. Troquei de abordagem: em vez de gerar pares , vamos focar o programa em palíndromos individuais . Dessa forma, pode-se simplesmente calcular todos os palíndromos x abaixo de N , e se N-x também é palíndromo, então estamos prontos.

Código Explicação

2_ŒḂƇ⁺ṆƲ # - Link monádico ou programa completo. Argumento: n.
2 # - A partir de 2 * , encontre os primeiros n números inteiros que satisfazem ...
 _ŒḂƇ⁺ṆƲ - ... o link auxiliar. Divisão (chame o número inteiro atual N):
    Filter - Filtro. Cria o intervalo [1 ... N] e mantém apenas aqueles que ...
  ŒḂ - ... são palíndromos. Exemplo: 21 -> [1,2,3,4,5,6,7,8,9,11]
 _ - Subtraia cada um desses palíndromos de N. Exemplo: 21 -> [20,19, ..., 12,10]
     ⁺ - Duplique o link anterior (pense nele como se houvesse um additional adicional)
            em vez de ⁺). Isso mantém apenas os palíndromos nesta lista.
            Se a lista não estiver vazia, significa que encontramos um par (x, Nx) que
            contém dois palíndromos (e obviamente x + Nx = N, então eles somam N).
      NOT - NOT lógico (estamos procurando os números inteiros para os quais esta lista está vazia).
       Group - Agrupe os últimos 4 links (basicamente faça _ŒḂƇ⁺Ṇ agir como uma única mônada).

* Qualquer outro dígito diferente de zero funciona, nesse caso.

Mr. Xcoder
fonte
7

Gelatina , 11 bytes

⁵ŻŒḂ€aṚ$EƲ#

Experimente online!

O programa completo funciona aproximadamente assim:

  1. Defina z para a entrada.
  2. Defina x como 10 .
  3. Defina R para [] .
  4. Para todo número k de 0 até x incluindo x , verifique se k e x - k são palíndricos.
  5. Se todos os elementos de L forem iguais (ou seja, se todos os pares possíveis que somam x tiverem ambos os elementos palindrômicos, ou todos esses pares tiverem no máximo um de seus elementos palindrômicos), defina z como z - 1 e acrescente x para R .
  6. Se z = 0 , retorne R e termine.
  7. Defina x como x + 1 .
  8. Vá para o passo 4.

Você pode suspeitar que a etapa 5 não faz o trabalho que deveria. Realmente não deveríamos decrementar z se todos os pares que somam x são palíndricos. No entanto, podemos provar que isso nunca acontecerá:

Vamos primeiro escolher um número inteiro k para que 10kx . Sempre podemos fazer isso, porque, na etapa 2, inicializamos x para ser 10 .

Se k não é um palíndromo, então temos o par (k,x-k) , onde k+(x-k)=x , portanto, nem todos os pares têm dois palíndromos.

Se, por outro lado, k é um palíndromo, então podemos provar que k-1 1 não é um palíndromo. Deixe os primeiros e últimos dígitos de k ser DF e Deu respectivamente. Como k é um palíndromo, DF=Deu>0 0 . Deixe os primeiros e últimos dígitos de k-1 1 seja DF e Deu , respectivamente. Como Deu>0 0 , Deu=DF-1 1DF . Portanto,k-1 1 não é um palíndromo e temos o par(k-1 1,x-(k-1 1)) , onde(k-1 1)+(x-(k-1 1))=k-1 1+x-k+1 1=x .

Concluímos que, se começarmos com a configuração x para um valor maior ou igual a 10 , nunca poderemos ter todos os pares de números inteiros não negativos que somam x serem pares de palíndromos.

Erik, o Outgolfer
fonte
Ah, bata em mim também - os primeiros n termos economizam 1 byte (fui para o STDIN eŻŒḂ€aṚ$Ṁ¬µ#
Jonathan Allan
@JonathanAllan Oh LOL não esperava isso. Enfim, alguém nos venceu. : D
Erik the Outgolfer
(10,x-10)10
11
3

Retina , 135 102 bytes

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

Experimente online! Muito lento para n10 ou mais. Explicação:

K`0

Comece tentando 0.

"$+"{

Repita os ntempos.

0L$`\d+
*__

Converta o valor de avaliação atual em unário e aumente-o.

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

Crie todos os pares de números inteiros não negativos que totalizem o novo valor de avaliação.

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

Repita enquanto existir pelo menos um par contendo dois números inteiros palindrômicos.

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

Incremente e expanda o valor da avaliação novamente.

0L`\d+

Extraia o valor final.

Neil
fonte
3

Haskell, 68 67 63 bytes

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

Retorna uma sequência infinita.

Colete tudo nonde aou n-anão é um palíndromo para todos a <- [0..n].

Experimente online!

nimi
fonte
3

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

-3 bytes graças a @NahuelFouilleul

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

Experimente online!

Nota: anypoderia ser substituído por grepe evitar a -Mopção de linha de comando, mas sob as regras de pontuação atuais, isso custaria mais um byte.

Xcali
fonte
pequena melhoria, -3bytes , usando enquanto em vez de refazer
Nahuel Fouilleul 27/06
E tirou mais um disso eliminando o +depois do while.
Xcali
3

R , 115 111 bytes

-4 graças a 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]

Experimente online!

A maior parte do trabalho é compactada nos argumentos da função para remover a {}chamada de função de várias instruções e reduzir os colchetes necessários na definição do objetor

A estratégia básica é encontrar todos os palíndromos até um determinado limite (incluindo 0), encontrar todas as somas aos pares e pegar o n-ésimo número que não estiver nessa saída.

O limite de n*1000foi escolhido puramente a partir de um palpite, portanto encorajo qualquer pessoa a provar / refutar como uma opção válida.

r=0:(n*1e3)provavelmente pode ser melhorado com um limite mais eficiente.

Map(paste,Map(rev,strsplit(a,"")),collapse="")é arrancado da resposta de Mark aqui e é incrivelmente inteligente para mim.

r[!r%in%outer(p,p,'+')][n]lê um pouco ineficiente para mim.

CriminallyVulgar
fonte
11
111 bytes apenas reorganizando algumas coisas.
Giuseppe
1

J , 57/60 bytes

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

Experimente online!

A versão vinculada adiciona 3 bytes para um total de 60 para salvar como uma função que o rodapé pode chamar.

No REPL, isso é evitado chamando diretamente:

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

Explicação

A estrutura geral é a dessa técnica, a partir de uma resposta 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

Isso economizou alguns bytes em relação à minha técnica de loop original, mas como a função principal é minha primeira tentativa de escrever J, provavelmente ainda há muito que pode ser aprimorado.

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.
0xfordcomma
fonte
Esse é um antigo formato meu, que combina outros truques que aprendi desde então produz uma solução de 41 caracteres:1&(_:1&((e.((*&(-:|.)&":"0>:)&i.-))+])+)*
miles
1

05AB1E , 15 12 bytes

°ÝDʒÂQ}ãOKIè

-3 bytes graças a @Grimy .

Indexado a 0.
Muito lento, então o tempo limite para a maioria dos casos de teste.

Experimente online ou verifique os primeiros casos removendo o .

Versão anterior muito mais rápida de 15 bytes:

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

1 indexado.

n

Explicação:

°Ý              # 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)
Kevin Cruijssen
fonte
11
12: °LDʒÂQ}ãOKIè(provavelmente existe um limite superior melhor que 10 ^ x para velocidade). Eu acho que ∞DʒÂQ}ãOKé tecnicamente um 9, mas atinge o tempo limite antes da primeira saída.
Grimmy 03/07
@Grimy Não tenho certeza se o produto cartesiano funciona preguiçosamente carregado em listas infinitas. De qualquer forma, quanto aos 12 byter, infelizmente está incorreto. Ele filtra números inteiros que podem ser formados somando 2 palíndromos, mas não números inteiros que são palíndromos. Sua sequência (sem o final ) é assim: [1,21,32,43,54,65,76,87,98,111,131,141,151,...]mas deve ser assim [*,21,32,43,54,65,76,87,98,201,1031,1041,1051,1052,...](o primeiro 1/ *pode ser ignorado, pois usamos a entrada indexada em 1).
Kevin Cruijssen 03/07
11
@Grimy Hmm, acho que uma correção direta está mudando a lista baseada em 1 para baseada Lem 0 .. :)
Kevin Cruijssen 03/07
0

Vermelho , 142 bytes

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]

Experimente online!

Retorna o n-ésimo termo, 1 indexado

Galen Ivanov
fonte
0

Python 3 , 107 bytes

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

Experimente online!

A inversão da verificação do palíndromo salvou 2 bytes :)

Para referência, o cheque positivo direto (109 bytes):

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
movatica
fonte
0

APL (NARS), 486 bytes

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

Qual é a palavra para quebrar o ciclo? Parece que é ": sai", certo? {k≡⌽k←⍕⍵}em p é o teste para o palíndromo. Essa função acima no loop armazena todo o palíndromo encontrado no conjunto P, se para algum elemento w de P for tal que iw esteja em P também, isso significa que i não está certo e temos incremento i. Resultados:

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