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();

        }
    }
}

Euler Problem 278


Euler Problem 278:

Suština zadatka je da se pronađe najveći broj koji se ne može napisati preko linearne kombinacije brojeva. Najveći broj koji se ne može napisati u obliku linearne kombinacije 3 relativno prosta a,b,c broja da je izrazom:

f(a,b,c)=2abc-ab-ac-bc

Problem sa matematičke olimpijade iz 1983. godine održan u Parizu.

Kada se zna ova činjenica implementacija u C# se može vrlo jednostavno napisati.

var primes = (from p in Enumerable.Range(2, 4998) where IsPrime(p) select (long)p).ToList();
var pr = from p in primes
         from q in primes
         from r in primes
         where p < q && q < r
         select new { p, q, r };
var result = pr.Aggregate(0L, (sum, PQR) => sum += 2*PQR.p * PQR.q * PQR.r -
                                                   PQR.p * PQR.q -
                                                   PQR.p * PQR.r -
                                                   PQR.r * PQR.q);

Windows 7 i .NET4


Iza nas je već više pola godine od kad je posljednji mircosoftov OS – Windows 7 lansiran. Povratne informacije od korisnika govore da je novi OS uspio u svojoj namjeri da pruži korisnicima pravi ugođaj u korištenju. Ono što ovaj OS čini posebnim od prethodnih verzija je bogato korisničko iskustvo koje korisnicima daje lakoću rada. Pored tona novih i usavršenja postojećih osobina Windows 7 za prosječnog korisnika je prava revolucija u korisničkom interfejsu koji ovaj sistem daje. Prvenstveno se misli na nekoliko stvari:

1. Podrška za Senzore i Lokacije

2. Novi redizajnirani TaskBar

3. Libraries

4. Podrška za MultiTouch

Senzors and Location Platform (SLP)

Senzori u Windows 7 smislu su uređaji koji su sposobni mjeriti određene fizičke veličine okoline. Npr. Senzor može detektovati temparaturu, intenzitet svjetlosti u okolini i sl. Također, senzori imaju mogućnost preko GPS sitema izračunavati trenutni položaj. Senzori i Lokacija je nova platforma u Windows 7, koja na jednistven način obuhvata i tretira ove uređaje, i kroz jedinstven API pruža kontrolu i iskorištavanje ovih uređaja u razvoju i korištenju aplikacija koje koriste ove uređaje. Prije Windows 7, svaki od uređaja se tretirao posebno i imao je poseban API s kojim se kontrolisao. Windows 7 pruža jedinstven API preko kojeg se mogu razvijati aplikacije za svaki uređaj koji je označen kao Windows 7 SLP Compatibile.

image

Gornja slika pokazuje novi Windows 7 Control Panel Aplet za prikaz i manupulaciju sa senzorima i lokacijom podržavanih uređaja. API koji je razvijen pod Windows 7 za senzore i lokacije, naravno je „native“ i direktono se ne može koristiti u razvoju .NET aplikacija.

U koliko nemate fizički senzorski uređaj, a još uvijek želite da razvijete aplikacije potpomognute sa ovim uređajima moguće je instalirati virtualni senzor koji oponaša fizički uređaj. Da bi mogli da koristite virtualni senzor potrebno je da instalirate zadnji Windows 7 SDK, te zavisno od tipa OS (32bit ili 64bit) instalirate virtualne senzore.

Instalacija Windows 7 SDK i podrška za virtualne senzore

U nekoliko koraka biće opisan način na koji se istalira podrška za virtualni senzor

1. Pokrenite web instalaciju Windows 7 SDK, sa ovog linka. Instalacija Windows 7 SDK može se skinuti u ISO verziji ili web instalaciji. ISO vrezija je oko 4 GB, pa se preporuča da se koristi web instalacija preko koje možete izabrati one komponente koje su vam interesantne.

2. Nakon pokretanja winsdk_web.exe, pokreće se instalacijski čarobnjak preko kojeg se mogu ozačiti one komponente koje su za vas interesantne. Naredni prozor pokazuje komponente koje se trebaju instalirati u koliko želite imati podršku za visturalne senzore i aplikaciju za manipulaciju senzora svjetlosti.

image

3. Nakon instalacije SDK-a, sada je potrebno instalirati driver za senzor. Otvorite Device Manager i dodajte novi hardware, kao na slici.

image

U narednom koraku odaberite sljedeće opcije kao na slikama:

image

image

image

image

Putanja na kojoj se nalazi driver za virtualni senzor zavisi od tipa OS. Kod Win64 driver se nalazi kao na slici dolje, dok se za Win32 driver nalaizi u Bin folderu (jedan nivo više).

image

Nakon instalacije potrebno je Senzor uključiti:

