6
$\begingroup$

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<i$ 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?

$\endgroup$
9
  • 2
    $\begingroup$ 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$. $\endgroup$ Mar 4, 2019 at 2:26
  • 2
    $\begingroup$ 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$. $\endgroup$ Mar 4, 2019 at 2:53
  • 2
    $\begingroup$ 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$. $\endgroup$ Mar 4, 2019 at 3:22
  • 3
    $\begingroup$ 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$. $\endgroup$ Mar 4, 2019 at 13:01
  • 3
    $\begingroup$ 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$). $\endgroup$ Mar 4, 2019 at 13:12

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.