Considere a seguinte sequência:

0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...

Parece bastante sem padrão, certo? Aqui está como isso funciona. Começando com 0, salte nnúmeros inteiros, niniciando em 1. Esse é o próximo número na sequência. Em seguida, acrescente os números "ignorados" e que ainda não foram vistos em ordem crescente. Em seguida, incremente ne pule do último número anexado. Repita esse padrão.

Então, por exemplo, quando chegamos 11, chegamos n=5. Aumentamos npara ser n=6, saltamos para cima e 17, em seguida, acrescentamos, 13 14 15 16pois eles ainda não foram vistos. Nosso próximo salto é n=7, então o próximo elemento na sequência é 23.

O desafio

Com base na entrada x, imprima o xtermo th desta sequência, os primeiros xtermos da sequência ou crie uma lista infinita dos termos da sequência. Você pode escolher a indexação 0 ou 1.

E / S e regras

• A entrada e saída podem ser fornecidas por qualquer método conveniente .
• Pode-se presumir que a entrada e a saída se encaixam no tipo de número nativo do seu idioma.
• Um programa completo ou uma função são aceitáveis. Se uma função, você pode retornar a saída em vez de imprimi-la.
• As brechas padrão são proibidas.
• Isso é código-golfe, portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.

JavaScript (ES7), 41 bytes

Retorna o n-ésimo termo da sequência, indexada em 0.

n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2

Experimente online!

Quão?

Caso principal: $n > 3$

Os quatro primeiros termos da sequência são especiais, então vamos colocá-los de lado por enquanto.

Para , a sequência é assim:$n > 3$

 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...

Podemos notar que, de fato, existem duas sub sequências intercaladas:

• A maioria dos valores pertence à sub-sequência para a qual simplesmente temos:$A$

  $$A(n) = n - 1$$

• Alguns outros valores pertencem à sub-sequência (destacada entre colchetes no diagrama acima) cujos índices seguem a sequência aritmética 3, 3, 4, 6, 9, 13, 18, 24 ... e para a qual temos:$B$

  $$B(n,k) = n + k - 1$$

  onde é o índice da sequência principal e k é o índice da sub-sequência B .$n$$k$$B$

Os índices de na sequência principal são dados por:$B$

Dado , sabemos que o termo correspondente na sequência principal pertence a B se n for uma solução inteira da equação quadrática:$n$$B$$n$

cujo discriminante é:

e cuja solução positiva é:

Esperamos para ser um número inteiro. Daí o teste:$\sqrt{\Delta}$

(d = (n-- * 8 - 23) ** .5) % 1

Casos especiais: $0 \le n \le 3$

Para , o discriminante é negativo e obtém sua raiz quadrada em NaN . Para n = 3 , o discriminante é 1 . Portanto, estas quatro primeiros termos da sequência são considerados como pertencendo à sub-sequência B .$n < 3$$n = 3$$1$$B$

Se apenas aplicarmos a fórmula padrão n - ~ d / 2 , obteremos:

ao invés de:

É por isso que nós XOR esses resultados com respectivamente.$0,1,2\text{ and }1$

Casca , 12 bytes

Θṁṙ_1C+ḣ2tNN

Experimente online!

Saída como uma lista infinita. Aqui é uma versão que imprime o primeiro N .

Explicação

C_1C + ḣ2tNN - Programa completo. Não recebe entrada, sai para STDOUT.
         tN - Construa a lista infinita de números naturais, começando em 2.
      + ḣ2 - E acrescente [1, 2] a ele. Rendimentos [1,2,2,3,4,5,6,7,8,9,10,11, ...].
     CN - Corte a lista infinita de números inteiros positivos em pedaços daqueles
               tamanhos. Rendimentos [[1], [2,3], [4,5], [6,7,8], [9,10,11,12], ...].
 Map - Mapeie e aplane os resultados posteriormente.
  ṙ_1 - Gire cada um para a direita em 1 unidade.
               Rendimentos [1,3,2,5,4,8,6,7,12,9,10,11, ...]
Θ - Anexar a 0. Rendimentos [0,1,3,2,5,4,8,6,7,12,9,10,11, ...]

