(*Mathematica start*)
(*Program to compute the sequence with the conjectured asymptotic sqrt(8*n)*)
Clear[a, b, f, p];
nn = 2000;
f[n_] := n;
a[n_] := DivisorSum[n, MoebiusMu[#] # &];
Monitor[TableForm[
   A = Accumulate[
     Table[Table[a[GCD[n, k]], {k, 1, nn}], {n, 1, nn}]]];, n]
TableForm[B = -Abs[A]];
Clear[A];
B[[All, 1]] = Table[f[n], {n, 1, nn}];
TableForm[B];
b = 1 + Total[Sign[1 + Sign[Accumulate[Transpose[B]]]]];
Clear[B];
Show[ListLinePlot[b],
 Plot[Sqrt[8*n], {n, 1, nn}, PlotStyle -> {Red, Thick}]]
(*Mathematica end*)