Euler Problem 72

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

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

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

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

}
}
```

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...");
}
//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;
}
}
}
```