# Solving for solutions to $\left(a+b\right)^2=a.b$

I ran across this stackoverflow question regarding finding solutions to

$$\left(a+b\right)^2=a.b$$ for $$a,b\in\Bbb{N}$$ where $$a.b$$ denotes concatenation of $$a$$ and $$b$$. Since concatenation isn't really a "true" mathematical operation, I'll write $$\left(a+b\right)^2=a\times10^c+b$$

where $$c=\lfloor{log_{10}b}\rfloor+1$$. The post there also has an implicit stipulation that neither $$a$$ nor $$b$$ may contain leading zeros, but that does not matter for the sake of this question- I can filter those solutions later. I wish to gain some mathematical insight into the pattern of these solutions, so that maybe I can write a more efficient solver.

The naive method of searching for solutions by iterating over pairs of $$a$$ and $$b$$ takes $$O\left(n^2\right)$$ time. By instead iterating over all squares $$i^2$$, and decomposing each into $$\lfloor2\log_{10}i\rfloor$$ separate $$a,b$$ pairs, we can search for solutions in $$O\left(n\log(n)\right)$$ time. I've since realized that because $$a,b and $$a\times10^c+b=i^2$$, that $$a$$ and $$b$$ must both be within $$+0/-2$$ orders of magnitude of $$i$$, and so there is at most three possibly valid $$a,b$$ pairs per $$i^2$$. This brings the time complexity down to $$O\left(n\right)$$, but I still feel like there might be other mathematical insights that could allow me to prune other invalid $$a,b$$, whether they result in an asymptotic speedup or not.

Is there a closed-form solution to this problem, or any particular pattern to the $$a$$ and $$b$$ forming valid solutions?

• Reducing modulo $a$ gives $b^2 \equiv b \pmod a$, and hence $b^2 \equiv b \mod m$ if $m \mid a$. For generic $a$ this leads to strong restrictions on $b$. For prime $a = p$ (or prime factors $p$ of $a$) this implies $b = 0, 1 \pmod p$. Mar 4, 2019 at 2:26
• Your formula for concatenation isn't quite right. It's problematic when $b$ is a power of $10$. E.g., if $a=1$ and $b=10$, then $c=\lceil\log_{10}10\rceil=1$ and $a\times10^c+b=20$, not $110$. Mar 4, 2019 at 2:53
• One can just as well prune cases by reducing modulo $b$, which gives $a^2 = 10^c a \pmod b$. If $2 \mid b$, we get immediately that $2 \mid a$, likewise for $5$. Similarly, if $3 \mid b$, then we conclude that either $3 \mid a$ or $a \equiv (-1)^c \pmod 3$. Mar 4, 2019 at 3:22
• One simple pruning: $a$ must be even, since $(a+b)^2\equiv a+b$ mod $2$. So you might as well rewrite the equation to solve as $(2a+b)^2=2a\times10^c+b$. Also, $b$ cannot be congruent to $2$ or $3$ mod $5$, since $(a+b)^2$ is always $0$, $1$, or $4$. Mar 4, 2019 at 13:01
• One other simple pruning: As soon as $b$ has two or more digits, it must be congruent to $0$, $1$, or $4$ mod $8$, since those are the only residues for $(a+b)^2$ (and $a$, as noted in the previous column, is even, so $a\times10^c\equiv0$ mod $8$ if $c\ge2$). Mar 4, 2019 at 13:12