A Lot of Phi's

Computer Science Level 5

Do you know Euler's Totient Function ? You probably do.

The function $\phi(n)$ stands for the number of positive integers less than or equal to n that are relatively prime to n.

In this problem, you will receive a list of a list of numbers, and you must answer the value of the sum of Euler's Totient Function for every number in that list. As the sum may be too big, you must give the answer modulo 1,000,000,007 .

Click here to access the list.

For example, if the list was {3, 5, 7}, your answer should be: $\phi(3) + \phi(5) + \phi(7) = 2 + 4 + 6 = 12$

The answer is 593197122.

2 solutions

Lucca Siaudzionis
Jun 20, 2014

My code can be accessed here

Explanations are on the code.

If you don't understand some properties, read this .

Why you define MAXP only as 55050 ? The numbers in your list is almost 800000000 .

Christopher Boo - 6 years, 1 month ago

Pranjal Jain
Jun 16, 2015

Python 3.4

import time
from math import ceil,sqrt
def primedivisors(x):
    if x==1:
        return [1]
    else:
        divisors=[]
        for i in range(2,ceil(sqrt(x))+1):
            if (x//i)*i==x:
                while(x//i)*i==x:
                    divisors.append(i)
                    x//=i
    if x!=1:
        divisors.append(x)
    return list(set(divisors))
def phi(x):
    prod=x
    a=uniquedivisors(x)
    for i in a:
        prod*=(1-1/i)
        prod=round(prod)
    return prod
a=list(int(i) for i in open('cs_totient.txt').readlines())
start_time=time.time()
print(sum(phi(i) for i in a)%(10**9+7)) #Returns 593197122
print(time.time()-start) #Returns 5.077291011810303 seconds

A Lot of Phi's

The answer is 593197122.

2 solutions

0 pending reports