image

5. Kad je driver instaliran sada je moguće pokrenuti aplikaciju VirtualLightSensor.exe za senzor svjetlosti koja se nalazi u Bin odnosno Bin/x64 folder za win32 ili win64 OS respektivno.

image

Razvoj .NET aplikacija koje podržavaju senzore

Razvoj .NET aplikacija koje podržavaju senzore i lokaciju, moguće je preko .NET 4.0 koji ulazi u release fazu ili koristiti .NET3.5. U oba slučaja potrebno je još koristiti određene biblioteke za podršku. S toga je Microsoft je pokrenuo Open Source projekat Windows API Code Pack, koji predstavlja ne samo wraper oko windows 7 dll-a, nego i OO platformu za razvoj aplikacija koje crpe osobine Windows 7 OS. Postiji čitav niz novih Windows 7 osobina koje su ugrađene u API Code Pack, koje će biti spomenute kasnije. Pored toga API Code Pack sadrži i podršku određenih osobina od starijih OS-ova poput Viste i XP, a koje nisu bile podržane sa .NET-om. API Code Pack sa prvom verzijom 1.0 pojavio se na ljeto 2009, dok je verzija 1.1.0 obznanjena na PDC2009 u oktobru 2009. Planovi su da će ovaj projekat u dogledno vrijeme biti sastavni dio .NET Frameworka.

LightSensorDemo

U okviru ovog posta implementiraćemo mali demo koji se bazira na senzoru svjetlosti. Aplikacija će detektovati senzore svjetlosti instalirane na PC-u (naravno virtualne). Detekcija svjetlosti registrovaće se sa progress bar controlom koja će prikazivati intenzitet svjetlosti. Za vrijeme promjene intenziteta svjetlosti u RichEdit koje će također biti povezana sa senzorom svjetlosti, mijenjaće svoju pozadinu u odnosu na intenzitet svjetlosti.

image

Da bi se mogao ovaj demo implementirati potrebno je, pored Windows 7 SDK, kojeg smo opisali, instalirati Windows API Code Pack.Koji će detaljnije biti opisan u narednom postu.

Nakon skidanja API Code Pack-a, potrebno je buildati biblioteku da bi se mogli referecirati njeni dll-ovi.

1. Otvorite Visual Studio 2010 (ili 2008), te formirajte novi Windows Forms Projekat LightSensorDEMO.

2. Nakon formiranja projekta potrebno je referencirati dll-ove od API Code Pack-a:

image

Odaberemo putanju u koju smo formirali dll-ove, te ih učitamo, kao na sljedećoj slici:

image

1. Nakon toga u Forms1.cs potrebno je deklarisati prostore imena:

image

Sada je jos potrebno implementirati logiku aplilacije. Da bi manipulisali sa senzorima koristimo statičku klasu: SensorManager čija je deklaracija prikazana u sljedećem kodu:

public static class SensorManager
    {
        public static event SensorsChangedEventHandler SensorsChanged;

        public static SensorList<Sensor> GetAllSensors();
        public static S GetSensorBySensorId<S>(Guid sensorId) where S : Sensor;
        public static SensorList<Sensor> GetSensorsByCategoryId(Guid category);
        public static SensorList<S> GetSensorsByTypeId<S>() where S : Sensor;
        public static SensorList<Sensor> GetSensorsByTypeId(Guid typeId);
        public static void RequestPermission(IntPtr parentWindowHandle, bool modal, SensorList<Sensor> sensors);
    }

Ova klasa sadrži statičke metode koje koristimo da dobijemo sve senzore instalirane na PC-u, secifične senzore filtrirane po kategoriji, ID, i sl. Pored ovih metoda postoji i event koji se okida kada god PC detektuje novi instaliran senzor. Ovom klasom u stanju smo potpuno manipulisati sa svim senzorima, kao i ad hock dobijati informacije o novoinstaliranom senzoru.

Na samom početku definisćemo event SensorsChanged, da u slučaju kada na aplikacija radi, imamo mogućnost detektovanja novoinstaliranog senzora.

U konstruktor klase Forms1 definišimo SensorsChanged,i implementirajmo metodu:

public Form1()
{
    InitializeComponent();
    SensorManager.SensorsChanged += new SensorsChangedEventHandler(SensorManager_SensorsChanged);
}

Pripadajuća metoda SensorManager_SensorsChanged poziva se iz radne niti (working thread) pa se direktono ne može manipulisati GUI kontrolama forme. S toga se pomoću BeginInvoke pristupa kontrolama na sljedeći način:

void SensorManager_SensorsChanged(SensorsChangedEventArgs change)
{

    BeginInvoke(new MethodInvoker(delegate
    {
        InitSensors();
    }));
}

