Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d <= 1,000,000?
This was really beautiful. First I brute-forced it, using 35 minutes and then I searched the solution-forum for a better algorithm, without success. Then my mentor suggested this approach, which is so elegant that it deserves a name: The Sieve of Senehtsotare...16 seconds!
using System;
using System.Collections.Generic;
namespace ProjectEuler
{
class Program
{
static void Main()
{
//Problem 72
DateTime start = DateTime.Now;
int number = 1000000;
BigInt sum = new BigInt("1");
var tots = GenerateTotients(number);
foreach (KeyValuePair<int, int> pair in tots)
sum += pair.Value;
Console.WriteLine(sum-2);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
public static List<List<int>> GeneratePrimeFactors(int n)
{
var primes = GeneratePrimes(n);
var primeFactors = new List<List<int>>();
primeFactors.Add(new List<int>{0});
for (int i = 1; i <= n; i++)
primeFactors.Add(new List<int>());
if (n==1) return primeFactors;
foreach (int i in primes)
for (int j = i; j <= n; j += i)
primeFactors[j].Add(i);
return primeFactors;
}
public static Dictionary<int, int> GenerateTotients(int n)
{
var totients = new Dictionary<int, int>{{0,0}};
List<List<int>> primeFactors = GeneratePrimeFactors(n);
for (int i = 1; i < primeFactors.Count; i++)
{
double totient = i;
foreach (int j in primeFactors[i])
totient *= 1 - 1/(double) j;
totients.Add(i,(int)totient);
}
return totients;
}
public static bool IsPrime(int n)
{
if (n < 2) return false;
if (n == 2) return true;
for (long i = 2; i <= Math.Sqrt(n); i++)
if (n % i == 0) return false;
return true;
}
public static List<int> GeneratePrimes(int n)
{
var primeNumbers = new List<int> { 2, 3 };
for (int i = 5; i <= n; i += 2)
if (IsPrime(i))
primeNumbers.Add(i);
return primeNumbers;
}
}
}
, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
10.
