Create a universal integer sequence

Question

Definition

Let's call an (infinite) integer sequence universal if it contains every finite integer sequence as a contiguous subsequence.

In other words, the integer sequence (a₁, a₂, …) is universal if and only if, for each finite integer sequence (b₁, …, b_n), there is an offset k such that (a_k+1, …, a_k+n) = (b₁, …, b_n).

The sequence of positive prime numbers, for example, is not universal, among others for the following reasons.

• It doesn't contain any negative integers, 1, or composite numbers.

• Although it contains 3, it does not contain the contiguous subsequence (3, 3, 3).

• Although it contains 2 and 5, it does not contain the contiguous subsequence (2, 5).

• Although it contains the contiguous subsequence (7, 11, 13), it does not contain the contiguous subsequence (13, 11, 7).

Task

Pick any single universal integer sequence (a₁, a₂, …) and implement it in a programming language of your choice, abiding to the following rules.

• You can submit a full program or a function.

• You have three options for I/O:

  1. Take no input and print or return the entire sequence.

  2. Take an index n as input and print or return a_n.

  3. Take an index n as input and print or return (a₁, …, a_n).

• For I/O options 2 and 3, you may use 0-based indexing if you prefer.

• Your submission must be deterministic: if run multiple times with the same input, it must produce the same output.

In addition, unless it's immediately obvious, please prove that the sequence you picked is universal. Your proof may not depend on unproven conjectures.

Standard code-golf rules apply. May the shortest code in bytes win!

Answer 1

Husk, 5 bytes

This prints an infinite list

ΣṖ…ݱ

Try it online! or find the first index of your sequence. (Takes a lot of memory for most sequences)

Explanation:

   ݱ   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

In Husk Ṗ behaves nicely for infinite lists. You can see it's behaviour here

Answer 2

Python 2, 49 46 43 bytes

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

f(n) returns a_n only. This uses the smallest digit of n in base d to extract one of the higher digits.

Try it online! This script (courtesy of Dennis) takes any finite sequence and gives you an n where that sequence begins.

Explanation

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

For example, for n in the range 3141592650 to 3141592659, d=10 and the last digit of n selects one of the other digits. Then we add -d/2 to get negative values.

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

Standalone alternative, also 43 bytes:

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

Answer 3

Brachylog 2, 11 bytes

≜~×-₂ᵐ~ȧᵐ≜∋

Try it online!

I also tried an algorithm using additive partitions on a list, but it wasn't any shorter. This is a generator that produces an infinite stream of integers as output; the TIO link has a header to print the first ten thousand of them.

Explanation

The program starts off by trying all possible integers in sequence (≜ tries all remaining possibilities, for integers by default). That's 0, 1, -1, 2, -2, etc. (although the negative integers don't reach the end of the program). This is the only "infinite" step of the program; all the others are finite.

~× then generates all possible factorisations of the integer, treating different orders as different, and using only values from 2 upwards (so there are only finitely many); note that composite numbers are allowed in the factorisation, not just primes. This means that all possible sequences of integers ≥ 2 will be generated by this step at some point in the execution of the function (as such a sequence necessarily has some product, and that product will be generated at some point by the initial ≜).

We then need to map the set of those sequences onto the set of all integer sequences, which is done in two steps: subtracting 2 (-₂) from each element (ᵐ), giving us the set of all nonnegative integer sequences, then taking plus or minus (~ȧ, i.e. "a value whose absolute value is") each element (ᵐ). The latter step is obviously nondeterministic, so Brachylog treats it as a generator, generating all possible lists whose elements are plus or minus the corresponding element of the input list. This means that we now have a generator for all possible integer sequences, and it generates them in an order that means they're all generated (specifically, the order that you get if you take the absolute value of each element, add 2 to each element, and then order by the product of the resulting elements).

Unfortunately, the question wants a single sequence, not a sequence of sequences, so we need two more commands. First, ≜ requests Brachylog to explicitly generate the sequence of sequences strictly (as opposed to producing a data structure describing the concept of a sequence generated via this method, and not actually generating the sequences until necessary); this both happens to make the program faster in this case, and ensures that the output is produced in the requested order. Finally, ∋ causes the generator to output the elements of the individual sequences one at a time (moving onto the next sequence once it's output all elements of the previous one).

The end result: each possible integer sequence gets generated and output, one element at a time, and all concatenated together into a single universal sequence.

Answer 4

Pyth - 11 bytes

nth power cartesian product of [-n, n], for all n.

.V1js^}_bbb

Try it online here (finitely).

Answer 5

Python 2, 100 99 bytes

• Saved one byte thanks to ovs; iterating over an itertools built-in to indefinitely loop.

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

Try it online!

Indefinitely prints all permutations of the n-times repeated integer range [-n; n) for all nonnegative integers n.
You can search for the first offset k for any subsequence using this modified version.

Answer 6

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

Try it online!

This uses a similar method to some of the other answers. It uses Cartesian products to print the elements of (-1,0,1), then all ordered pairs of the elements in (-2,-1,0,1,2), then all ordered triplets of the elements in (-3,-2,-1,0,1,2,3), etc.

I'm new to Perl, so there might be more golfing that could be done.

More readable version:

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