Definição

Vamos chamar uma sequência inteira (infinita) de universal se ela contiver toda sequência inteira finita como uma subsequência contígua.

Em outras palavras, a sequência inteira (a ₁ , a ₂ ,…) é universal se e somente se, para cada sequência inteira finita (b ₁ ,…, b _n ) , existe um deslocamento k tal que (a _{k + 1} ,…, A _{k + n} ) = (b ₁ ,…, b _n ) .

A sequência de números primos positivos, por exemplo, não é universal, entre outros pelos seguintes motivos.

• Não contém números inteiros negativos, 1 ou números compostos.

• Embora contenha 3 , não contém a subsequência contígua (3, 3, 3) .

• Embora contenha 2 e 5 , não contém a subsequência contígua (2, 5) .

• Embora contenha a subsequência contígua (7, 11, 13) , não contém a subsequência contígua (13, 11, 7) .

Tarefa

Escolha qualquer sequência inteira universal única (a ₁ , a ₂ ,…) e implemente-a na linguagem de programação de sua escolha, respeitando as seguintes regras.

• Você pode enviar um programa completo ou uma função.

• Você tem três opções para E / S:

  1. Não faça nenhuma entrada e imprima ou retorne a sequência inteira.

  2. Pegue um índice n como entrada e imprima ou retorne um _n .

  3. Pegue um índice n como entrada e imprima ou retorne (a ₁ ,…, a _n ) .

• Para as opções de E / S 2 e 3 , você pode usar a indexação baseada em 0, se preferir.

• Seu envio deve ser determinístico: se executado várias vezes com a mesma entrada, deve produzir a mesma saída.

Além disso, a menos que seja imediatamente óbvio, prove que a sequência que você escolheu é universal. Sua prova pode não depender de conjecturas não comprovadas.

Aplicam-se as regras padrão de código de golfe . Que ganhe o código mais curto em bytes!

Casca , 5 bytes

Isso imprime uma lista infinita

ΣṖ…ݱ

Experimente online! ou encontre o primeiro índice da sua sequência . (Leva muita memória para a maioria das seqüências)

Explicação:

   ݱ   Infinite list [1,-1,2,-2,3,-3,4,-4,5,-5...]
  …     Rangify       [1,0,-1,0,1,2,1,0,-1,-2,...]
 Ṗ      Powerset
Σ       Concatenate

Em Husk Ṗse comporta bem para listas infinitas. Você pode ver o seu comportamento aqui

Python 2 , 49 46 43 bytes

def f(n):d=len(`n`);return n/d**(n%d)%d-d/2

f(n)retorna um _n apenas. Isso usa o menor dígito de nna base dpara extrair um dos dígitos mais altos.

Experimente online! Esse script (cortesia de Dennis) pega qualquer sequência finita e mostra nonde essa sequência começa.

Explicação

n/d**(n%d)%d-d/2
     (n%d)         least significant digit of n
n/d**(   )%d       get n%d-th digit of n
            -d/2   offset to get negative values

Por exemplo, para nna faixa 3141592650de 3141592659, d=10e o último dígito do nSelecciona um dos outros dígitos. Em seguida, adicionamos -d/2para obter valores negativos.

n%d:       0  1  2  3  4  5  6  7  8  9
f(n)+d/2:  0  5  6  2  9  5  1  4  1  3
f(n):     -5  0  1 -3  4  0 -4 -1 -4 -2

Alternativa autônoma, também 43 bytes:

n=input();d=len(`n`);print n/d**(n%d)%d-d/2

Braquilog 2, 11 bytes

≜~×-₂ᵐ~ȧᵐ≜∋

Experimente online!

Eu também tentei um algoritmo usando partições aditivas em uma lista, mas não foi mais curto. Este é um gerador que produz um fluxo infinito de números inteiros como saída; o link do TIO possui um cabeçalho para imprimir os dez mil primeiros.

Explicação

