16
$\begingroup$

Given $n$ and $k$, find the number of pairs of integers $(a, b)$ which satisfy the conditions $n < a < k, n < b < k$ and $(ab-n)$ is divisible by $(a-n)(b-n)$. Given: $0 ≤ n ≤ 100000, \ n < k ≤ 10^{18}$.

Link to problem: http://www.codechef.com/SEPT11/problems/SHORT

  • 6
    For future reference, tagging a question both as elementary-number-theory and number-theory defeats the whole purpose of having two separate tags.2011-09-04
  • 0
    Is this some Project Euler kind of question? Can you provide the source?2011-09-05
  • 0
    This problem is taken from codechef. http://www.codechef.com/SEPT11/problems/SHORT2011-09-06
  • 1
    It might be simpler to find $a$ and $b$ where $ab|((a+n)(b+n)-n)$ or equivalently $ab|n(a+b+n-1)$.2011-09-06
  • 0
    Even in this expression,if we are going to find all pairs of (a,b) then running two loops for ($ 10^{18} * 10^{18}$ ) doesn't seem to be possible.I think there must be some theorem of mathematics which will make it easier to solve.2011-09-06
  • 0
    But the loops aren't (both) of that size. $ab|n(a+b+n-1)$ implies $ab \leq n(a+b+n-1)$ and $b|n(a+n-1)$. Assume WLOG $b \geq a$ then $a \leq n(a/b + 1 + (n-1)/b) < 3n$, and $b < 4n^2$. Yes, this is still a really big loop, but this starts the optimization.2011-09-06
  • 0
    @code_hacker can u tell where am i wrong with logic or ...any other issues like datatype of variables pastebin.com/qQHiwQWF2011-09-07

3 Answers 3

2

As noted in the comments, you can replace $(a,b)$ by $(a',b') = (a-n, b-n)$ and your condition then becomes $a'b' | n(a'+b'+n-1)$. I will make the replacement, and drop the primes.

$ab|n(a+b+n-1)$ implies $ab \leq n(a+b+n-1)$ and $b|n(a+n-1)$. Assume WLOG $b \geq a$ then $a \leq n(a/b + 1) + n(n-1)/b < n^2+n$, and $b < n^3 + 2n^2$.

But you only have to run the loop over $a$, you then use the fact that $b|n(a+n-1)$, factorize $n(a+n-1)$, and find all divisors $b$ in the range $[a,...k-n]$. Then for such pairs $(a,b)$ you check that they satisfy the condition $ab | n(a+b+n-1)$.

You can actually do better on the bounds of the a loop using the fact that $n(n−1)/b≤n(n−1)/a$, so $a≤2n+n(n−1)/a$. That is equivalent to $(a−n)^2≤2n^2−n$, so your loop is actually of size O(n).

