Euler's Totient Sum

Computer Science Level 3

Find the sum of Euler's Totient function from 1 to 314.

The Euler's Totient function of n n is defined to be the number of relatively prime positive integers to n n less than or equal to n n . 1 is relatively prime to every number, even itself.


The answer is 30104.

View wiki
Tristan Shin by Tristan Shin , 20, USA

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.

4 solutions

Tristan Shin
Mar 26, 2014 
 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
39
40
41
42
43
44
45
46
 
def smallestFactor(n):
    a = 2
    while a <= n:
        if float(n) / a == int(n / a):
            return a
        a += 1

def relativePrime(a, b):
    factors1 = []
    x = smallestFactor(a)
    while x != a:
            factors1.append(x)
            a /= x
            x = smallestFactor(a)
    factors1.append(x)
    factors2 = []
    y = smallestFactor(b)
    while y != b:
        factors2.append(y)
        b /= y
        y = smallestFactor(b)
    factors2.append(y)
    finalBool = True
    c = 0
    while c < len(factors1):
        d = 0
        while d < len(factors2):
            if factors1[c] == factors2[d]:
                finalBool = False
            d += 1
        c += 1
    return finalBool

max = input()
x = []
a = 1
while a <= max:
    b = [1]
    c = 2
    while c <= a:
        if relativePrime(a, c):
            b.append(c)
        c += 1
    x.append(len(b))
    a += 1
print sum(x)

2 Helpful 0 Interesting 0 Brilliant 0 Confused

is there any solution for that with using C or PYTHON or any other computer code language !! i will appreciate you if you give me such solution

Rishabh Jain - 7 years, 2 months ago

Log in to reply

I provided a Python solution if you want, but unfortunately I only know Python and Java, so this is the best I can provide. If you want a more efficient code, I can use the formula and create a program based on that, but as for C, I don't know much C. Sorry!

Tristan Shin - 7 years, 2 months ago
David Holcer
Apr 3, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
import fractions
def phi(n):
    amount = 0
    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1
    return amount
array=[]
summ=0
for i in range(1,315):
    array.append(phi(i))
for i in array:
    summ+=i
print summ

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Wolfram|Alpha? Huh!

Use Free Software.

Here is a sage code as simple: 

sum(map(euler_phi,range(1,315)))

Go to http://sagenb.org and run it.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

"Paid version" code: 

Total[Map[EulerPhi,Range[1,314]]]

or 

Sum[EulerPhi[x], {x,1,314}]

Bernardo Sulzbach - 6 years, 11 months ago
Tunk-Fey Ariawan
Mar 31, 2014

Since this is a Computer Science problem, so I think it doesn't matter for us to answer it by using WolframAlpha . Here is the solution:

# Q . E . D . # \Large\color{#3D99F6}{\text{\# }\mathbb{Q.E.D.}\text{ \#}}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...