某人提出的二进制序列问题

无心人

由0,1组成的最长的字符串长度f(n)，满足：任意两段长度等于n的互无交叠的子串不相同。
即对于字符串S，任意整数i,j，满足
0 <= i, i + n <= j, j + n <= len(S)
S[i:i+n] != S[j:j+n]

显然这个最大长度f(n)是有限的，因为n位二进数只有2^n个，所以f(n)<n*(2^n+1). 不过这个上界有点粗。

如f(1) = 2, 序列是01
f(2) = 7, 序列是0001110
f(3) = 16
求f(7)和f(8)

无心人

f(4)=32
f(5)=59
f(6)=110

无心人

提出问题的人提出了个搜索策略
比如n=6先构造10000000000011111111111
`1 \ \underbrace{0\cdots0}_{(2n-1)个}\ \overbrace{1\cdots1}^{(2n-1)个}`
后面的搜索，优先搜索当前位置与它前n-1位置相同的字符

.·.·.

https://oeis.org/A332232
没想到这个帖子比OEIS还早
早这么多

mathe

这个问题感觉应该可以继续扩张而不应该只找到6项。
显然，如果我们要求所有长度为n的两个子串都不同（去掉重叠的限制），那么由于最多有$2^n$个子串，每个字符只能作为一个子串的起点，加上最后n-1个字符不能作为某个子串的起点，得到长度最多$2^n +n-1$.
而我们的目标是要构造一个二进制串，使得长度为n的相同子串尽量多，那么这些子串也必然都是自相交的。
比如n=8,子串
abcdeabc
最多可以在后面继续添加{deabc}，构成abcdeabc{deabc}使得子串abcdeabc子相交出现两次
而实际上我们还可以继续最长延伸这个字符串到abcdeabc{deabcdeab}, 但是后面不能再添加字母c了（不然会出现不相交的相同串)
比较有意思的是，这个序列正好会让
bcdeabcd
cdeabcde
deabcdea
eabcdeab
也都重复了一次。

类似的，对于次数更多的重复序列如
abcabcab
可以补充为abcabcab{cabcabca},使得三个序列
abcabcab
bcabcabc
cabcabca
都可以重复三次。

通过提前统计每个序列本身最多可以被重叠的次数，我们就可以得到这种二进制序列最大长度的一个上限。

XIAOWEN

f(7) 的值为 119098

王守恩

f(1)=2: 01=10,取01
f(2)=7: 0001110=1110001=0111000=1000111,取0001110=331
f(3)=16: 0000010101111100=1111101010000011=0011111010100000=1100000101011111,取0000010101111100=5111152
f(4)=32: 01010100100110110111111100000001=？我们约定从0开始，且0尽可能的多，还有比这好的吗？
f(5)=59: 00000000010001000110011001110100101010101101101111111110000,取913132222311211111111212194
f(6)=110: 00000000000100001000011000110001110011100111101000101001010010110010011011011010101010111011101111111111100000
f(7)<220: