Saturday, October 6, 2012

Modifying the Euler Totient Funtion

Hi All, Came across an interesting problem and thought of sharing it. Most would know about the ETF , which basically helps one to count the number of integers co-prime and less than N . However to get the count of integers which are co-prime to N but less than a specified limit (say M <= N ) is not so common.

At first i thought of modifying the ETF calculation ETF calculation by initialising result to m . The results were 'almost' accurate but not correct. So as a turnaround , i got a different approach. We can factorise N and then from M do an inclusion-exclusion principle on the factors of N . i.e say the factors of N are p1,p2, . Then the required solution would be : M - sum(M/pi) (1<=i<=k) + sum(M/pi*pj) - ..sum(M/pi*pj*

Though i had got the result but coding it was the next challenge. 1. First step was easy as it involved just factoring N . (O(sqrt(N)))
2. Next we had to get all combinations of the factors, in other words all the subsets. This can be done by bitmask technique, i.e consider binary representation of integers and if the ith bit is set then the integer is in the set . We can store each subset in a vector and then based on the size of the subset calculate the denominator with appropriate sign!
3. Thus we can calculate the answer perfectly. :)

Hope it was useful. Finally a post after almost 6 months.Been really busy , specially after getting into this corporate world.