Количество n-значных чисел

void Main()
{
    int n = 100000;
    const string template = @"M({0:n0}) = {1} - time: {2:ss'.'fffffff} {3}";
    var timer = new Stopwatch();
    
    cache.Clear();
    timer.Restart();
    var res1 = MertensRecursiveBasic(n);
    timer.Stop();
    Console.WriteLine(template, n, res1, timer.Elapsed, "рекуррентная формула");
 
    cache.Clear();
    timer.Restart();
    cache.Add(1, 1);
    var res2 = MertensRecursiveOdd(n);
    timer.Stop();
    Console.WriteLine(template, n, res2, timer.Elapsed, "рекуррентная формула нечётные");
 
    cache.Clear();
    timer.Restart();
    var res3 = MertensRecursiveSqrt(n);
    timer.Stop();
    Console.WriteLine(template, n, res3, timer.Elapsed, "рекуррентная формула группировка");
 
    cache.Clear();
    timer.Restart();
    cache.Add(1, 1);
    var res4 = MertensRecursiveSqrtOdd(n);
    timer.Stop();
    Console.WriteLine(template, n, res4, timer.Elapsed, "рекуррентная формула нечётные группировка");
 
 
    cache.Clear();
    timer.Restart();
    var len = (int)(Math.Sqrt(n)*Math.Log(n + 3)) + 3;
    mertens = GetMertens(len);  
    var res5 = MertensRecTableSqrtOdd(n);
    timer.Stop();
    Console.WriteLine(template, n, res5, timer.Elapsed, "рекуррентная формула нечётные группировка решето");
 
}
 
// Define other methods and classes here
private static Dictionary<long, long> cache = new Dictionary<long, long>();
private static int[] mertens = new int[] {0,1,0};
 
// рекуррентная формула
private static long MertensRecursiveBasic(long n)
{
    long res;
    if (cache.TryGetValue(n, out res))
        return res;
    
    res = 1;
    for (int k = 2; k <= (int)n; k++)
        res -= MertensRecursiveBasic(n / k);
    
    cache[n] = res;
    return res;
}
 
// рекуррентная формула нечётные
private static long MertensRecursiveOdd(long n)
{
    long res;
    if (cache.TryGetValue(n, out res))
        return res;
    
    res = 0;
    for (int k = 3; k <= (int)n; k+=2)
        res -= MertensRecursiveOdd(n / k);
    
    cache[n] = res;
    return res;
}
 
// M(n) = 1 - sum [<=sqrt] ( M(n/k) ) - sum [<=sqrt] ( (n/k - n/(k + 1))*M(k) )
// рекуррентная формула корень
        private static long MertensRecursiveSqrt(long n)
        {
            long res;
            if (cache.TryGetValue(n, out res))
                return res;
 
            int sqrt = (int)Math.Sqrt(n);
            res = 1;
            for (int k = 2; k <= sqrt; k++)
                res -= MertensRecursiveSqrt(n / k);
            for (int k = 1; n / k > sqrt; k++)
                res -= (n / k - n / (k + 1)) * MertensRecursiveSqrt(k);
 
            cache[n] = res;
            return res;
        }
 
        // рекуррентная формула корень нечётные
 
        // M(n) = 1 - sum odd [<=sqrt] ( M(n/k) ) - sum [<=sqrt] ( (n/k - n/(k + 1))*M(k) )
        private static long MertensRecursiveSqrtOdd(long n)
        {
            long res;
            if (cache.TryGetValue(n, out res))
                return res;
 
            int sqrt = (int)Math.Sqrt(n);
            res = 0;
            for (int k = 3; k <= sqrt; k += 2)
                res -= MertensRecursiveSqrtOdd(n / k);
            for (long k = 1, nk = n, nk1; nk > sqrt; k++, nk = nk1)
            {
                nk1 = n / (k + 1);
                res -= (nk - (nk >> 1) - nk1 + (nk1 >> 1)) * MertensRecursiveSqrtOdd(k);
            }
            cache[n] = res;
            return res;
        }
 
        // решето
        private static int[] GetMertens(int max)
        { 
            var sqrt = (int)Math.Floor(Math.Sqrt(max));
            var mu = new int[max + 1];
            for (int i = 1; i <= max; i++)
                mu[i] = 1;
            for (int i = 2; i <= sqrt; i++)
            {
                if (mu[i] == 1)
                {
                    for (int j = i; j <= max; j += i)
                        mu[j] *= -i;
                    for (int j = i * i; j <= max; j += i * i)
                        mu[j] = 0;
                }
            }
            for (int i = 2; i <= max; i++)
            {
                if (mu[i] == i)
                    mu[i] = 1;
                else if (mu[i] == -i)
                    mu[i] = -1;
                else if (mu[i] < 0)
                    mu[i] = 1;
                else if (mu[i] > 0)
                    mu[i] = -1;
                mu[i] += mu[i - 1];
            }
            return mu;
        }
        
        
        // рекуррентная формула корень нечётные таблица
 
        // M(n) = 1 - sum odd [<=sqrt] ( M(n/k) ) - sum [<=sqrt] ( (n/k - n/(k + 1))*M(k) )
        private static long MertensRecTableSqrtOdd(long n)
        {
            if (n < mertens.Length) return mertens[n];
            long res;
            if (cache.TryGetValue(n, out res))
                return res;
 
            int sqrt = (int)Math.Sqrt(n);
            res = 0;
            for (int k = 3; k <= sqrt; k += 2)
                res -= MertensRecTableSqrtOdd(n / k);
            for (long k = 1, nk = n, nk1; nk > sqrt; k++, nk = nk1)
            {
                nk1 = n / (k + 1);
                res -= (nk - (nk >> 1) - nk1 + (nk1 >> 1)) * MertensRecTableSqrtOdd(k);
            }
            cache[n] = res;
            return res;
        }