Let us say a proper substring is any continuous section of an original string. For example cat
is a substring of concatenate
. We will say that a proper substring is a substring that is not equal to the original string. For example concatenate
is a substring of concatenate
but not a proper substring. (single character strings have no substrings)
We will now define a sequence using these terms. The nth term in this sequence will be the smallest number such that there is a proper substring of its binary representation that is not a substring of any earlier term in the sequence. The first term is 10
.
As an exercise lets generate the first 5 terms. I will work in binary to make things easier.
The first term is 10
since 11
, the next smallest number, has only one proper substring, 1
which is also a substring of 10
, 11
is not in the sequence. 100
however does contain the proper substring 00
which is not a substring of 10
so 100
is our next term. Next is 101
which contains the unique proper substring 01
adding it to the sequence, then 110
contains the proper substring 11
which is new adding it to the sequence.
Now we have
10, 100, 101, 110
111
is up next but it contains only the substrings 1
and 11
making it not a term. 1000
however contains 000
adding it to the sequence.
Here are the first couple terms in decimal
2, 4, 5, 6, 8, 9, 10, 11, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 30, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 50, 54, 56, 58
Task
Either
Take n as input and generate the nth term in this sequence (either 0 or 1 indexed)
Continuously output terms of the sequence
This is code-golf answers are scored in bytes with less bytes being better.