PE #34 intelligent brute-force

Problem34.cs

    class Problem34
    {
        static int[] factorial = new int[10];
                public static void Solve()
        {
            factorial[0] = 1;
            int sum = 0;
            // Use Halley's method to compute the solution 9!*x = 10^x - 1
            // Start where the gradient is shallow, to avoid overshooting into the solution near 0.
            // This gives us about a 10% speed improvement over the integer multiple.
            double error = 1;
            double tol = .0001;
            double z = -(Math.Log(10) / Factorial(9)) * Math.Pow(10, -1 / Factorial(9));
            double w = -6;
            double w1 = 0;
            double wp1;
            double ew;
            double wewz;
            while (error > tol)
            {
                wp1 = w + 1;
                ew = Math.Exp(w);
                wewz = w * ew-z;
                w1 = w - wewz / (wp1 * ew - (wp1+1)*(wewz)/(2*wp1));
                error = Math.Abs(w1 - w);
                w = w1;
            }
            double K = -w / Math.Log(10) * Factorial(9) - 1;
            int f, k, n;
            for (int i = 10; i <= K; i++)
            {
                f = 0;
                k = i;
                while (k > 9)
                {
                    n = k % 10;
                    k /= 10;
                    f += factorial[n];
                }
                if (i == f + factorial[k])
                    sum += i;
            }
            Console.WriteLine(sum);
        }

        // recursively compute the factorial, with memoization
        public static int Factorial(int n)
        {
            if (factorial[n] == 0)
                factorial[n] = n * Factorial(n - 1);

            return factorial[n];
        }
    }