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

Advertisements