Haskell , 43 bytes

0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)

Experimente online!

Define uma lista infinita:

  0:1:3:2:(5!3)
≡ 0:1:3:2:5:4:(8!4)
≡ 0:1:3:2:5:4:8:6:7:(12!5)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:(17!6)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:17:13:14:15:16:(23!7) …

Gelatina , 15 bytes

+‘ɼṪRṙ-œ|@
0Ç¡ḣ

Este é um programa completo que, dado n , imprime os primeiros n itens da sequência.

Experimente online!

Como funciona

0Ç¡ḣ        Main link. Argument: n

0           Set the return value to 0.
 Ç¡         Call the helper link n times, first with argument 0, then n-1 times
            with the previous return value as argument.
   ḣ        Head; extract the first n items of the last return value.


+‘ɼṪRṙ-œ|@  Helper link. Argument: A (array)

 ‘ɼ         Increment the value in the register (initially 0) and yield it.
+           Add that value to all items in the sequence.
   Ṫ        Tail; extract the last item.
    R       Range; map k to [1, .., k].
     ṙ-     Rotate -1 units to the left, yielding [k, 1, ..., k-1].
       œ|@  Perform multiset union of A and the previous return value.

C (gcc), 73 67 64 bytes

t,d;f(x){for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);t=x<4?x^x/2:x-1;}

Experimente online!

Define uma função fque recebe indexação 0 ne produz o nnúmero th na sequência.

Podemos analisar a sequência da seguinte maneira:

f(n)  = n   where n = 0, 1

f(2)  = 3   // 2 and 3 are swapped
f(3)  = 2

f(4)  = 5   // (+2,+3)
f(6)  = 8   // (+3,+4)
f(9)  = 12  // (+4,+5)
f(13) = 17  // (...)
...

f(n)  = n-1 // for all cases not yet covered

Primeiro, lidamos com a seção do meio:

for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);

Observe que os argumentos à esquerda (4, 6, 9, 13, ...) seguem um padrão: primeiro adicione dois, depois adicione três, depois adicione quatro e assim por diante. Começamos em t=4e adicionamos d(que começa em 2) a cada iteração do loop, incrementando do processo.

O corpo do loop é mais interessante. Lembre-se de que queremos mapear 4 a 5, 6 a 8, 9 a 12, etc .; isso é apenas adicionar d-1se xfor t. No entanto, essa lógica vem antes do último caso, f(n) = n - 1então sabemos que vamos subtrair 1 no final. Portanto, podemos simplesmente adicionar dif x == t( x-t||(x+=d)). No entanto, também terá de sair do loop imediatamente após este - então adicionamos que para dobter o absurdo de aparência d+=x+=d, que vai sempre fazer a d<xcondição falhar.

Isso cobre tudo, exceto os quatro primeiros valores. Olhando para eles em binário, obtemos:

00 -> 00
01 -> 01
10 -> 11
11 -> 10

Então, queremos virar o último bit se 2 <= x < 4. Isso é realizado com x^x/2. x/2fornece o segundo bit menos significativo; portanto, XORing com o número original inverte o último bit se o número for 2 ou 3.

Geléia ,  13  10 bytes

-3 Agradecimentos a Dennis (use a indexação 0 para salvar 2 da configuração da soma cumulativa e um decréscimo final)

Ḷ»2Äi+_>2$

Um link monádico que aceita um número inteiro, n indexado a 0 , que retorna um número inteiro, a (n)

Experimente online! Ou veja uma suíte de testes

Perl 5 com -pl, 70 bytes

$"="|";push@f,$;=$f[-1]+$-++,grep!/^(@f|$;)$/,0..$;for 0..$_;$_=$f[$_]

Experimente online!

MATL , 22 bytes

1y:"t0)@+h5M:yX-h]qw:)

Emite o primeiro n termos da sequência.

Experimente online!

Explicação

