Generate unseen numbers

Question

Let us say a 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 proper 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.

• AdmBorkBork: Is the output supposed to be in decimal or binary? Or either?
• Erik the Outgolfer: @AdmBorkBork I think it's supposed to be integers.
• Rod: Could add the 100th term (or any other large n) ?
• Wheat Wizard: @AdmBorkBork You should output in any standard allowed format.
• Wheat Wizard: @Rod Is 36 large enough? a(36) is 47 (1 indexed).

Answer 1

Python 3, (削除) 88 (削除ここまで) (削除) 80 (削除ここまで) (削除) 78 (削除ここまで) 75 bytes

^{-6 bytes thanks to Wheat Wizard
-2 bytes thanks to RootTwo
-3 bytes thanks to notjagan}

s={0}
n=1
while 1:n+=1;b=f"{n:b}";p={b[1:],b[:-1]};s|=p-s and{b,print(n)}|p

Try it online!

• Wheat Wizard: Porting to python 3 saves 4 bytes if you want
• Wheat Wizard: Actually 7
• Rod: @WheatWizard ninja'd
• RootTwo: In Python 3.6, you can save 2 more by replacing bin(n)[2:] with f"{n:b}".
• notjagan: -3 bytes with some really weird changes.

Answer 2

Jelly, 22 bytes

BẆṖ
ṄÇ;ð9Çḟ\?98‘¤ß
2ç8

Try it online!

Answer 3

Mathematica, (削除) 116 (削除ここまで) 110 bytes

x={};f=Subsequences[#~IntegerDigits~2]&;Do[MemberQ[Most@f@n,s_/;FreeQ[f/@x,s,2]]&&x~AppendTo~Echo@n,{n,2,∞}]

Infinitely outputs terms of the sequence.

Explanation

x={};

x is the list of terms of the sequence so far.

f=Subsequences[#~IntegerDigits~2]&

f is a Function which takes an integer and returns all Subsequences of its base 2 representation (including the empty list {} and the full list of IntegerDigits itself).

Do[...,{n,2,∞}]

Evaluate ... for value of n from 2 to ∞.

...&&x~AppendTo~Echo@n

If ... is False, then the second argument to And (&&) is never evaluated. If ... is True, then Echo@n prints and returns n, which we then AppendTo the list x.

MemberQ[Most@f@n,s_/;FreeQ[f/@x,s,2]]

We want to check that some proper substring of n is not a substring of any previous term in the sequence. Most@f@n is the list of proper substrings of n, we then check whether there are any substrings s_ which is a MemberQ of that list such that the list f/@x of lists of substrings of previous terms of the sequence is FreeQ of s at level 2.

Answer 4

Mathematica, (削除) 109 (削除ここまで) 94 bytes

s={};Do[!SubsetQ[s,(t=Subsequences@IntegerDigits[i,2])[[2;;-2]]]&&(s=s~Join~t;Echo@i),{i,∞}]

Continuously output terms of the sequence

Special thanx to @ngenisis for -15 bytes

Mathematica, 123 bytes

(s=r={};For[i=2,i<2#,i++,If[!ContainsAll[s,(t=Subsequences@IntegerDigits[i,2])[[2;;-2]]],s=s~Join~t;r~AppendTo~i]];r[[#]])&

Take n as input and generate the nth term in this sequence (1 indexed)

input

[1000]

output

1342

• user61980: Good idea to keep track of the substrings that have appeared so far! I spy at least15 bytes that can go: SubsetQ is shorter than and equivalent to ContainsAll, you can use And instead of If, the Union is unnecessary, and Do is almost always shorter than For: s={};Do[!SubsetQ[s,(t=Subsequences@IntegerDigits[i,2])[[2;;-2]]]&&(s=s~Join~t;Echo@i),{i,∞}]
• user61980: 3 more bytes by using Most: s={};Do[!SubsetQ[s,Most[t=Subsequences@IntegerDigits[i,2]]]&&(s=s~Join~t;Echo@i),{i,2,∞}]

Answer 5

Pyth, 20 bytes

u+G
fP-Fm.:.Bd)+TG1Y

This prints the sequence infinitely. It can only be used offline as a consequence.

Explanation (The space is a newline):

u+G fP-Fm.:.Bd)+TG1Y
u Y Apply the following function to the previous output
 until it stops changing (or forever, in this case),
 starting with the empty list
 f 1 Find the first positive integer where
 +TG The integer prepended to the current list
 m Map to
 .Bd Convert to binary
 .: ) Form all subsequences
 -F Fold the filter-out function over the list
 This iteratively removes all subsequences already seen
 from the candidate
 P Remove the last subsequence which is the whole number.
 (newline) Print that first integer
 +G Prepend that first integer to the list

Answer 6

Pyth, 20 bytes

.V2I-=ZP.:jb2)Yb=+YZ

Try it online!

Answer 7

Haskell, (削除) (削除ここまで) 172 bytes

import Data.List
b 0=""
b n=b(n`div`2)++(show$n`mod`2)
s=nub.(tails=<<).inits
p x=s x\\[x]
n(_,l)x|(p.b)x\\l/=[]=(x,l++(s.b)x)|1<2=(0,l)
filter(>1)$fst<$>scanl n(1,[])[1..]

Try it online.

Explanation

The code generates the sequence continuously.

• b returns the binary representation of an Int as a String
• s returns all the substrings of a string
• p returns all the proper substrings of a string
• n is a function that is applied iteratively and returns a tuple containing:
  • the current element, if it is a member of the sequence, otherwise 0
  • a list of all substrings to check against for all following numbers
• finally, scanl is used to call n over and over again and its output is filtered to only contain elements greater than 1

Here's a slightly more readable version, before golfing:

import Data.List
binary :: Int -> String
binary 0=""
binary n|(d,r)<-divMod n 2=binary d++["01"!!r]
substrings :: String -> [String]
substrings xs = nub$inits xs>>=tails
properSubstrings :: String -> [String]
properSubstrings xs = substrings xs\\[xs]
sb = substrings.binary
psb = properSubstrings.binary
g = scanl step (1,[]) [1..]
 where step (_,l) x | psb x \\ l /= [] = (x,l++sb x)
 | otherwise = (0,l)
f=filter(>1)$fst<$>g

Answer 8

JavaScript, 57 bytes

for(x=1;;x++)/^10|10(00)*$/.test(x.toString(2))&&alert(x)

alert=x=>{if(x>100)throw 'Let we stop here.';document.write(x+'<br/>');};
for(x=1;;x++)/^10|10(00)*$/.test(x.toString(2))&&alert(x)

Let we write the given number n in binary form, then:

• If the number is starts with 10, n must in the sequence:
  • remove the first 1 in it, the remaining binary string must not be seen, since n is the smallest number which may contain such string
• If the number is starts with 11:
  • By removing the first 1 in it, the remaining binary string (let we donate it as 1x must be seen since:
    • number 1x is in the sequence, or
    • number 1x0 is in the sequence, since it contain unique sub string 1x
  • If it is odd (ends with 1), it must not in the sequence, since:
    • (n - 1) / 2 in the sequence, or
    • (n - 1) in the sequence, since it contain unique sub string (n - 1) / 2
  • If it is even (ends with 0), it is in the sequence iff n / 2 is not in the sequence
    • with the same idea, n / 2 is not in the sequence iff n / 2 is odd, or n / 4 is in the sequence

Conclusion:

the binary form of the number starts with 10 or ends with 1 followed by odd number of 0. Or describe in regex: x match /^10|10(00)*$/.