Who says you don't need a computer?

Computer Science Level 4

Euler's Phi function is a function $\phi : \mathbb{N} \rightarrow \mathbb{N}$ which when applied to a natural number $n$ , gives the number of natural numbers less than or equal to $n$ that are coprime to $n$ .

Find $\displaystyle \sum_{n=1}^{1000} \phi(n)$

Suggestions :-

Solve this with a program in language you like, rather than using a calculator (Programming practice) ..... Make use of the properties of the Phi function.
Everything that I shared on Brilliant

The answer is 304192.

5 solutions

Pranshu Gaba
Mar 2, 2015

This is my code in Python

from fractions import gcd

# defines phi function
def phi(n): 
    count = 0
    i = 1
    while i <= n:
        if gcd(n, i) == 1:
            count += 1
        i += 1
    return count

total = 0
j = 1

# adds phi(1) + phi(2) + ... + phi(1000)
while j <= 1000:
    total += phi(j)
    j += 1

print total

It outputs $\boxed{304192}$

Could you find the flaw in this computation:

primeList=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009 ]

def phi(num): originalNum=num for i in primeList: if(i>(originalNum//2)+1): break elif(originalNum%i==0): num=num*(1-(1/i)) return(int(num)) sum=0
for i in range(1,1001): sum+=phi(i)

print(sum)

i am getting the answer as 303959. i checked the values of phi() for some random nos with your code and they came out to be exactly same!

Vaibhav Ojha - 5 years, 11 months ago

Could you explain why you have used the following condition in the if statement if (i > (originalNum // 2) + 1):

Pranshu Gaba - 5 years, 11 months ago

because the max value of a divisor of a number (apart from the number itself) can be (that number/2)

Vaibhav Ojha - 5 years, 11 months ago

@Vaibhav Ojha – If you divide any number by itself, then you get $1$ which is an integer, therefore every number is its own divisor. You must also include the number itself along with other divisors.

If you compare your code with mine, you will notice that it gives different values of phi for all odd primes. Can you correct your code now?

Hint: One way to calculate $\phi(5)$ would be $5 \times \left( 1 - \frac{1}{5} \right) = 4$ . However your code calculates $5 \times 1 = 5$ .

Pranshu Gaba - 5 years, 11 months ago

@Pranshu Gaba – Thanks! That sorts it out!

Vaibhav Ojha - 5 years, 11 months ago

@Vaibhav Ojha – You're welcome!

The new if condition must be if (i > originalNum):

Pranshu Gaba - 5 years, 11 months ago

Vladimir Lem
Mar 2, 2015

C++:

#include <iostream>
using namespace std;

long long phi(int i) {
    long long res=i;
    int j=2;
    while (i!=1) {
        if (i%j == 0) {
            res-=res/j;
            while (i%j == 0) i /= j;
        }
        j++;
    }
    return res;
}

int main() {
    long long a=0;
    for (int k=1;k<=1000;k++) a += phi(k);
    cout << a << endl;
    return 0;
}

Mayank Raj
Apr 13, 2015

int c,ctr=0,sum=0;
for(c=1;c<=1000;c++)
{
for(int j=1;j<=c;j++)
{
int i,a=c,b=j,HCF,LCM;
if(a>b)
{
for(i=a%b;i!=0;i=a%b)
{
a=b;
b=i;
}
HCF=b;
}
else
{
for(i=b%a;i!=0;i=b%a)
{
b=a;
a=i;
}
HCF=a;
}
if(HCF==1)
ctr++;
}
}
System.out.println(ctr);
the ans will come 304192
in JAVA

Rushikesh Jogdand
Mar 24, 2015

I wrote following program in python for $\varphi (n)$ , but it's returning wrong values...can someone help me to spot my mistake (since I'm beginner with python, I'm prone to mistakes)

Hello Rushikesh Jogdand , there's no need to define these many functions, you may read this note on the Phi function , it includes the way you wanted to achieve from the above efforts... :D

Aditya Raut - 6 years, 2 months ago

Brock Brown
Mar 2, 2015

Python:

from fractions import Fraction as frac
def coprime(n, test):
    return frac(n,test).numerator == n
def phi(n):
    count = 0
    for test in xrange(1, n+1):
        if coprime(n, test):
            count += 1
    return count
total = 0
for n in xrange(1, 1001):
    total += phi(n)
print "Answer:", total

Who says you don't need a computer?

The answer is 304192.

5 solutions

0 pending reports