O programa inicia tentando todos os números possíveis em sequência ( ≜tenta todas as possibilidades restantes, para números inteiros por padrão). Isso é 0, 1, -1, 2, -2, etc. (embora os números inteiros negativos não cheguem ao final do programa). Este é o único passo "infinito" do programa; todos os outros são finitos.

~×depois gera todas as possíveis fatorações do número inteiro, tratando diferentes ordens como diferentes e usando apenas valores de 2 para cima (portanto, existem apenas finitas); observe que números compostos são permitidos na fatoração, não apenas números primos. Isso significa que todas as seqüências possíveis de números inteiros ≥ 2 serão geradas por esta etapa em algum momento da execução da função (como tal sequência necessariamente possui algum produto e esse produto será gerado em algum momento pela inicial ≜).

Precisamos, então, mapear o conjunto dessas seqüências para o conjunto de todas as seqüências inteiras, o que é feito em duas etapas: subtraindo 2 ( -₂) de cada elemento ( ᵐ), fornecendo o conjunto de todas as sequências inteiras não-negativas e, em seguida, recebendo mais ou menos ( ~ȧ, ou seja, "um valor cujo valor absoluto é") cada elemento (ᵐ) O último passo é obviamente não determinístico, então Brachylog o trata como um gerador, gerando todas as listas possíveis cujos elementos são mais ou menos o elemento correspondente da lista de entrada. Isso significa que agora temos um gerador para todas as seqüências inteiras possíveis e as gera em uma ordem que significa que todas são geradas (especificamente, a ordem que você obtém se usar o valor absoluto de cada elemento, adicione 2 a cada e, em seguida, faça o pedido pelo produto dos elementos resultantes).

Infelizmente, a pergunta quer uma única sequência, não uma sequência de sequências, por isso precisamos de mais dois comandos. Primeiro, ≜solicita ao Brachylog que gere explicitamente a sequência de sequências estritamente (em vez de produzir uma estrutura de dados descrevendo o conceito de uma sequência gerada por esse método, e não gerando as seqüências até que seja necessário); isso acontece para acelerar o programa nesse caso e garante que a saída seja produzida na ordem solicitada. Finalmente, ∋faz com que o gerador produza os elementos das sequências individuais, um de cada vez (passando para a próxima sequência, uma vez que todos os elementos da anterior são gerados).

O resultado final: cada sequência inteira possível é gerada e gerada, um elemento de cada vez, e todos concatenados juntos em uma única sequência universal.

Pitão - 11 bytes

nproduto cartesiano de potência de [-n, n], para todos n.

.V1js^}_bbb

Experimente on-line aqui (finitamente).

Python 2 , 100 99 bytes

• Economizou um byte graças a ovs ; iterando sobre um itertoolsloop interno para indefinidamente.

from itertools import*
for n in count():
 for P in permutations(range(-n,n)*n):
	for p in P:print p

Experimente online!

Imprime indefinidamente todas as permutações do nintervalo inteiro repetido vezes [-n; n)para todos os números inteiros não negativos n.
Você pode procurar o primeiro deslocamento kpara qualquer subsequência usando esta versão modificada .

Perl 6 , 91 bytes

loop (my$i=1;;$i++){my@n=(-$i..$i);my@m=@n;loop (my$k=1;$k <$i;$k++){@m=@m X@n;};print @m;}

Experimente online!

Isso usa um método semelhante a algumas das outras respostas. Ele usa produtos cartesianos para imprimir os elementos de (-1,0,1), em seguida, todos os pares ordenados dos elementos (-2,-1,0,1,2), em seguida, todos os trigêmeos ordenados dos elementos (-3,-2,-1,0,1,2,3), etc.

Eu sou novo no Perl, então pode haver mais golfe a ser feito.

Versão mais legível:

loop (my $i = 1; ; $i++) {
  my @n = (-$i..$i);
  my @m = @n;
  loop (my $k=1; $k <$i; $k++) {
    @m = @m X @n;
  }
  print @m;
}