1         % Push 1
y         % Implicit input: n. Duplicate from below
":        % For each k in [1 2 ... n]
  t0)     %   Duplicate sequence so far. Get last entry, say m
  @+      %   Add k: gives m+k
  h       %   Concatenate horizontally
  5M      %   Push m+k again
  :       %   Range [1 2 ... m+k]
  y       %   Duplicate from below
  X-      %   Set difference
  h       %   Concatenate horizontally
]         % End
q         % Subtract 1, element-wise
w         % Swap. Brings original copy of n to the top
:)        % Keep the first n entries. Implicit display

Haskell , 51 bytes

0:1:do(a,b)<-zip=<<(1:)$scanl(+)3[2..];b:[a+1..b-1]

Experimente online!

Um pouco mais do que a resposta de Lynn Haskell , mas a abordagem diferente pode ser interessante, no entanto.

Ruby , 73 bytes

f=->x,l,n{!l[x]&&(i=l[-1];f[x,l+[i+n]+([*(i+1...i+n)]-l),n+1])||l[0...x]}

Experimente online!

Função recursiva que retorna os primeiros x números da lista.

QBasic, 58 bytes

DO
b=r+j
?b
r=b
FOR x=a+1TO b-1
?x
r=x
NEXT
a=b
j=j+1
LOOP

Saídas indefinidamente. Você pode adicionar um SLEEP 1loop interno ou torná-lo LOOP WHILE b<100ou algo parecido para ver os resultados.

Isso basicamente implementa apenas as especificações. Observe que os números para os quais voltamos sempre serão os números entre o número saltado mais recentemente e o número saltado anterior a ele. Então, nós armazenar esses limites como ae be usar um FORloop para imprimir todos os números entre eles.

05AB1E , 14 bytes

0)sƒ¤N+LÁ«}Ùs£

Experimente online!

R , 70 bytes

function(e){for(i in 1:e)F=c(setdiff((F+i):1-1,F),F[1]+i,F);rev(F)[e]}

Experimente online!

• Indexado 1
• -4 bytes usando F constantes graças à sugestão @JAD
• -5 bytes invertendo a lista, graças à sugestão de @ Giuseppe
• -2 bytes removendo chaves inúteis no loop for graças à sugestão do @JAD
• -2 bytes usando em setdiffvez dex[x %in% y]

Versão anterior (79 bytes)

Python 2 , 123 bytes

def f(z):[s.extend([s[-1]+n]+[x for x in range(s[-1]+1,s[-1]+n)if not x in s]) for n in range(1,z)if len(s)<z];return s    

Experimente online!

Dada a entrada x, imprima os primeiros x termos da sequência,

Estou aprendendo Python e esses desafios tornam as coisas mais interessantes.

Edit: raspar algum espaço em branco

Gelatina , 16 bytes

RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ

Experimente online!

Um byte a mais do que a resposta Jelly existente, mas isso poderia ser um pouco de golfe. RÄṬŻk²Ḋ$talvez possa ser mais curto.

18 bytes

RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ

Mais longo, mas diferente.

Ruby , 63 bytes

->x,n=0{n+=1while 0>d=n*n+n<=>2*x-6;[0,1,3,2][x]||[x+n,x-1][d]}

Experimente online!

Indexado a 0. Provavelmente pode ser jogado para baixo.

Perl 6 , 52 bytes

(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)

Experimente online!

Esta é uma expressão de gerador usando o ...operador Ele procura lacunas na sequência anterior @_por meio de ((^max @_)∖@_).min.?key:

      @_  # prior sequence values         [0,1,3]
  max @_  # largest prior sequence value       3
 ^        # the Range 0..max @_            0,1,2
(       )∖@_  # set subtract prior seq     -0,1  -> (2=>True)
            .min  # smallest unseen value  2=>True
                .?key  # set yields pairs  2

O ?é necessário para o valor inicial que não possui a .key. Se nenhuma lacuna for encontrada, ele adicionará n (aqui na $variável) ao último valor da lista, mais um por 0 erros.

Python 3 , 104 bytes

def f(x):
 n=a=0
 l=list(range(x*x))
 while n<x:print(l[a+n],*l[a+2-(n<3):a+n],end=' ');a=a+n-(a>0);n+=1

Experimente online!

Dada a entrada x, produza as primeiras x "sequências"