# Can this puzzle be solved without brute force?

Consider positive integers $a$ and $b$, where $a \ge b$ and the sum $\frac{a+1}{b}+\frac{b+1}{a}$ is also an integer. Find the sum of all $a$ values less than $1000$ that meet this criteria.

For example, if $a=3$ and $b=2$, then $$\frac{a+1}{b}+\frac{b+1}{a} = \frac{3+1}{2}+\frac{2+1}{3} = 3$$ which is an integer and provides one legal value of $a$. The problem asks for all such values of $a \lt 1000$. I’m assuming that a particular $a$ suffices if there exists even one $b \le a$ that satisfies the condition.

This problem can be solved by simply writing a computer program that double-loops through the positive integers less than 1000, testing each case, however I’m wondering if there is a more general/abstract way to solve it.

Here are some thoughts … I’m not sure how helpful they are:

1. $\frac{a+1}{b}+\frac{b+1}{a}$, which is an integer, can be rewritten as $\frac{a}{b}+\frac{b}{a}+\frac{1}{b}+\frac{1}{a}$.
2. either the quotients $(a+1) \div b$ and $(b+1) \div a$ are each also integers, or their fractional parts add up to $1$.
• This might be helpful: oeis.org/A182756 – Luckyluck63 Apr 26 '16 at 3:08
• – individ Apr 26 '16 at 4:36
• In 2, I think you meant the fractional parts, not remainders. I think you can prove that both of $a+1/b$ and $b+1/a$ are integers. – TheRandomGuy Apr 26 '16 at 9:20
• And could you tell what solutions you found? I think this is the only one. – TheRandomGuy Apr 26 '16 at 9:27
• @Dhruv Another solution for $(a,b)$ is $(6,3)$ because $7/3 + 4/6$ is an integer. To answer your first question, these fractions aren't integers though their sum is. – chharvey Apr 26 '16 at 22:28

We use a now-standard technique called Vieta jumping, which has a fascinating and surprisingly recent history.

Suppose $a^2 + a + b^2 + b = kab$ for some integer $k$. Then, writing this as a polynomial in $a$ with integer coefficients:

$$a^2 - (kb-1) a + (b^2+b) = 0,$$

we see that if $(a,b)$ is one of the roots of the above quadratic, then the other one is $c = (b^2+b)/a$, which is clearly positive. Furthermore, since the two roots sum to an integer, namely $kb-1$, then $c$ is necessarily a positive integer.

Now let's consider sizes. If $a>b$, then $a \ge b+1$ so $c = b(b+1)/a \le b$. So if $(a,b)$ is one solution to the problem, then either $a=b$ or $(b,c)$ is a smaller solution, with the same value of $k$. Since all values remain positive, they can only get smaller finitely many times, so eventually we must reach a solution where $a=b$.

The case where $a=b$ is very easy: we must have $k = 2 + 2/a$, so the only solutions of this type are $(1,1)$ with $k=4$ and $(2,2)$ with $k=3$.

Finally, since every solution eventually reduces to either $(1,1)$ or $(2,2)$ by the reduction process, we can recover all solutions by running the process in reverse, starting from $(1,1)$ and $(2,2)$:

$$(1,1) \leftarrow (2,1) \leftarrow (6,2) \leftarrow (21,6) \leftarrow \cdots$$ $$(2,2) \leftarrow (3,2) \leftarrow (6,3) \leftarrow (14,6) \leftarrow \cdots$$

The values grow exponentially, so it doesn't take long for either sequence to exceed $1000$.