Preko BeginInvoke pristupamo metodi InitSensors(); u kojoj definišemo i incijaliziramo event za promjenu intenziteta senzora svjetlosti.

Implementacija metode je sljedeća:

private void InitSensors()
{
    SensorList<AmbientLightSensor> alsList = SensorManager.GetSensorsByTypeId<AmbientLightSensor>();
    if (alsList.Count < 1)
    {
        MessageBox.Show("Ne postoji instaliran Senzor svjetlosti!");
        return;
    }

    alsList[0].DataReportChanged += new DataReportChangedEventHandler(Form1_DataReportChanged);
    alsList[0].UpdateData();
}

Ova metoda radi sljedeće:

1. Pohranjuje u listu sve instalirane senzore

2. U koliko lista nije prazna uzimamo prvi senzor iz liste i pretplaćujemo se na event DataReportChanged, koji će pratiti promjenu svjetlosti.

3. Metoda Form1_DataReportChanged uzima trenutnu vrijednost svjetlosti koju senzor registrira, na osvnovu te vrijednosti podešava se progress bar kontrola, a rich edit kontroli mijenja boju pozadine. Ova implementacije je prikazana na sljedećem listingu:

void Form1_DataReportChanged(Sensor sender, EventArgs e)
{
    AmbientLightSensor sensor = sender as AmbientLightSensor;
    // Seznor promjene svjetlosti dolazi iz radne niti stoga je potreno
    // preko BeginInvoke promjenu prosljediti u UI nit
    BeginInvoke(new MethodInvoker(delegate
    {
        int lightVal= (int)sensor.CurrentLuminousIntensity.Intensity;
        progressBar1.Value =lightVal;

        if (lightVal < 5)
            richTextBox1.BackColor = Color.Gray;
        else if(lightVal<10)
            richTextBox1.BackColor = Color.Goldenrod;
        else if (lightVal < 20)
            richTextBox1.BackColor = Color.LawnGreen;
        else if (lightVal < 100)
            richTextBox1.BackColor = Color.Green;
        else if (lightVal < 500)
            richTextBox1.BackColor = Color.Red;
        else if (lightVal < 1000)
            richTextBox1.BackColor = Color.Blue;
        else if (lightVal < 5000)
            richTextBox1.BackColor = Color.Yellow;
        else if (lightVal < 50000)
            richTextBox1.BackColor = Color.SaddleBrown;

    }));
}

LightSensorDEMO aplikacija demonstrira upotrebu novih mogućnosti Windows 7 OS, za razvoj .NET aplikacija korištenjem Windows API Code Pack. Cjelokupan sourcecode aplikacije možete preuzeti sa ovog linka.

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;
        }
    }
}

Euler Problem 100


Euler Problem 100: Finding the number of blue discs for which there is 50% chance of taking two blue.

Rješenje:

Potrebno je pronaći broj plavih diskova, čiji ukupan broj diskova prelazi 10^{12} . Ako pretpostavimo da je:

b – broj plavih diskova,
d_{u} – ukupan broj diskova većih od  10^{12}

Sada imamo sljedeću situaciju. Vjerojatnost da izaberemo dva plava diska možemo izračunati na sljedeći način analogno kao i u opisu problema:

\frac{b}{d_{u}}\cdot \frac{b-1}{d_{u}-1}=\frac{1}{2}

Odnosno nakon sređivanja izraza dobijamo:

2b(b-1)=d_{u}(d_{u}-1)

Sada je potrebno ovaj izraz svesti na Pell-ovu jednačinu i tražiti prvo rješenje.  Ako izraz pomnožimo sa 4, dobijamo sljedeće:

8b(b-1)=4d_{u}(d_{u}-1)

2(4b^{2}-4b+1-1)=4d_{u}^{2}-4d_{u}+1-1

2(2b-1)^{2}-2=(2d_{u}-1)^{2}-1

Sređivnjem jednačine imamo:

(2d_{u}-1)^2-2(2b-1)^2=-1

Izraz smo transformirali u oblik koji je pogodan da se uvede dodatna smjena.

x=2d_{u}-1, y=2b-1

Izraz prije uvođenja smjene sada poprima oblik:

x^2-2y^2=-1

Zadnji izraz predstavlja Pellovu jednačinu, koja se sada rješava standardnom metodom. Vrlo lako ovu jednačinu možemo riješiti preko Mathematica, ili nekom od već urađenih implementacija kontinualnih frakcija za rješevanje Pellove jednačine.

Implementacija u Mathematica:

Clear[sol,x,y,n];
sol=y/.FindInstance[x^2-2 y^2==-1&&x>10^12&&y>0,{x,y},Integers][[1]];
FindInstance[2 b-1==sol&&b>0,{n},Integers]