All sequences as substrings

Question

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 sequence 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.

Answer 1

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)

Answer 2

Haskell, 39 bytes

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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!

Port of @Polichinelle's JS answer.

Answer 7

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)

Answer 8

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 \$<b\$.

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!