Running the second loop from $[a,...,k-n]$ isn't wrong, it just takes too long. As to the implementation: 1) Generate a list of primes from 1 to $\sqrt{n}$. 2) Do trial division from this list of primes into n to get the factorization of n. 3) Create an array A of size $(1+\sqrt{2})n$. Each entry in the array should be a list of (prime, power) such that if this is in the $k$th entry of the array, $(n+k)$ is divisble by (prime) raised to (power). 4) You fill in this array by going thru the list of primes, finding the smallest number >= n that is divisible by prime^power, and incrementing by prime^power. 5) Now that you have the factorizations of n and all numbers in the range $[n,...,(2+\sqrt{2})n]$, you go thru and find divisors of $n*(n+k)$ that are greater than $k \space (= a-1)$. For each such divisor $b$, you check that $ab | n(a+b+n-1)$.

  • 0
    I implemented your method but it's not working.Here is my implementation of your method. http://pastebin.com/w5RTtQ7H2011-09-06
  • 0
    The problem is your inner loop on j. You don't want to actually loop on the entire range $[a,...,k-n]$. You want to factorize $n(a+n-1)$, then use the factorization to construct the set of divisors, then pick the ones that lie in the right range. Like Yuval said below, the most efficient way of doing this is first factorizing $n$, then using a sieve to simultaneously get the factorizations of all numbers in the range $[n, (2+\sqrt{2})n]$.2011-09-06
  • 0
    I'm facing difficulty in implementation of your method of finding all factors and then checking conditions.Can you give me some idea of implementation or some pseudocode.I'll be thankful to you.One more thing running second loop from [a,...,k-n] is wrong?2011-09-07
  • 0
    You may find it easier to use Jyrki's solution. It has longer asymptotic run time, I think (not sure tho), but for $n$ of this scale it should be fine.2011-09-07
  • 0
    I may be irritating you guyz but really I'm stuck with this problem even trying naive implementation gives me wrong answer again and again.Can you guyz please suggest me any point which I'm missing.Here is my implementation using Jyrki's first observation that a<3n and b<4n^2. http://pastebin.com/apK7MQcJ2011-09-07
  • 1
    We have explicitly stated that we are only counting the cases where $b \geq a$. 1) Your code doesn't do that. 2) Once you have the set of cases where $b > a$ and the set of cases where $b = a$, then your answer is 2 times the size of the first set, plus the size of the second set.2011-09-07
  • 0
    I modified my code but still same problem.My brain has stopped working because of continuously getting wrong answer.Here is my modified code. http://pastebin.com/apK7MQcJ Any other suggestion?2011-09-07
  • 0
    @code_hacker: Where did you get the impression that I claimed $a<2n$ and $b<4n^2$? I never said anything like that! I told that it is impossible for both $a$ and $b$ simultaneously to be $>n^2$. That means that if $a$b$ can be very large. I was just idly discussing, how I would approach the problem, not giving any definite bounds at that time. You took the example bounds out of context. I deleted those from the answer since. Please use the improved bound only. – 2011-09-08
2

Not a solution, but something to reduce the length of the search.

Isn't it so that if $a$ and $b$ are very large in comparison to $n$, then the number $(a-n)(b-n)$ is in the same ballpark as $ab-n$? Then their quotient can't be much larger than 1, but yet it has to be an integer!!

If $n>0$, we always have $(a-n)(b-n)=ab-an-bn+n^21$. As this is supposed to be a positive integer, we get something that we can take advantage of as follows.

