Totient Function

C++. This is the problem 69 from Project Euler.

Question: 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.

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. Link to the page.

Solution: Please check those reference links to see how Totient function works: Link1 and Link2 To make the implementation efficient, analysing the sequence for a small quantity is important. When we observe, we see that Phi is lesser for even numbers than the next consecutive odd numbers. That means that only even numbers will make the ratio is higher. Therefore, we only check even numbers in input n, particularly for big values. Plus, I used float data type instead of double for efficiency by trading with precision. So there is a small rounding error at the calculation of Phi at some points. However, it does not affect the result and the rounding error is neglectable. The answer is 510510, and Phi is 92160 for the input 510510.

#include <iostream>

struct Totient
{
	float phi = 0.0f;
	
	float operator()(int x)
	{
		phi = static_cast<float>(x); // initialising phi as x

	//checking all prime factors of x and for every prime
	//factoring p and multiplying phi with (1 - 1/p)
	for (int p = 2; p * p < x + 1; ++p)  
	{
		//checking if p is a prime factor
		if (x % p == 0) 
		{
			//updating x and phi
			while (x % p == 0)
			{
				x /= p;
			}
			phi *= (1.0f - (1.0f / p));	
		}
	}

	//where x > 1 and x has a prime factor p > sqrt(x) 
	if (x > 1)
	{
		phi *= (1.0f - (1.0f / x));
	}
	//there is a small rounding error for phi by floating point calculation 
	//however, it does not affect the result, so neglecting the error is fine
	//otherwise, we could use casting like static_cast<int>(phi + 0.5f)
	
	return phi;
	}		
};

int main()
{
	Totient totient;
	
	int n = 1000000;

	int result = 0;
	float ref_ratio = 0.0f;
	float max_ratio = 0.0f;
	
	//phi is lesser for even numbers than the next consecutive odd numbers
	//it means that only even numbers will make the ratio is higher
	//so, we only check even numbers in input n, particularly for big values
	for (int i = 2; i < n + 1; i+=2)
	{
		ref_ratio = i / totient(i);  //totient() is a functor
		if (ref_ratio > max_ratio)
		{
			max_ratio = ref_ratio;
			result = i;
		}
	}
	std::cout << "n is " << result << " where phi is " << totient(result) << std::endl;

	return 0;
}

#include <iostream>

struct Totient

{

float phi = 0.0f;

float operator()(int x)

{

phi = static_cast<float>(x); // initialising phi as x

//checking all prime factors of x and for every prime

//factoring p and multiplying phi with (1 - 1/p)

for (int p = 2; p * p < x + 1; ++p)

{

//checking if p is a prime factor

if (x % p == 0)

{

//updating x and phi

while (x % p == 0)

{

x /= p;

}

phi *= (1.0f - (1.0f / p));

}

//where x > 1 and x has a prime factor p > sqrt(x)

if (x > 1)

{

phi *= (1.0f - (1.0f / x));

}

//there is a small rounding error for phi by floating point calculation

//however, it does not affect the result, so neglecting the error is fine

//otherwise, we could use casting like static_cast<int>(phi + 0.5f)

return phi;

}

};

int main()

{

Totient totient;

int n = 1000000;

int result = 0;

float ref_ratio = 0.0f;

float max_ratio = 0.0f;

//phi is lesser for even numbers than the next consecutive odd numbers

//it means that only even numbers will make the ratio is higher

//so, we only check even numbers in input n, particularly for big values

for (int i = 2; i < n + 1; i+=2)

{

ref_ratio = i / totient(i); //totient() is a functor

if (ref_ratio > max_ratio)

{

max_ratio = ref_ratio;

result = i;

}

std::cout << "n is " << result << " where phi is " << totient(result) << std::endl;

return 0;

}