Euler Problem 72:

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

Solution:

Rješenje se ogleda u osobini Farrey ovog niza koji je opisan ovdje.

Implementacija: Najlakše je ovaj problem riješiti preko Mathematica u vrlo jednostavnom kodu poput:

Mathematica:

sum = 1;
For[i = 3, i <= 1000000, i++,
sum = sum + EulerPhi[i]
]; sum

C# Implementacija svodi se na optimiziranu implementaciju Eulerove Totient funkcije. Rješenje se dobija oko 37 sec što je poprilično dobar rezultat.

namespace EulerProblem72
{
    /* Iskoristiti osobinu Farey niza
     * |Fn|=1+SIGMA(phi(m)), m=1,1,...n
     */
    class Program
    {
        static List<long> primes = new List<long>();
        static void Main(string[] args)
        {
            long d = 100000;
            long count = 1;
            for (int i = 2; i < d; i++)
                if (IsPrime(i))
                    primes.Add(i);

            for (int i = 3; i <= d; i++)
                count = count + eulerTotient(i);

            Console.WriteLine("Solution PE72={0}", count);
            Console.WriteLine("Press any key to continue...");
            Console.Read();
        }

        private static bool IsPrime(int n)
        {
            for (int i = 2; i * i <= n; i++)
                if (n % i == 0)
                    return false;
            return true;
        }
        static int eulerTotient(int n)
        {
            int numPrimes = (from prim in primes where n + 1 > prim select prim).Count();

            int totient = n;
            int currentNum = n, temp, p, prevP = 0;
            for (int i = 0; i < numPrimes; i++)
            {
                p = (int)primes[i];
                if (p > currentNum)
                    break;
                temp = currentNum / p;

                if (temp * p == currentNum)
                {
                    currentNum = temp;
                    i--;
                    if (prevP != p)
                    {
                        prevP = p;
                        totient -= (totient / p);
                    }
                }
            }
            return totient;
        }

    }
}

Euler Problem 71

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

namespace EulerProblem71
{
    class Program
    {
        static void Main(string[] args)
        {
             Tuple<int, int> sol= FindFarreySeq(1000000);
           // Console.WriteLine("Sol: {0}/{1}", sol.Item1,sol.Item2);
            Console.WriteLine("Press any key to continue...");
            Console.Read();
        }
        //Return nth Ferey seq, either asc or desc
        static Tuple<int, int> FindFarreySeq(int n, bool asc = true)
        {
            double a, b, c, d,x,y;
            a = 1; b = 1; c = n-1; d = n;
            x = 3; y = 7;
            
            while (a>0)
            {
                x = Math.Floor((n + b) / d) * c - a;
                y = Math.Floor((n + b) / d) * d - b;
                

              
                     
                 if (x == 3.0 && y == 7.0)
                     return new Tuple<int, int>((int)c, (int)d);

                 a = c;
                 b = d;
                 c = x;
                 d = y;
                 Console.WriteLine("{0}/{1}",x,y);
            }
            return null;
        }
    }
}