Write $q(b)=(ab-n)(a-n)^{-1}(b-n)^{-1}$. Then it is easy to show that $q'(b)<0$, so $q(b)$ is a decreasing function with the limit $a/(a-n)$ as $b\to\infty$. So if $r$ is the smallest integer with the property $r>a/(a-n)$, then we get an upper bound for $b$ by solving the inequality $q(b)\ge r$. The bound reads $b\le n[r(a-n)-1]/[(r-1)a-rn]$.

  • 0
    Let me try to figure out the asymptotic runtime of this algorithm. For fixed $r$, we have $(a-n)r > a > (a-n)(r+1)$, or $n(r+1)/r > a > nr/(r-1)$. We also have $b \leq n[r(a-n) -1] / [(r-1)a - nr] = f(a;n,r)$. This bound is, I believe, quadratic in n for fixed r. Let's check. $$f'(a) = nr / [(r-1)a-nr] - (r-1)n[r(a-n) -1] / [(r-1)a -nr]^2 = $$ $$n/[(r-1)a -nr]^2 * [r(r-1)a - nr^2 - (r-1)r(a-n) - (r-1)] < 0,$$ so $f(a)$ has a maximum at the lower bound of a, where $f(a) = n(n+r+2)/(r-1)$. For fixed $r$, $a,b$ have ranges which are $O(n/r^2)$ and $O(n^2/r)$ respectively. Not a fast algorithm.2011-09-07
  • 0
    Yup. You're right. This beats $10^{18}\cdot 10^{18}$, but surely having any kind of efficient idea of using divisibility should beat this. I have trouble assessing the complexity of your approach, because generating that array does take time. Granted, you can reuse a lot of the effort, if the next call is for just a slight different value of $n$. IOW you can use a LUT to good effect.2011-09-07
  • 0
    I have implemented your method in C++ to solve the problem but it is giving me wrong answer again and again.Can you suggest me some mistakes in my program? Link to program: http://pastebin.com/apK7MQcJ2011-09-08
  • 0
    My native language is Pascal, sorry. I don't understand those nULLs at all. But where do you compute the integer $r$ for example?2011-09-08
  • 0
    I mean, the upper bound on $b$ depends on $a$, so you have to compute it inside the outer loop.2011-09-08
  • 0
    How to find value of r?2011-09-08
  • 0
    @code_hacker: It is the smallest integer that is larger than $a/(a-n)$. I don't know what primitive operations you programming tools give you, so I cannot answer in general. If you have the floor function at hand, then $r=floor(a/(a-n))+1$.2011-09-08
  • 0
    @Jyrki: I've fixed the initial comment (or at least, it's looking fixed on my computer).2011-09-08
  • 0
    @Zev: Great! Looks good on my screen, too. Your mod work is duly appreciated.2011-09-08
  • 0
    @Jyrki: No problem! Actually, since it sounded like you'd wanted to make an edit but were unable to, I could go ahead and make the edit for you now, if it's still applicable.2011-09-08
  • 0
    @Zev: I would have liked to edit a comment at that time, but ended up writing another one instead. That has actually since become obsolete, so I will delete the later comment instead. Very sorry to bother you about this.2011-09-08
  • 0
    @code_hacker: A point in this approach is that you must recompute the upper bound $y$ on line 24 before you enter the inner loop. First compute $r$ then $y$. Sorry about not making that clear - well, I thought it was made clear, but it was getting late :-).2011-09-08
  • 0
    @code_hacker: Note BTW that I am using the original meaning for $a$ and $b$, not those 'translated by $n$' as Craig. So you need to make the corresponding adjustments to your code all depending...2011-09-08
  • 0
    @Jyrki Lahtonen : I'm explaining you from starting that what am I going to do in my program,please correct me where I'm wrong.First I'll take input n and k.After that I'll run two loops,one for a and second from b where n2011-09-08
  • 0
    @code_hacker: The lower bound for $a$ is obviously $n+1$. The upper bound could be $n^2+2n$ from Craig's answer, but I didn't check that bit. Test it!. For $b$ the lower bound is $a$, and the upper bound is the one listed. Note that if $a$ is too large, then the upper bound for $b$ is lower than the lower bound, i.e. the inner loop is empty. It would be nice, if you could prove that after this happens for some $a$, it also happens for all the larger ones, because then you could use that as an exit condition. I would take testing the case $b=a$ out of the inner loop.2011-09-09
  • 0
    @Jyrki Lahtonen : I'm sorry to say this but I think your algorithm is not correct.I implemented this in my code based on our earlier discussion but still it doesn't work.Moreover this time it got wrong answer more quickly meaning code fails to run very early. Link to implementation: http://pastebin.com/VMNfaz132011-09-09
  • 0
    @code_hacker: For which values of $n$, $k$ did it fail? Did you debug it by having it list the $(a,b)$ pairs, and count them against some precalculated table? Which $(a,b)$ pairs were left out? This is essential for figuring out, where the bounds failed. Or how do you know that the program failed?2011-09-09
2

As mentioned above, we can use the transformation $c = a-n$, $d=b-n$ to rewrite the problem as $$ cd | (c+n)(d+n) - n = cd + n(c+d+n-1). $$ Equivalently, $$ cd | n(c+d+n-1), \quad 1 \leq c,d < k-n. $$ In particular, this implies that $cd \leq n(c+d+n-1)$ and so $$ c(d-n) \leq n(d+n-1). $$ Suppose that $d \geq (1+\sqrt{2})n$. In that case we can divide by $d - n$ and deduce that $$c \leq n \frac{d+n-1}{d-n} < n \frac{d+n}{d-n} = n \left(1 + \frac{2n}{d-n}\right) \leq (1+\sqrt{2})n. $$ So $$\min(c,d) \leq (1+\sqrt{2})n.$$

Fix some $c \leq (1+\sqrt{2})n$. For emphasis, we replace it with $C$. Rearranging, we have $$ Cd | nd + n(C+n-1) \triangleq nd + M. $$ This implies, in particular, that $d | M$. Hence it is enough to go over all factors of $M$. Since $M \approx n^2$, The average number of divisors is $2 \log n$, which is not too bad. Each of them can be tried separately.

It remains to efficiently find the factorization of all integers in the range $[n,(2+\sqrt{2})n]$. This can be done using a sieving algorithm (e.g. Eratosthenes) efficiently.

  • 0
    This is the same solution as Craig's.2011-09-06