Euler Problem 211


Euler Problem 211:

Problem koji tretira djelioce prirodnih brojeva.

Fantastičan post na koji sam naletio riješio je ideju oko zadatka. Nakon pročitanog posta nije bilo teško implemetirati rješenje. Naime, oko divizora i multiplikativnih funkcija mogu se pronaći informacije i na Wikipedii, a suština je i osobini koju posjeduje Sigma funkcija.

Multiplikativne funkcije imaju osobinu da je funkcija proizvoda jednaka proizvodu funkcija:

f(ab)=f(a)f(b)

Ovu osobinu imaju nekoliko značajnih funkcija teorije brojeva poput: Euler Totient funkcija \varphi(n), Möbius Funkcija \mu(n), Sigma \sigma_{r}(n), i druge funkcije.

Kao što je u prethodnim postovima rečeno Sigma funkcije tretira djelioce prirodnog broja n i to:

\sigma_{r}(n)=\sum_{i=1}^{k} d_{i}^{r}

gdje su d_{i} djelioci broja n.

Zbog multilpikativnosti ove funkcije zadnji izraz možemo napisati kao:

\sigma_{r}(n)=\sigma_{r}( p_{1}^{l_{1}} p_{2}^{l_{2}} ... ) = \sigma_{r}(p_{1}^{l_{1}}) \sigma_{r}(p_{2}^{l_{2}})...

gdje su p_{1},p_{2}, ... prosti faktori broja n, a l_{1},l_{2},..., potencije faktora.

Na osnovu zadnjeg izraza možemo pisati:

\sigma_{r}(n)=\prod_{i=1}^{r}\frac{p_{i}^{(l_{i}+1)\cdot r}-1}{p_{i}^{r}-1}.

Proširenjem algoritma datog u postu i prilagođavanjem za postavke zadatka imamo:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//Modified code found at http: // comeoncodeon.wordpress.com
namespace EulerProblem211
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = 64000000;
            long nprim = (long)Math.Sqrt(N)+1;
            long[] Sigma0 = new long[N];
            long[] Sigma2 = new long[N];
            long[] isprime = new long[nprim];
            long d, n, p, k, i,e,nom,den;

            for (n = 2; n < nprim; n++)
                isprime[n] = 1;

            //Sieve for Eratosthenes for Prime
            //Storing the smallest prime which divides n.
            //If Sigma0[n]=0 it means it is prime number.
            for (d = 2; d < nprim; d++)
            {
                if (isprime[d] > 0)
                {
                    for (n = d * d; n < nprim; n += d)
                    {
                        isprime[n] = 0;
                        Sigma0[n] = d;
                    }
                    for (; n < N; n += d)
                        Sigma0[n] = d;
                }
            }
            //Applying the formula
            //Divisor(N)=Divisors(N/p^f(N,p))*(f(N,p)+1)
            Sigma0[1] = 1;
            Sigma2[1] = 1;
            for (n = 2; n < N; n++)
            {
                //Prime number
                if (Sigma0[n] == 0)
                {
                    Sigma0[n] = 2;
                    Sigma2[n] = n*n+1;
                }
                else
                {
                    //The smallest prime factor of n
                    p = Sigma0[n];

                    Sigma2[n] += p * p;
                    k = n / p;
                    e = 2;
                    while (k % p == 0)
                    {
                        k /= p;
                        e++;
                    }
                    Sigma0[n] = Sigma0[k] * e;
                    nom = (long)Math.Pow(p, 2 * e) - 1;
                    den =p*p-1;
                    long temp = nom / den;
                    long sol = Sigma2[k]*temp;
                    Sigma2[n] = sol;
                }
            }
            long sum = 0;
            for (i = 1; i < N; i++ )
            {
                long temp = (long)Math.Sqrt(Sigma2[i]);
                if (temp * temp == Sigma2[i])
                sum += i;
            }
            Console.WriteLine(sum);
            Console.Read();

        }
    }
}

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 16/03/2010, in Project Euler and tagged . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s