22
\$\begingroup\$

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 (a1, a2, …) is universal if and only if, for each finite integer sequence (b1, …, bn), there is an offset k such that (ak+1, …, ak+n) = (b1, …, bn).

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 (a1, a2, …) 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 an.

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

  • 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 rules apply. May the shortest code in bytes win!

\$\endgroup\$
  • \$\begingroup\$ Your proof may not depend on unproven conjectures. I thought that's implied :p \$\endgroup\$ – Erik the Outgolfer Oct 19 '17 at 14:13
  • \$\begingroup\$ and how you would save a list of numbers in a number? \$\endgroup\$ – RosLuP Oct 24 '17 at 5:56
13
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You might want to elaborate on how Q works. (I think I got it, but I'm not sure.) \$\endgroup\$ – Dennis Oct 19 '17 at 0:05
  • \$\begingroup\$ @Dennis turns out I wanted , not Q \$\endgroup\$ – H.PWiz Oct 19 '17 at 0:06
9
\$\begingroup\$

Python 2, 49 46 43 bytes

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

f(n) returns an 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
\$\endgroup\$
  • \$\begingroup\$ You can use len(`n`) instead of len(str(n)). \$\endgroup\$ – Dennis Oct 19 '17 at 16:23
  • \$\begingroup\$ Thanks @Dennis. I can add more explanation if anyone needs it. \$\endgroup\$ – japh Oct 19 '17 at 16:28
  • \$\begingroup\$ I wrote a function that, given a finite sequence, finds an offset in your sequence. Try it online! \$\endgroup\$ – Dennis Oct 19 '17 at 16:45
  • \$\begingroup\$ This is very cool. \$\endgroup\$ – histocrat Oct 19 '17 at 21:33
  • \$\begingroup\$ Nice. Only thing is it'll break upwards of n=2**63-1 since the representation gets an L appended (str(n) would address that for three bytes if it's necessary). \$\endgroup\$ – Jonathan Allan Oct 21 '17 at 14:22
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ ais523… is that you!? \$\endgroup\$ – Fatalize Oct 24 '17 at 6:33
  • \$\begingroup\$ If it's not them, it's a hell of a coincidence, considering posts from their deleted account show the same account number. \$\endgroup\$ – totallyhuman Oct 24 '17 at 10:45
4
\$\begingroup\$

Pyth - 11 bytes

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

.V1js^}_bbb

Try it online here (finitely).

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ while~0:. Heh heh... \$\endgroup\$ – Chas Brown Oct 19 '17 at 7:24
  • \$\begingroup\$ 99 bytes using itertools.count \$\endgroup\$ – ovs Oct 19 '17 at 7:24
  • \$\begingroup\$ @ovs Thanks; did not know of that built-in. \$\endgroup\$ – Jonathan Frech Oct 19 '17 at 10:49
2
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.