Definicja

Nazwijmy (nieskończoną) sekwencję całkowitą uniwersalną, jeśli zawiera ona każdą skończoną sekwencję całkowitą jako ciągłą podsekwencję.

Innymi słowy, sekwencja liczb całkowitych (a ₁ , a ₂ ,…) jest uniwersalna wtedy i tylko wtedy, gdy dla każdej skończonej sekwencji liczb całkowitych (b ₁ ,…, b _n ) istnieje przesunięcie k takie, że (a _{k + 1} ,…, A _{k + n} ) = (b ₁ ,…, b _n ) .

Na przykład sekwencja dodatnich liczb pierwszych nie jest uniwersalna, między innymi z następujących powodów.

• Nie zawiera ujemnych liczb całkowitych, 1 ani liczb zespolonych.

• Chociaż zawiera 3 , nie zawiera ciągłej podsekwencji (3, 3, 3) .

• Chociaż zawiera 2 i 5 , nie zawiera ciągłych podsekwencji (2, 5) .

• Chociaż zawiera ciągłe podsekwencje (7, 11, 13) , nie zawiera ciągłych podsekwencji (13, 11, 7) .

Zadanie

Wybierz dowolną uniwersalną sekwencję liczb całkowitych (a ₁ , ₂ ,…) i zaimplementuj ją w wybranym przez siebie języku programowania, przestrzegając następujących zasad.

• Możesz przesłać pełny program lub funkcję.

• Masz trzy opcje wejścia / wyjścia:

  1. Nie wprowadzaj danych i wydrukuj lub zwróć całą sekwencję.

  2. Weź indeksu n jako wejście i wydrukować lub powrócić do _n .

  3. Weź indeks n jako dane wejściowe i wydrukuj lub zwróć (a ₁ ,…, a _n ) .

• W przypadku opcji We / Wy 2 i 3 możesz użyć indeksowania opartego na 0 , jeśli wolisz.

• Twoje przesłanie musi być deterministyczne: jeśli zostanie uruchomione wiele razy z tymi samymi danymi wejściowymi, musi dawać takie same wyniki.

Ponadto, o ile nie jest to od razu oczywiste, udowodnij, że wybrana sekwencja jest uniwersalna. Twój dowód może nie zależeć od niesprawdzonych przypuszczeń.

Obowiązują standardowe zasady gry w golfa . Niech wygra najkrótszy kod w bajtach!

Łuska , 5 bajtów

Spowoduje to wydrukowanie nieskończonej listy

ΣṖ…ݱ

Wypróbuj online! lub znajdź pierwszy indeks swojej sekwencji . (Zajmuje dużo pamięci dla większości sekwencji)

Wyjaśnienie:

   ݱ   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

W Husk Ṗzachowuje się ładnie dla nieskończonych list. Widać, że to zachowanie tutaj

Python 2 , 49 46 43 bajty

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

f(n)Zwraca _n tylko. Używa najmniejszej cyfry w bazie, aby wyodrębnić jedną z wyższych cyfr.nd

Wypróbuj online! Ten skrypt (dzięki uprzejmości Dennisa) pobiera dowolną skończoną sekwencję i daje npoczątek sekwencji.

Wyjaśnienie

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

Na przykład, nw przedziale 3141592650do 3141592659, d=10a ostatnia cyfra nwybiera jedną z pozostałych cyfr. Następnie dodajemy, -d/2aby uzyskać wartości ujemne.

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

Autonomiczna alternatywa, również 43 bajty:

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

Brachylog 2, 11 bajtów

≜~×-₂ᵐ~ȧᵐ≜∋

Wypróbuj online!

Próbowałem też algorytmu wykorzystującego partycjonowane partycje na liście, ale nie był on krótszy. Jest to generator, który wytwarza nieskończony strumień liczb całkowitych jako wynik; link TIO ma nagłówek do wydrukowania pierwszych dziesięciu tysięcy z nich.

Wyjaśnienie

