Java, n=11 (~30-35 sec on TIO)
import java.util.ArrayList;
import java.util.List;
class Main{
public static void main(String[] args){
for(int n=1; ; n++){
String binaryFormat="%"+n+"s";
int sum=0, c=0;
double powerOf2=Math.pow(2,n);
for(int a=0; a<powerOf2; a++){
String binaryA=toBinary(n,a);
for(int b=0; b<powerOf2/2; b++){
String binaryB=toBinary(n,b);
sum += solve(binaryA, binaryB);
c++;
}
}
System.out.println(n+": "+sum+"/"+c);
}
}
private static String toBinary(int n, int a){
return String.format("%"+n+"s", Integer.toBinaryString(a)).replace(' ','0');
}
private static int solve(String a,String b){
String s=a+2+b+3;
List<Integer> M = new ArrayList<>();
for(int c : s.getBytes())
M.add(c);
List<Integer> S = suffixList(M, 51);
List<Integer> I = new ArrayList(S);
for(int i=0; i<S.size(); i++)
I.set(S.get(i), i);
int L=0,R=0,m=0,h=0;
for(int i=0; i<S.size(); i++){
if(I.get(i)!=0){
int j=S.get(I.get(i)-1);
while(s.charAt(i+h)==s.charAt(j+h))
h++;
if(h>m){
int len = a.length();
int sortedMid = (i-j)*(j-len)>0 ? j
: (i-j)*(i-len)>0 ? len
: i;
if(len == sortedMid){
m=h;
L=i<j?i:j;
R=L+h;
}
}
if(h>0)
h--;
}
}
return R-L;
}
private static List<Integer> suffixList(List<Integer> s, int K){
int n=s.size();
s.add(0);s.add(0);s.add(0);
int n0=(n+2)/3, n1=(n+1)/3, n2=n/3;
int n02=n0+n2;
int adj=n0-n1;
int length=(n+adj)/3;
List<Integer> A=new ArrayList<>();
for(int x=0; x<n+adj; x++)
if(x%3!=0)
A.add(x);
A.add(0);A.add(0);A.add(0);
radixPass(K,s,A,2,n02);
radixPass(K,s,A,1,n02);
radixPass(K,s,A,0,n02);
List<Integer> B=new ArrayList<>();
for(int i=0; i<n02; i++)
B.add(0);
int[] t=new int[3];
int m=0;
for(int i=0; i<n02; i++){
int x=A.get(i);
int[] u=new int[3];
for(int j=x; j<x+3; j++)
u[j-x]=s.get(j);
if(t[0]!=u[0]||t[1]!=u[1]||t[2]!=u[2])
m++;
t=u;
B.set(x/3+x%3/2*n0, m);
}
if(n02==1)
for(int i=0; i<n02; i++)
A.set(i, 0);
else{
List<Integer> X = suffixList(B,m);
for(int i=0; i<n02; i++)
A.set(i, X.get(i));
}
List<Integer> I = new ArrayList<>(A);
for(int i=0; i<n02; i++)
I.set(A.get(i), i+1);
B = new ArrayList<>();
for(int x:A)
if(x<n0)
B.add(3*x);
radixPass(K,s,B,0,n0);
List<Integer> R = new ArrayList<>();
int p=0;
for(int T=adj; T<n02; ){
int x = A.get(T);
boolean bool = x>=n0;
int b = bool?1:0;
int i=(x-b*n0)*3-~b;
int j=B.get(p);
if(p==n0
|| (bool ? s.get(i)<s.get(j) || (s.get(i)==s.get(j)&&s.get(i+1)<s.get(j+1)) || (s.get(i)==s.get(j)&&s.get(i+1)==s.get(j+1)&&I.get(A.get(T)-n0+1)<I.get(j/3+n0))
: s.get(i)<s.get(j) || (s.get(i)==s.get(j)&&I.get(A.get(T)+n0)<I.get(j/3)))){
R.add(i);
T++;
}else{
R.add(j);
p++;
}
}
for(int i=p; i<n0; i++)
R.add(B.get(i));
return R;
}
private static void radixPass(int K, List<Integer> s, List<Integer> a, int o, int n){
int[] c=new int[K+3];
for(int i=0; i<n; i++)
c[s.get(a.get(i)+o)+1]++;
for(int i=0; i<K+3; i++)
c[i]+=c[i<1?c.length-1:i-1];
List<Integer> A = new ArrayList<>(a);
for(int i=0; i<n; i++){
int x=A.get(i);
int j=s.get(x+o);
a.set(c[j], x);
c[j]++;
}
}
}
NOTE: The fractions aren't normalized like in the challenge description. The decimal values the fractions represent are correct, though.
Try it online with indefinite printing - times out after 60 sec or try it online with given argument \$n\$.
Only just got it working, so will try to improve its performance later on.
Short explanation of my solution:
I first modified @MitchSchwartz' Python 2 answer for the Longest common substring in linear time challenge so it will loop over the binary-string pairs we want to check. This challenge asks for the starting and ending index of the longest common substring between two strings, in lineair time (\$O(n)\$ complexity).
His answer implements 'The Skew Algorithm' described in Juha Kärkkäinen's & Peter Sanders' Simple Linear Work Suffix Array Construction article, with the implementation of the Longest Common Prefix part using the algorithm described in Toru Kasai's, Gunho Lee's, Hiroki Arimura's, Setsuo Arikawa's, and Kunsoo Park's Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications article.
Since we basically want to check all binary-string pairs \$A\$ and \$B\$, where \$A\$ are binary strings for integers \$a\$ in the range \$a=[0, 2^n)\$ and \$B\$ are binary strings for integers \$b\$ in the range \$b=[0,\frac{2^n}{2})\$ (similar as the existing Mathematica answer does), I've modified @MitchSchwartz' ungolfed answer to take the difference between the found indices, and sum those together for our numerator (the denominator will be \$n^{2n-1}\$ for any given \$n\$).
Here is that modified Python code:
Try it online printing indefinitely or try it online with given input \$n\$ (which produces \$n=9\$ in about 25-30 sec on TIO).
Since I'm not too skilled with Python, I decided to port everything to Java which I use on a daily basis. This allows me to make performance enhancing modifications (which I will try to do later on) easier. And I also knew that the larger \$n\$ would become, the better the performance of the Java program in comparison to the Python program would be (which can also be seen by checking some \$n\$ in both programs on TIO - i.e. the inputs \$n=1,5,7,9\$ will take approximately 1.5, 2.25, 1.75, 4.0 seconds in Java, but 0.02, 0.1, 1.5, 30.0 seconds in Python 2 respectively.
Long explanation:
TODO: I will describe the actual implementation and perhaps add some comments to the code later on. This already took long enough to modify and port to Java for now.
