Euler Problem 108 i 110


Euler Problem 108:

\frac{1}{x}+\frac{1}{y}=\frac{1}{n}

gdje su: x,y,n>0 prirodni brojevi.

Prije bilo kakvog zaključka potrebno je početnu jednačinu transformirati u drugi oblik. Gornju jednakost možemo napisati:

nx+ny=xy

xy-nx-ny=0

Dodajmo lijevoj i desnoj strani n^2, pa imamo:

(x-n)(y-n)=n^2

Sada naša jednačina ima drugačiji smisao, odnosno pojednostavljeno rješenje, a to je: Potrebno je pronaći za koje n, n^2 ima broj divizora koji prelaze 2x.

Rješenje se najbrže može pronaći korištenjem Wolfram Mathematica i to:

For[i = 2, i != 1, i++, If[DivisorSigma[0, i^2] > 2000, Break[]]]; i

Ovo je jednostavniji oblik problema 110, koji traži broj rješenja koji prelaze 4.000.000. Svakako da pristup koji je prezentiran nije adekvatan. S toga je potrebno ovaj problem proširiti. Zadnjom jednačinom pokazali smo da je potrebno pronaći broj čiji kvadrat treba da ima određen broj divizora. Osnovni teorem Aritmetike kaže svaki prirodni broj se može jedinstveno napisati u obliku produkta prostih brojeva, odnosno:

n=\prod_{i=1}^{k}p_{i}^{\alpha_{i}}

gdje je p_{1}>p_{2}>...>p_{k}, i=1,2,3,...,k.

S druge strane ako znamo proste faktore broja n, tada možemo izračunati broj njegovih divizora odnosno možemo izračunati sigma funkciju:

\sigma _{0}(n)=\prod_{i=1}^{k}(\alpha_{i}+1)

Ako je broj divizora broja n dat gornjim izrazom tada broj divizora broja n^2 možemo izračunati kao:

\prod_{i=1}^{k}(2*\alpha_{i}+1)

Zadatak se svodi na rekurzivno rješavanje jednakosti:

divisors= \prod_{i=1}^{k}(2*\alpha_{i}+1)

i

n=\prod_{i=1}^{k}p_{i}^{\alpha_{i}}

Na osnovu datih izraza imamo implementaciju rješenja za probleme 108 i 110.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace EulerProblem110
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Solution PE108:{0}", Solve(1999, 1000).ToString());
            Console.WriteLine("Solution PE110:{0}", Solve(7999999, 4000000).ToString());
            Console.Read();

        }
        static BigInteger Solve(int divisors,int max,int nthPrime=0)
        {
            if(divisors<=1)
                return 1;

            else if(divisors<=3)
               return Primes().ElementAt(nthPrime);
            else
            {
                BigInteger power=Primes().ElementAt(nthPrime);
                BigInteger result=power*Solve((divisors+2)/3,1,nthPrime+1);

                for(int i=2; i<=max; ++i)
                {
                    power*=Primes().ElementAt(nthPrime);
                    if(power > result)
                        break;
                    BigInteger temp=power*Solve((divisors+2*i)/(2*i+1),i,nthPrime+1);

                    if(temp<result)
                        result=temp;
                }
                return result;
            }

		}
        static IEnumerable<long> Primes()
        {
            yield return 2;
            yield return 3;
            long prevPrime = 3;
            while (true)
            {
                prevPrime++;
                if (IsPrime(prevPrime))
                    yield return prevPrime;
            }
        }
        static bool IsPrime(long n)
        {
            if (n < 2) return false;
            for (int i = 2; i * i <= n; i++)
                if (n % i == 0)
                    return false;
            return true;
        }
    }
}

About Bahrudin Hrnjica

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

Posted on 09/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