Começamos com uma sequência indexada em branco 1:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,...

Na ^nésima etapa, preenchemos todos os espaços em branco a (n) com números inteiros maiores que 1 começando no primeiro espaço em branco restante, onde a (n) é a ^nésima entrada da sequência.

Após o primeiro passo:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,...

Observe que a (1) deve ser 2 porque o primeiro número inteiro maior que 1 é 2.

Na segunda etapa, preenchemos todos os a (2) espaços em branco. Será evidente que a (2) deve ser 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,...

Na terceira etapa, preenchemos todos os a (3) espaços em branco. A partir da sequência, a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,...

Na quarta etapa, preenchemos todos os a (4) espaços em branco. A partir da sequência, a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,...

Eventualmente:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,...

Tarefa

Dado n, retorne o n- ^ésimo elemento da sequência.

Os primeiros 10.000.000 de termos da sequência podem ser encontrados aqui .

Isso é código-golfe . A resposta mais curta em bytes vence. Aplicam-se brechas padrão .

Haskell , 80 67 bytes

g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m

Experimente online!

Haskell é a linguagem perfeita para definir uma lista infinita em termos de si mesma.

C, 123 bytes

f(n){int*p=calloc(n,4),i=0,j,k;for(*p=p[1]=2;i<n;++i)for(j=0,k=i/2?0:2-i;j<n;++j)p[j]||k++%p[i]||(p[j]=k/p[i]+2);n=p[n-1];}

Experimente online!

Passo a passo

f(n){int*p=calloc(n,4),

Aloque uma matriz de n números inteiros para armazenar os primeiros n elementos da sequência. Isso codifica sizeof(int)como 4, que é uma suposição segura na maioria dos casos e certamente uma que estou disposto a fazer no contexto do código de golfe. :)

i=0,j,k;

Estes são todos os contadores: ipara o índice da etapa em que estamos, jpercorrer a sequência procurando por espaços vazios e kcontar quantos espaços vazios foram vistos.

for(*p=p[1]=2;i<n;++i)

Antes de iniciarmos nosso loop principal, nos esgueiramos na inicialização dos dois primeiros elementos da sequência para 2. ( p[0]= *(p + 0)= *p.) Isso joga fora a contagem para k, porém, mas ...

for(j=0,k=i/2?0:2-i;j<n;++j)

... também fazemos uma inicialização sorrateira de k, que testa para ver se ié menor que 2e corrige o valor inicial de kse for. O loop interno também começa aqui, que itera toda a sequência até o momento durante cada etapa.

p[j]||k++%p[i]||(p[j]=k/p[i]+2);

Essa linha poderia realmente usar algumas explicações. Podemos expandir isso para:

if (!(p[j] || ((k++) % p[i]))) {
    p[j] = k / p[i] + 2;
}

por curto-circuito e, em seguida, pelas leis de De Morgan e pelo fato de 0ser falso em C:

if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
}

Isso basicamente afirma: "se esse espaço estiver vazio, aumente k. E se kanteriormente era um múltiplo do tamanho da etapa, execute a seguinte instrução". Portanto, executamos a instrução em todos os elementos de tamanho de etapa , que é exatamente como a sequência é descrita. A afirmação em si é simples; Tudo que faz é gerar 2, 3, 4, ....

n=p[n-1];}

Usando o complicado-return-sem-um-retorno que funciona com gcc, nós "devolver" o último elemento dos primeiros n termos na seqüência, que passa a ser o n º prazo.

Pitão, 29 bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1

Experimente online

Como funciona

Em vez de brincar com listas, isso usa uma fórmula recursiva simples.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input())))

Haskell , 67 bytes

0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j<i]
f=(%1).pred

Experimente online!

Uma solução aritmética recursiva que resultou basicamente no mesmo método da resposta Pyth de Anders Kaseorg .

Esse código é coberto de verrugas - partes feias que parecem poder ser jogadas fora, mas eu não vi como.

A função i%jrealmente deseja usar uma proteção para verificar se mod i(f j)>0e avaliar uma das duas expressões correspondentes. Mas, ambas as expressões usam div i(f j). Vincular isso a um guarda não o fará aplicar aos dois lados. Tanto quanto eu sei, um guarda não pode ser feito para "distribuir" sobre outros guardas. lete wheresão muito longos. Portanto, o código usa lastpara escolher uma das duas expressões enquanto o guarda vincula a variável. Ugh.

Idealmente, usaríamos divModporque the dive modsão usados, mas (d,m)<-divMod ...é uma expressão longa. Em vez disso, verificamos hackilymente que o mod é diferente de zero, verificando se o divvalor vezes o divisor fica aquém do valor original.

O 0%j=2caso não seria necessário se Haskell tivesse um curto-circuito div 0, o que não acontece. O .predconverte a entrada indexada em 1 em indexada a zero, ou então haverá -1correções em todos os lugares.

JavaScript (ES6), 98 93 91 bytes

Uma função recursiva que para assim que o resultado está disponível.

f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Versão alternativa, 90 bytes

Sugerido por Shaggy para -1 byte

Este deve ser chamado com f(n)(). Embora o post correspondente na meta atualmente dê uma pontuação positiva, essa sintaxe é aparentemente contestada.

n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Demo

f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

for(n = 1; n <= 50; n++) {
  console.log('a[' + n + '] = ' + f(n));
}

Java 8, 124 bytes

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];}

Expressão lambda.

Cria uma matriz inteira e a preenche continuamente até o enésimo valor ser preenchido.

Pré-declarar variáveis ​​na parte superior para reduzir o maior número possível de declarações, pois cada uma intcusta 4 bytes de espaço em vez de adicionar ,n2.

Na j'ª iteração do cálculo, o número de' espaços em branco 'que é necessário pular é igual a a[j](ou 2, se estiver em branco). Conclui que, se o primeiro espaço em branco que precisamos preencher estiver na posição k, k * a[j]nos dará o 'passo' ( s).