Program rozpoczyna od wypróbowania wszystkich możliwych liczb całkowitych po kolei ( ≜domyślnie wypróbowuje wszystkie pozostałe możliwości, dla liczb całkowitych). To 0, 1, -1, 2, -2 itd. (Chociaż ujemne liczby całkowite nie osiągają końca programu). Jest to jedyny „nieskończony” krok programu; wszystkie pozostałe są skończone.

~×następnie generuje wszystkie możliwe faktoryzacje liczby całkowitej, traktując różne rzędy jako różne, i używając tylko wartości od 2 w górę (więc jest tylko skończonych wiele); zauważ, że w rozkładzie na czynniki dozwolone są liczby złożone, a nie tylko liczby pierwsze. Oznacza to, że wszystkie możliwe sekwencje liczb całkowitych ≥ 2 zostaną wygenerowane na tym etapie w pewnym momencie wykonywania funkcji (ponieważ taka sekwencja niekoniecznie ma jakiś produkt, a ten produkt zostanie wygenerowany w pewnym momencie na początku ≜).

Następnie musimy zmapować zestaw tych sekwencji na zbiór wszystkich sekwencji całkowitych, co odbywa się w dwóch krokach: odejmując 2 ( -₂) od każdego elementu ( ᵐ), dając nam zestaw wszystkich nieujemnych sekwencji całkowitych, a następnie biorąc plus lub minus ( ~ȧtzn. „wartość, której wartością bezwzględną jest”) każdy element (ᵐ). Ten ostatni krok jest oczywiście niedeterministyczny, więc Brachylog traktuje go jako generator, generując wszystkie możliwe listy, których elementy są plus lub minus odpowiedni element listy wejściowej. Oznacza to, że mamy teraz generator wszystkich możliwych sekwencji liczb całkowitych i generuje je w kolejności, która oznacza, że ​​wszystkie są generowane (w szczególności kolejność, którą otrzymujesz, jeśli weźmiesz wartość bezwzględną każdego elementu, dodaj 2 do każdego element, a następnie uporządkuj według produktu uzyskanych elementów).

Niestety pytanie wymaga pojedynczej sekwencji, a nie sekwencji, więc potrzebujemy jeszcze dwóch poleceń. Po pierwsze, ≜Brachylog prosi o jawne wygenerowanie sekwencji sekwencji ściśle (w przeciwieństwie do tworzenia struktury danych opisującej koncepcję sekwencji wygenerowanej tą metodą, a nie generowania sekwencji dopóki nie będzie to konieczne); zarówno to sprawia, że ​​program jest szybszy w tym przypadku, i zapewnia, że ​​dane wyjściowe są wytwarzane w żądanej kolejności. Wreszcie, ∋powoduje , że generator wysyła elementy poszczególnych sekwencji pojedynczo (przejście do następnej sekwencji, gdy wypisze wszystkie elementy poprzedniej).

Wynik końcowy: każda możliwa sekwencja liczb całkowitych jest generowana i wyprowadzana, po jednym elemencie na raz, i wszystkie łączone razem w jedną uniwersalną sekwencję.

Pyth - 11 bajtów

nprodukt kartezjański mocy [-n, n]dla wszystkich n.

.V1js^}_bbb

Wypróbuj online tutaj (ostatecznie).

Python 2 , 100 99 bajtów

• Oszczędność jednego bajtu dzięki ovs ; iteracja po itertoolswbudowanej pętli bez końca.

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

Wypróbuj online!

W nieskończoność wypisuje wszystkie permutacje nzakresu powtórzonych liczb całkowitych [-n; n)dla wszystkich nieujemnych liczb całkowitych n.
Za kpomocą tej zmodyfikowanej wersji można wyszukać pierwsze przesunięcie dowolnego podsekwencji .

Perl 6 , 91 bajtów

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;}

Wypróbuj online!

To używa metody podobnej do niektórych innych odpowiedzi. Używa produktów kartezjańskich do drukowania elementów (-1,0,1), następnie wszystkich uporządkowanych par elementów w (-2,-1,0,1,2), a następnie wszystkich zamówionych trojaczek elementów w (-3,-2,-1,0,1,2,3)itp.

Jestem nowy w Perlu, więc może być więcej golfa, które można by zrobić.

Bardziej czytelna wersja:

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;
}