Euler Problem 125


Euler Problem 125:

Unutar minute:

class Program
{
    static void Main(string[] args)
    {
        int N = 100000000;
       // int N = 1000;
        List<long> nums= new List<long>();
        List<int> palindrom= new List<int>();
        for (int i = 2; i < N; i++)
            if (IsPalindrom(i.ToString()))
                palindrom.Add(i);

       for (int i = 0; i < palindrom.Count; i++)
        {
            int num=palindrom[i];
            if (IsSumSquare(num))
                nums.Add(num);

        }
       Console.WriteLine(nums.Sum());
       Console.WriteLine("Press any key to continue...");
       Console.Read();
    }

    private static bool IsSumSquare(int num)
    {
        int sqrt = (int)Math.Sqrt(num);
        if (sqrt * sqrt == num)
            sqrt -= 1;
        for (int j = sqrt; j >= 2; j--)
        {
            bool found = false;
            int k = j;
            int sum = 0;
            while (true)
            {
                sum += k * k;
                if (sum == num)
                  return true;
                else if (sum > num)
                    break;
                else if (k > 1)
                    k--;
                else
                    break;
            }
            if (found)
                break;

        }
        return false;
    }
     static bool IsPalindrom(string n)
    {
        int lnl;
        if (n.Length % 2 != 0)
            lnl = 1 + n.Length / 2;
        else
            lnl = n.Length / 2;

        int ln = n.Length;
        for (int i = 0; i < ln / 2; i++)
            if (n[i] != n[ln - 1 - i])
                return false;
        return true;
    }

}

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