Overlap Study

by Ed Pegg Jr

Initialization

StringOverlaps[a_String]:=​​Select[Table[StringJoin[StringTake[a,i],a],{i,StringLength[a]-1}],​​StringMatchQ[#,a~~__]&]
StringOverlaps[{a_String,b_String}]:=Union[StringOverlaps0[a,b],StringOverlaps0[b,a],StringOverlaps1[a,b],StringOverlaps1[b,a]]
StringOverlaps0[a_String,b_String]:=​​Select[Table[StringJoin[StringTake[a,i],b],{i,StringLength[a]-1}],​​StringMatchQ[#,a~~__]&]
StringOverlaps1[a_String,b_String]:=If[StringPosition[b,a,1]==={},{},{b}]
StringOverlapsQ[list:{_String..}]:=!((Length[Union[list]]Length[list])&&!Apply[Or,StringOverlapsQ/@list]&&Catch[Scan[If[!(SameQ@@#)&&(StringOverlapsQ@@#),Throw[False]]&,Tuples[list,2]];True])
StringOverlapsQ[a_String]:=!(StringLength[a]==1||MatchQ[StringPosition[a,Table[StringTake[a,-i],{i,StringLength[a]-1}],1],{}|{{x_,_}}/;x>1])
onepercent[table_]:=N[Count[Flatten[table],1]/Length[Flatten[table]]];

NKS: notes-9-10--string-overlaps -- Approximations

NKS: String Overlaps.
Length/@Table[Select[ToString[FromDigits[#]]&/@Partition[DeBruijnSequence[Range[2],k],k,1,1],Not[StringOverlapsQ[#]]&],{k,1,12}]
{2,2,4,6,12,20,40,74,148,284,568,1116}
a[0]=1;a[n_]:=ka[n-1]-If[EvenQ[n],a[n/2],0]
a[10]/.k2
284

OEIS

A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet.
A003000[n]/2^n converges to 0.2677868402178891123766714035843025525550598979934845320763118885112149...
N[(a[200]/.k2)/2^200,50]
0.26778684021788911237667140358451379912424045658290
NSum
n-1
(-1)
2
(
n+1
2
-1)
2
-1
Product
(
m
2
-1)
2
(
m
2
-1)
2
-1
,{m,2,n},{n,1,4},50
0.26778684021788911212689482147090374617173890124715
A019308 Number of “bifix-free” words of length n over a three-letter alphabet.
N[(a[200]/.k3)/3^200,100]
0.5569798397642302936529413190253562568356116596043093950906928955668660775762511906554109976074594572
A019309 Number of “bifix-free” words of length n over a four-letter alphabet.
N[(a[200]/.k4)/4^200,100]
0.6877480120883629865157307881281905516741574947528722573136150598611735495440385705285448433200001072
unforge=Table[N[(a[100]/.km)/m^100,20],{m,2,20}];
approx=Flatten[Table[x/.Solve[m-Sqrt[-1/(1/(1/(1-x)-(m-1))-(m+1))]0],{m,2,20}]]

4
15
,
44
79
,
174
253
,
472
621
,
1040
1291
,
2004
2395
,
3514
4089
,
5744
6553
,
8892
9991
,
13180
14631
,
18854
20725
,
26184
28549
,
35464
38403
,
47012
50611
,
61170
65521
,
78304
83505
,
98804
104959
,
123084
130303
,
151582
159981

N[unforge-approx]
{0.00112017,0.0000178144,9.76515×
-7
10
,1.03726×
-7
10
,1.66666×
-8
10
,3.5579×
-9
10
,9.34515×
-10
10
,2.87498×
-10
10
,1.0018×
-10
10
,3.86071×
-11
10
,1.61677×
-11
10
,7.25991×
-12
10
,3.4595×
-12
10
,1.73511×
-12
10
,9.09911×
-13
10
,4.96223×
-13
10
,2.80166×
-13
10
,1.63149×
-13
10
,9.76794×
-14
10
}

Alphabet “12”, No self-overlap, up to length 11 --- no overlap chance 0.278271

dbsnall=SortBy[Sort[Flatten[Table[Select[ToString[FromDigits[#]]&/@Partition[DeBruijnSequence[Range[2],k],k,1,1],Not[StringOverlapsQ[#]]&],{k,1,11}]]],StringLength[#]&];
Length[dbsnall]
1160
tabnall=Table[If[Length[StringOverlaps[{dbsnall[[a]],dbsnall[[b]]}]]0,1,0],{a,1,Length[dbsnall]-1},{b,a+1,Length[dbsnall]}];
onepercent[tabnall]
0.278271
There is no benefit to comparing “1___2” strings with “2___1” strings, since these will always overlap.
ArrayPlot[tabnall,PixelConstrained1,FrameFalse]

Alphabet “12”, No self-overlap, up to length 12, always start “1” --- no overlap chance 0.582985

dbsnall=Flatten[Table[Select[ToString[FromDigits[#]]&/@Partition[DeBruijnSequence[Range[2],k],k,1,1],Not[StringOverlapsQ[#]]&],{k,1,12}]];
dbsnall=Select[dbsnall,StringTake[#,1]"1"&];
Length[dbsnall]
1138
tabnall=Table[If[Length[StringOverlaps[{dbsnall[[a]],dbsnall[[b]]}]]0,1,0],{a,1,Length[dbsnall]-1},{b,a+1,Length[dbsnall]}];
onepercent[tabnall]
0.582985
ArrayPlot[tabnall,PixelConstrained1,FrameFalse]

Alphabet “123”, No self-overlap, up to length 8, always start “1”--- no overlap chance 0.759355

dbsnall=Flatten[Table[Select[ToString[FromDigits[#]]&/@Partition[DeBruijnSequence[Range[3],k],k,1,1],Not[StringOverlapsQ[#]]&],{k,1,8}]];
dbsnall=Select[dbsnall,StringTake[#,1]"1"&];
Length[dbsnall]
1851
tabnall=Table[If[Length[StringOverlaps[{dbsnall[[a]],dbsnall[[b]]}]]0,1,0],{a,1,Length[dbsnall]-1},{b,a+1,Length[dbsnall]}];
onepercent[tabnall]
0.759355
ArrayPlot[tabnall,PixelConstrained1,FrameFalse]

Alphabet “1234”, No self-overlap, up to length 6, always start “1”--- no overlap chance .859005

dbsnall=Flatten[Table[Select[ToString[FromDigits[#]]&/@Partition[DeBruijnSequence[Range[4],k],k,1,1],Not[StringOverlapsQ[#]]&],{k,1,6}]];
dbsnall=Select[dbsnall,StringTake[#,1]"1"&];
Length[dbsnall]
949
tabnall=Table[If[Length[StringOverlaps[{dbsnall[[a]],dbsnall[[b]]}]]0,1,0],{a,1,Length[dbsnall]-1},{b,a+1,Length[dbsnall]}];
onepercent[tabnall]
0.859005
ArrayPlot[tabnall,PixelConstrained1,FrameFalse]

Alphabet “12345”, No self-overlap, up to length 5, always start “1”--- no overlap chance 0.905358

dbsnall=Flatten[Table[Select[ToString[FromDigits[#]]&/@Partition[DeBruijnSequence[Range[5],k],k,1,1],Not[StringOverlapsQ[#]]&],{k,1,5}]];
dbsnall=Select[dbsnall,StringTake[#,1]"1"&];
Length[dbsnall]
601
tabnall=Table[If[Length[StringOverlaps[{dbsnall[[a]],dbsnall[[b]]}]]0,1,0],{a,1,Length[dbsnall]-1},{b,a+1,Length[dbsnall]}];
onepercent[tabnall]
0.905358
ArrayPlot[tabnall,PixelConstrained1,FrameFalse]

junk
