[ASSIGNMENT] Eulers totient

Question

Phi(n) - also known as totient(n) - is the number of integer lower than n such that k and n have no common divisor (ie gcd(n,k)==1)

Code a function phi(n).
Note that if gcd(a,b)=1 then phi(ab)=phi(a)phi(b)

Test values:
p in [13,17,2593] => phi(p)=p-1
2=>1 16=>8 100=>40 25=>20 33=>20 4=>2

More on Totient: http://mathworld.wolfram.com/TotientFunction.html

Answer 1

https://code.sololearn.com/co96oapIC0Iq/?ref=app

Answer 2

Accelerated using prime factorization:

https://code.sololearn.com/cgKQ250c4ibF/?ref=app

Answer 3

Nevfy
Ok, I got it 👍

Answer 4

Nevfy
I have no problem with speed, but I have a problem with memory limit on SL 😁
On my Intellij IDE, the time for range 1-180.000 is 4.297 second.
Here's :
https://code.sololearn.com/c9xS6mscs7W7/?ref=app

I try to write a solution using the SieveOfEratosthenes method to avoid memory limit exceed.

Answer 5

VcC
I made some changes to ver.2: I changed the type of int to type long, inserted line 26 to break loop when N=1
Now works for N over 9000000000000000000 (single check)

Answer 6

VcC Nevfy
I'm not a mathematician, and I do not know if my second version has some name for algorithm...but it seems to me it works as it should.

I used prime factorization of N.
For all distinct factors I used the function phi (p) = p-1
For repeating factors: (p) = p or p-0

For example :
N=220
factors=(11,5,2,2)
distinct=(11,5,2)
repeated=(2)
phi(11)*phi(5)*phi(2)*2 = 80

For example :
N=50.000
factors =(5,5,5,5,5,2,2,2,2)
distinct =(5, 2)
repeated=(5,5,5,5,2,2,2)
phi(5)*phi(2)*5*5*5*5*2*2*2=20.0000

Answer 7

VcC
Thank you 😉

Answer 8

Nevfy
Okay. I try to modify the code for numbers in the range during the day. But on SL, the problem occurs when printing a large number of lines or characters - shows the time limit exceed. Is there a way to solve this problem?

Answer 9

Nevfy
That's true.
With gcd(k, n) my code works for N<100.000 without limit exceed.
With prime factorization and phi(p^n) works for N over 500 milion

Answer 10

Nevfy
Yes, single check.

Answer 11

Without imports:
https://code.sololearn.com/cX1DKYARwlgg/?ref=app

Answer 12

This an oneliner, which use a naive approach:
https://code.sololearn.com/c8DFh5a7O29G/?ref=app

@VcC Could you also add some input-output examples to simplify examination of the codes?

Answer 13

Ok, finally I decided to convert my optimization idea to a code. Here it is:

https://code.sololearn.com/c8O6H0iKshMM/?ref=app

I have found that optimized version works three times quicker checking consequently all numbers from 1 to 2000. You can type only the highest limit using my code and see the comparison (for sure it doesn't work for big limits due to Time Limit of SoloLearn).

Answer 14

Any language

Answer 15

phi(p^n)=p^n-p^n-1 if p is prime
The problem in your version is that factorization can be very slow for large primes. You could eliminate 2, then limit the loop to odd numbers and up to sqrt(n) only

Answer 16

@VcC That's a great formula! Now optimized version will work even quicker!
@LukArToDo And it also means that your code is correct.

Answer 17

@LukArToDo Just do not print them :-)
Time spent for the calculations for all numbers from 1 to given by user limit is the only required line in the output. Is there any timing library in kt?

Answer 18

Any specific language it needs to be done in?

Answer 19

@LukArToDo
Your first code: phi(25) = phi(5)*phi(5) = 20
The answer 20 is correct but the output is wrong. First of all gcd(5,5) != 1, so this formula can't be used, secondly, phi(5) = 4.

Answer 20

@VcC The only thing to speed up the code, which comes to my mind is:
1. Check if number is Prime?
- if so return n-1
- if not, we just lost some time
Complexity O(sqrt(n)) for direct check or O(log(n)) for a probabilistic one.
2. Do a prime factorization of number.
2.a. Create list of Primes from 2 to n//2.
As always I offer a Sieve algorithm with complexity of O(n*log(log(n))).
2.b. Factorization itself has a complexity of about O(log(n))
3. Use formula phi(ab)=phi(a)*phi(b) if gcd(a,b)=1.
It means that for all Primes, which are met only once, we can use phi(a)=a-1
For others - do a direct calculation.

Example: 725
1. It is not Prime.
2. 725 = 5^2 * 29
3. phi(725) = phi(25) * 28

I'm not sure about complexity of GCD algorithm, but let's say O(log(n)), where n is the biggest from 2 input number.
So direct check has a complexity of about O(n*log(n)).
It is a bit difficult to estimate the complexity of proposed above optimization, but I think that it is about the same. What do you think? Do you also have some other ideas?
If you offer a good test set to check the performance of both algorithm, I can code my idea and we can check it...