CS doesnot means Common sense!

Computer Science Level 4

ϕ ( n ) \phi(n) is defined as the number of positive integers less than or equal to n that are relatively prime to n n .

Determine the value of

( ∑ n = 1 19999 ϕ ( n ) ) m o d ( 100 ) \left(\displaystyle\sum_{n=1}^{19999} \phi(n)\right)\mod(100)


The answer is 96.

View wiki
Siddharth Bhatt by siddharth bhatt , 25, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Roel Baars
Jul 2, 2015

Very naive solution in Mathematica 

1
2
 
phi[n_] := Count[CoprimeQ[n, #] & /@ Range[1, n], True];
Mod[ParallelSum[Phi[n], {n, 1, 19999}], 10]

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Arulx Z
Jun 24, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
>>> from fractions import gcd
>>> def phi(n):
        num = 1
        for x in xrange(2, n):
            if gcd(n, x) == 1:
                num += 1
        return num

>>> summ = 0
>>> for x in xrange(1, 20000):
        summ += phi(x)
>>> summ % 100
96

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

Nice choice with xrange vs range . While your code gets the right answer, its runtime is very long. Can you think of ways to speed up your calculation? Check out memoization .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...