Introdução (pode ser ignorado)

Colocar todos os números positivos em sua ordem regular (1, 2, 3, ...) é um pouco chato, não é? Então, aqui está uma série de desafios em torno de permutações (reorganizações) de todos os números positivos. Este é o terceiro desafio desta série (links para o primeiro e o segundo desafios).

Neste desafio, organizaremos os números naturais em linhas de comprimento crescente, de forma que a soma de cada linha seja primo. O que eu acho realmente incrível nisso é que todo número natural tem um lugar nesse arranjo. Nenhum número é ignorado!

Essa visualização desse arranjo é assim:

row             numbers             sum
1                  1                  1
2                2   3                5
3              4   5   8             17
4            6   7   9  15           37
5          10 11  12  13  21         67
6        14  16 17  18  19  23      107
etc.

Podemos ler os elementos das linhas neste triângulo. Os primeiros 20 elementos são: 1, 2, 3, 4, 5, 8, 6 , 7, 9, 15, 10, 11, 12, 13, 21, 14, 16, 17, 18, 19 ( sim, existe uma música do New Order oculta nesta sequência ).

Como esse é um desafio de "sequência pura", a tarefa é gerar $a(n)$ para um dado $n$ como entrada, onde $a(n)$ é A162371 .

Tarefa

Dada uma entrada inteira $n$ , imprima $a(n)$ no formato inteiro.

$a(n)$ é definida como o$n$ ésimo elemento do lexicograficamente primeiros permutação dos números naturais de tal modo que, quando visto como um triângulo lido por linhas, para n> 1 as somas de linhas são números primos. Desde a primeira permutação lexicográfico de números inicia naturais com 1,$a(1)$ é 1. Note-se que por esta definição$a(1) = 1$ e$a(1)$ énãonecessário para ser nobre. Esta é a sequência OEISA162371.

Nota: a indexação baseada em 1 é assumida aqui; você pode usar a indexação baseada em 0; portanto, $a(0) = 1; a(1) = 2$ , etc. Por favor mencione isso na sua resposta se você optar por usá-lo.

Casos de teste

Input | Output
---------------
1     |  1
5     |  5
20    |  19
50    |  50
78    |  87
123   |  123
1234  |  1233
3000  |  3000
9999  |  9999
29890 |  29913

Regras

• Entrada e saída são números inteiros (seu programa deve, pelo menos, suportar entrada e saída no intervalo de 1 a 32767)
• Entrada inválida (0, valores flutuantes, seqüências de caracteres, valores negativos etc.) pode levar a resultados imprevisíveis, erros ou comportamento (não) definido.
• Regras de E / S padrão se aplicam.
• As brechas padrão são proibidas.
• Isso é código-golfe , então as respostas mais curtas em bytes ganham

Geléia , 32 bytes

;®»ṀƊSÆn_S
ẎṀ©+LRḟẎḣL;Ç$ṭ
1Ç¡Fị@

Experimente online! - muito lento, pois constrói n linhas primeiro, para uma versão mais rápida que não tenta , a 37 bytes.

Perl 6 , 80 bytes

{({$!=@_;+(1...{$_∉$!&&(|$!,$_).rotor(1..*).one.sum.is-prime-1})}...*)[$_]}

Experimente online!

Explicação:

{                                  }  # Anonymous code block
 (                        ...*)[$_]   # Index into the infinite sequence
  {                      }   # Where each element is
   $!=@_;  # Save the list of previous elements into $!
   +(1...{             })    # Return the first number that
          $_∉$!         # Has not appeared in the list so far
          &&            # And
          (|$!,$_)      # The new sequence
          .rotor(1..*)  # Split into rows of increasing length
                        # And ignoring incomplete rows
          .one          # Have exactly one row
          .sum          # Where the sum
          .is-prime-1   # Is not prime (i.e. just the first row)

Haskell , 122 120 bytes

import Data.Numbers.Primes
l%a|(p,q)<-splitAt l a,(s,k:t)<-span(not.isPrime.(+sum p))q=p++k:(l+1)%(s++t)
((1:1%[2..])!!)

Experimente online! (possui 2 bytes extras para f=)

Edição: agora usa indexação baseada em 0 para salvar 2 bytes. Obrigado @wastl por apontar isso, devo ter perdido no OP.

Foi muito divertido escrever! A função auxiliar %tem um comprimento le uma lista de valores que pode ser usada a. Retorna uma lista infinita de valores para a sequência. O comprimento é um a menos que o comprimento da linha atual do triângulo e a lista é infinita e pré-classificada. Primeiro, apenas produzimos os primeiros lvalores de ae depois examinamos o restante de a até encontrarmos o primeiro (menor) valor que torna a soma principal. Nós dividimos a lista em torno desse valor usando spane alguma correspondência de padrões. Agora, tudo o que precisamos fazer é gerar esse novo valor e retornar com o próximo comprimento de linha l+1e os valores restantes em a. Para o resultado final, anexamos 1 (caso especial para n = 0) e indexamos nele com !!.

JavaScript (ES6),  111  110 bytes

n=>{for(g=n=>{for(d=n;n%--d;);},i=l=0;i--||(k=s=0,i=l++),n--;g[k]=s+=r=k)for(;g[++k]|g(!i*++s)|d>1;);return r}

Experimente online!

Gelatina , 46 bytes

S©‘æR®Ḥ‘¤_®ḟ;F¥Ṃ
FLḤRḟFḣ0ịLƊ;祵W
1;Ç$⁸½Ḥ¤¡Fị@

Experimente online!

O tempo limite é excedido, mas funciona lá para todos, exceto os dois últimos exemplos.

Lua , 242 228 226 211 bytes

s={}u={}i=0 n=0+...while i<n do
n=n-i
x,S=1,0
for j=1,i do
while u[x]do x=x+1 end
s[j]=x
S=S+x
u[x]=0
end
while u[x]or p do
x=x+1
d=S+x
p=F
for c=2,d-1 do
p=p or d%c<1
end
end
i=i+1
s[i]=x
u[x]=0
end
print(s[n])

Experimente online!