Euler Problem 230


Euler Problem 230: Fibonacci Words

Članak o Fibonacci words može se pogledati na wikipedia. Fibonacci Words predstavlja L-System. Formula pomoću koje se dobije n-to slovo u Fibonaccijevom nizu data je izrazom:

a(n) = \left \lfloor (n+2)*r \right \rfloor-\left \lfloor (n+1)*r \right \rfloor

gdje je

a(n) = \left \lfloor x\right \rfloor floor funkcija (najveći cijeli broj r<=x),

r=\frac{\varphi }{1+2\cdot \varphi}

\varphi=\frac{1+\sqrt{5} }{2} – zlatni rez (Golden ratio)

Obzirom da su ovdje u pitanju riječi A i B, koje čine 100 cifara (karaktera), potrebno je formulu modificirati nanačin da je n-to slovo koje se traži mora oduzeti od 200 odnosno Length(A+B). Nakon toga n se podjeli sa 100 i izračuna spomenuta formula. Ostatak djeljenja n sa 100 je cifra u riječi A ili B, zavisno od evaluacije formule.

static string a = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
static string b = "8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196";
static double phi = (1 + Math.Sqrt(5)) / 2.0;//Golden Ratio
static double r = phi / (1 + 2 * phi);

public static int D(long n)
{

    if (n > 200)
        n -= 200;      // -> ab-200
    else if (n > 100)
        n -= 100;      //B -> ab-100
    //else
    //    n = n;       //A -> a

    long m = n / 100;

    int index = (int)(n % 100);//Index of digit of word A or B

    //nth Fibonacci Word http: // research.att.com/~njas/sequences/A003849
    double nthDigit = (long)((m + 2) * r) - (long)((m + 1) * r);

    if (nthDigit == 1)//A
        return int.Parse(a[index - 1].ToString());
    else//B
        return int.Parse(b[index - 1].ToString());
}

static void Main(string[] args)
{
    long sum = 0;
    for (int i = 0; i <= 17; i++)
    {
       long m = (127 + 19 * i) * (long)Math.Pow(7, i);

        int digit = D(m);

        sum += digit * (long)Math.Pow(10, i);
    }
    Console.WriteLine(sum);
    Console.ReadLine();
}

Euler Problem 104


Euler Problem 104:

Na prvi pogled zadatak vrlo prost. Mathematica bi trebala da ga riješi za pa sekundi. Medjutim…
Prvi Brute force pokušaj i nije bio toliko loš.

For[i=45,True,i++,lst=IntegerDigits[Fibonacci[i]];
If[Sort[lst[[1;;9]]]=={1,2,3,4,5,6,7,8,9},If[Sort[Take[lst,-9]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]]
];i

Print[i] koji je stavljen ispisiva pandigitalne brojeve prvih 9 cifara Fibonaccievog broja. Ovim se htjelo vidjeti kako se često takvi brojevi pojavljuju, i drugo kako brzo algoritam radi.
Ubrzo se vidjelo da kod neće završiti brzo.

Druga optimizacija bila je da se izračunava ostatak djeljenja Fibonaccievog niza sa 10^9, a onda da se provjeri da li je prvi dio cifara pandigitalan. Odmah se vidjelo da je algoritam dosta brži ali i da neće završiti za 60 sekundi.

For[i=45,True,i++,
If[Sort[IntegerDigits[Mod[Fibonacci[i],10^9]]]=={1,2,3,4,5,6,7,8,9},
If[Sort[IntegerDigits[Fibonacci[i]][[1;;9]]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]]];

U implementaciji najsporiji dio je funkcija Fibonacci[], koja svaki put mora ispočetka da izračunava Fobonaccijev broj. Sada je potrebno ovaj dio optimizirati:

f1=1;f2=1;For[i=3,True,i++,
f=f1+f2;
If[Sort[IntegerDigits[Mod[f,10^9]]]=={1,2,3,4,5,6,7,8,9},
If[Sort[IntegerDigits[f][[1;;9]]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]];
f1=f2;
f2=f
];i

Kod se izvršava za 20 sec što je prihvatljiv rezultat. Približan rezultat dobijemo i sa C# implementacijom:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace EulerProblem104
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger div=BigInteger.Pow(10,9);
            long n = 1;
            foreach (var x in FibonacciNiz())
            {
                if (IsPanDigital(x % div))
                {
                    string ss = x.ToString();
                    if (ss.Length > 8)
                    {
                        var digits = ss.Substring(0, 9);
                        if (IsPanDigital(BigInteger.Parse(digits)))
                            break;
                    } 
                }
                n++;
                
            }
            Console.WriteLine(n);
            Console.WriteLine("Press any key to continue...");
            Console.Read();

        }
        static bool IsPanDigital(BigInteger numb)
        {
            var v = numb.ToString();
            if (v.Length < 9)
                return false;
           var ss=v.OrderBy(x => x).ToArray();
            for (int i = 0; i < ss.Count(); i++)
                if (ss[i].ToString() != (i + 1).ToString())
                    return false;
                return true;
        }
        static IEnumerable<BigInteger> FibonacciNiz()
        {
            BigInteger a = 1;
            BigInteger b = 1;
            BigInteger c = 0;
            yield return a;
            yield return b;
            while (true)
             {
               yield return c = a + b;
               a = b;
               b = c;
             }
        }
   }

}

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

        }
    }
}