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$
    – Travis Willse
    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$
    – Barry Cipra
    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$
    – Travis Willse
    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$
    – Barry Cipra
    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$
    – Barry Cipra
    Mar 4, 2019 at 13:12

0

Reset to default

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.