Блог пользователя DMGR

Solve number theory Inclusion/Exclusion problems without using exponential time
Автор DMGR, история, 9 лет назад, По-английски

For some number theory problems like finding Euler Totient Function for some number N,the method involves multiplying N by (1-1/p) for all primes p which divide N. This takes care of Inclusion Exclusion step as all additions/subtractions correspond to Inclusion/Exclusion step. However if the problem is modified to finding all numbers below K which are coprime to N, we cannot directly carry on the multiplications as some of the primes may not divide K completely and instead of this we have to carry on Integer divisions corresponding to each combination of prime divisors of N(2^x,if x prime divisors). So the solution which was linear in number of prime divisors is rendered exponential. Is their someway around this complication.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think Euler totient function is still exponential in terms of divisors ,

For example , if you run the Erathostenes Sieve version OR if you run the backtracking for all prime divisors of X for every 1<=X<=N you will do the same number of steps

The complexity quickness on Erathostenes Sieve comes from the fact that you can find the prime divisors very fast , instead of doing SQRT(X) steps for a random digit number.

I may be wrong as i just woke up from sleep :) , please correct me then :D

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Oh i understood it bad , as usual , You cannot solve normal inclusion/Exclusion problems without using expenential time in terms of divisors or something.

Euler totient function is a particular special case because it holds the property :

For every a,b two integers with gcd(a,b)!=1 φ(A⋅B)=φ(A)⋅φ(B) From this thing you can derive a nice mathematical formula instead of doing inclusion/exclusion

But for a general case you need some kind of back-tracking

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks. I was under the impression that there might be some shortcut technique which might give the answer even in this case but I think I was wrong.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What do you want to do? E.g. you can solve the problem "count all numbers below K which are coprime to N" with this approach (russian only) in time, where x is a number of prime divisors on N, if you know all prime divisors of N.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I was unable to understand the blog in the link as google translation was really unfathomable. The problem I was trying to solve was this. I was thinking of finding all the coprime fractions for all denominator values less than or equal to N which fall less than x/y. But I was exceeding the given time limit by 10 times. I thought that I might better it by finding someway to calculate the coprime fractions in linear time of number of prime divisors but I think I was wrong. I will try finding some other way. Thanks.

    → Ответить