# All sequences as substrings

Make a program that outputs a sequence of integers so that every finite sequence of positive integers is a substring (continuous subsequence) of the output.

For example, the following sequence satisfies the rules:

1,1,1,2,1,1,1,1,2,2,1,3,1,1,1,1,1,1,2,1,2,1,1,3,2,1,1,3,1,4,...

To see the underlying pattern, let's format the sequence a bit differently:

1,
1,1, 2,
1,1,1, 1,2, 2,1, 3,
1,1,1,1, 1,1,2, 1,2,1, 1,3, 2,1,1, 2,2, 3,1, 4,
1,1,1,1,1, 1,1,1,2, 1,1,2,1, 1,1,3, 1,2,1,1, 1,2,2, 1,3,1, 1,4, 2,1,1,1, 2,1,2, 2,2,1, 2,3, 3,1,1, 3,2, 4,1, 5
...


Here you can see that every row contains every sequence of positive numbers that sum to the index of the row. For example, row 3 has all sequences whose sum is 3. This means that every sequence is included somewhere in the list.

Standard rules apply. As stated before, your sequence may also contain 0 or negative numbers. These non-positive numbers are not ignored, meaning that your output must contain arbitrarily long substrings of only positive integers.

# 05AB1E, 3 bytes

∞Ó˜


Try it online!

Outputs the exponents of numbers' prime factorization, flattened. It can be easily seen that all sequences will appear - a sequence $$\ a_i \$$ will appear when we go over the number $$\ \prod {p_i}^{a_i} \$$ ($$\ p_i \$$ is the i-th prime)

do y<-[1..];q<-mapM id$[1..y]<$[1..y];q


Try it online!

Start with the positive integers [1..]. Draw an integer y. Then take the cartesian product of y copies of [1..y]. This is just all the ways to choose y numbers less than or equal to y.

# Vyxal, 8 bytes

Þ∞ƛṄvṖ;f


Try it Online!

Pretty much the sequence in the question, but with a lot more 1s. Outputs as an infinite lazy list.

  ƛ   ;  # Over each element of...
Þ∞       # 1...∞
Ṅ     # Get integer partitions
vṖ   # Get all permutations
f # Flatten the result


# R, 22 bytes

repeat cat(rpois(9,9))


Try it online!

Outputs a random sequence of integers (realizations of the Poisson(9) distribution). They are printed in batches of 9, including some 0s (which is allowed by OP).

There is a theoretical guarantee that any finite sequence will almost surely be printed eventually.

• Nice, and inspired me to a similar sneaky approach in Husk. By the way, do you really mean "almost" in "almost surely"...? Feb 11 at 13:46
• @DominicvanEssen "Almost surely" means "with probability 1". Feb 11 at 14:20
• I didn't know that. Thanks! Feb 11 at 14:22

# JavaScript (Node.js), 50 49 bytes

for(x=0n;y=++x;)for(b=1n;y/=b;)console.log(y%++b)


Try it online!

Shortened by @l4m2.

This outputs the mixed-radix digital expansion of each positive integer n, where the radices used are 2, 3, 4, ... Any finite sequence of positive (or even nonnegative) integers will occur in the digits of some n.

• 49?
– l4m2
Feb 17 at 17:39

# Python, 54 bytes

j=k=t=2
while t:=k%2>0!=print(t)or-~t:k=k//2or(j:=-~j)

Attempt This Online!

This version consistently outputs True for 1.

### Old Python, 57 bytes

j=k=1
while[print(t:=len(f"{k&-k:b}"))]:k=k>>t or(j:=-~j)

Attempt This Online!

### Old Python, 63 bytes (@pxeger)

j=k=1
while 1:j+=k<1;k=k or j;t=len(f"{k&-k:b}");k>>=t;print(t)

Attempt This Online!

#### Old Python, 73 bytes

def f(j=1,k=1):
while 1:j+=k<1;k=k or j;t=len(f"{k&-k:b}");k>>=t;yield t

Attempt This Online!

This goes through all positive integers and outputs for each the sequence of distances between 1s in its binary representation.

For example:

1616 -> 11001010000 -> 5,2,3,1


# Python, 53 bytes

j=k=t=1
while k:=k//t or(j:=j+(t:=1)):print(k%t);t+=1

Attempt This Online!

# 05AB1E, 7 bytes

∞Åœ€€œ˜


Outputs the infinite example sequence, but without an unquify of the permutations.

Try it online.

Explanation:

∞        # Push an infinite positive list: [1,2,3,...]
Åœ      # Map each to a list of all possible lists of positive integers that sum
# to that integer:
#  [[[1]], [[1,1],[2]], [[1,1,1],[1,2],[3]], ...]
€     # Map over each list:
€    #  Map over each inner list:
œ   #   Get all permutations of this list
#    [[[[1]]], [[[1,1],[1,1]],[[2]]], [[[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],[[1,2],[2,1]],[[3]]], ...]
˜  # Flatten this list of lists
#  [1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,1,3,...]
# (after which the result is output implicitly)


# Pari/GP, 39 bytes

for(i=1,oo,[print(p[2])|p<-factor(i)~])


Try it online!

A port of @Command Master's 05AB1E answer.

## Pari/GP, 44 bytes (@Polichinelle)

for(i=9,oo,[print(d)|d<-digits(i,log(i)\1)])


Try it online!

## Pari/GP, 47 bytes

for(i=9,oo,[print(d)|d<-digits(i,log(i)^.9\1)])


When $$\i\$$ is larger enough, $$\b = \lfloor\log(i)^{0.9}\rfloor\$$ will satisfy $$\b^b < i\$$. So the code will print the base-$$\b\$$ digits of a sequence of more than $$\b^b\$$ consecutive integers, which will contain all sequences of integers in $$\1,\dots,b-1\$$ with length $$\.

Try it online!

## Pari/GP, 50 bytes

for(i=2,oo,for(j=1,i^i,[print(d)|d<-digits(j,i)]))


Try it online!

• The ^.9 is not necessary in log(i)^.9\1 (-3 bytes.) Feb 13 at 2:08