# Finding when $(a-n)(b-n)|(ab-n)$

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

-
For future reference, tagging a question both as elementary-number-theory and number-theory defeats the whole purpose of having two separate tags. – Willie Wong Sep 4 '11 at 11:56
Is this some Project Euler kind of question? Can you provide the source? – Srivatsan Sep 5 '11 at 15:12
This problem is taken from codechef. codechef.com/SEPT11/problems/SHORT – code_hacker Sep 6 '11 at 12:28
It might be simpler to find $a$ and $b$ where $ab|((a+n)(b+n)-n)$ or equivalently $ab|n(a+b+n-1)$. – robjohn Sep 6 '11 at 15:20
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. – code_hacker Sep 6 '11 at 16:29

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.

-
This is the same solution as Craig's. – Yuval Filmus Sep 6 '11 at 22:35

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)$.

-
I implemented your method but it's not working.Here is my implementation of your method. pastebin.com/w5RTtQ7H – code_hacker Sep 6 '11 at 21:53
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]$. – Craig Sep 6 '11 at 22:48
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? – code_hacker Sep 7 '11 at 9:18
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. – Craig Sep 7 '11 at 12:57
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. – Craig Sep 7 '11 at 19:04

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^2<ab-n^2-n^2+n^2=ab-n^2\le ab-n$. So the quotient $q=(ab-n)/((a-n)(b-n))>1$. 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]$.

-
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. – Craig Sep 7 '11 at 13:16
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. – Jyrki Lahtonen Sep 7 '11 at 13:52
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: pastebin.com/apK7MQcJ – code_hacker Sep 8 '11 at 6:00
My native language is Pascal, sorry. I don't understand those nULLs at all. But where do you compute the integer $r$ for example? – Jyrki Lahtonen Sep 8 '11 at 6:32
I mean, the upper bound on $b$ depends on $a$, so you have to compute it inside the outer loop. – Jyrki Lahtonen Sep 8 '11 at 6:41