project euler -- problem 69

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n Relatively Prime φ(n) n/φ(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666...
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.


---
φ(n) is the Euler's totient function.
It states
\( \varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right) \)
where the product is over the distinct prime numbers dividing n.

So, we can deduce that
\( \frac{n}{\varphi(n)} = \prod(\frac{p}{p-1}) \)
Each \( \frac{p}{p-1} \) is larger than one. We can see that \( \frac{p}{p-1} \) is larger when p is smaller. and \( \frac{n}{\varphi(n)} \) has a higher value when there are more smaller p divided by n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<cmath>
#include<vector>
 
using namespace std;
const int N=1000000;
 
bool isPrime(int n);
 
int main() {
  vector<int> primes;
  for (int i=2; i <= sqrt(N); i++) {
    if (isPrime(i)) {
      primes.push_back(i);
    }
  }
  int n=1;
  for (int i=0; i< primes.size(); i++) {
    if (n * primes[i] > N) {
      cout << "Answers to PE 69: " << n << endl;
      break;
    }
    n *= primes[i];
  }
  return 0;
}
 
bool isPrime(int n) {
  if (n == 2)
    return true;
  if (n % 2 == 0)
    return false;
  for (int i=2; i <= sqrt(n); i++) {
    if ( n % i == 0 )
      return false;
  }
  return true;
}

This code runs very fast...

Answers to PE 69: 510510
   user  system elapsed 
  0.001   0.003   0.004
m4s0n501

Related Posts

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>