using System;

using System.Diagnostics;

public class Program

{

    public static void Main()

    {

        for (var i = 1; i <= 5; i++)

        {

            var sw = Stopwatch.StartNew();

            var result = SPOJ_0074_DIVSUM_v3.sigma(i * 100000);

            sw.Stop();

            Console.WriteLine("sigma({0})  = {1}     {2}ms", i * 100000, result, sw.ElapsedMilliseconds);

        }

        const int max = 500000;

        var csSw = Stopwatch.StartNew();

        var checksum = SPOJ_0074_DIVSUM_v3.checksum(max);

        csSw.Stop();

        Console.WriteLine("summing sigma(0)..sigma({0}) ... {1} ({2} ms)", max, checksum, csSw.ElapsedMilliseconds);

    }

    class SPOJ_0074_DIVSUM_v3

    {

        public const int LIMIT = 500000;

        static int[] sigma_cache;

        static int   sigma_limit;

        static SPOJ_0074_DIVSUM_v3 ()

        {

            sigma_cache = new int[LIMIT + 1];

            sigma_cache[0] = 0;

            sigma_cache[1] = 1;

            sigma_limit = 1;

        }

        public static ulong checksum(int n)

        {

            unchecked

            {

                ulong result = 0;

                for (var i = 0; i <= n; i++)

                {

                    result += (ulong) sigma(i);

                }

                return result;

            }

        }

        public static int sigma (int n)

        {

            if (n > sigma_limit)

                extend_sigma_cache(n);

            return sigma_cache[n];

        }

        static void extend_sigma_cache (int new_limit)

        {

            Trace.Assert(sigma_cache != null && new_limit < sigma_cache.Length);

            Trace.Assert(sigma_limit >= 1);

            for (int n = sigma_limit + 1; n <= new_limit; ++n)

            {

                int gpn_index = 1;

                int gpn_value = 1;

                int gpn_delta = 1;

                int sum = 0, k;

                for ( ; ; )

                {

                    if ((k = gpn_value) >= n) break;

                    sum += sigma_cache[n - k];

                    if ((k += gpn_index) >= n) break;

                    sum += sigma_cache[n - k];

                    ++gpn_index; gpn_value += (gpn_delta += 3);

                    if ((k = gpn_value) >= n) break;

                    sum -= sigma_cache[n - k];

                    if ((k += gpn_index) >= n) break;

                    sum -= sigma_cache[n - k];

                    ++gpn_index; gpn_value += (gpn_delta += 3);

                }

                if (k == n)

                    sum += (gpn_index & 1) != 0 ? n : -n;

                sigma_cache[n] = sum;

            }

            sigma_limit = new_limit;

        }

    }

}