15
$\begingroup$

Does there exist any perfect square integer (other than $10^{2k}$) whose digits are only $0$ and $1$ in base 10 expression?

This just comes up in a leisure talk with my friends. Is that elementary or hard to prove? Any comment will be helpful.

some discussion i found on mathoverflow: https://mathoverflow.net/questions/22/can-n2-have-only-digits-0-and-1-other-than-n-10k

$\endgroup$
4
  • 4
    $\begingroup$ Presumably we are talking about base 10, right? If we were talking in base two then every number would have this property $\endgroup$
    – ASKASK
    Commented Apr 8, 2015 at 16:37
  • $\begingroup$ @user1008646 Such a small range says little. After all the number of $1$s must be $1\pmod 3$ or $0\pmod 9$, so only relatively few candidates for $n^2$ occur. $\endgroup$ Commented Apr 8, 2015 at 16:57
  • $\begingroup$ @ASKASK yeah. but i think every base >2 looks hard. $\endgroup$
    – AlgRev
    Commented Apr 8, 2015 at 17:19
  • $\begingroup$ @HagenvonEitzen you seem to be suggesting that the likelihood increases... $\endgroup$
    – Zach466920
    Commented Apr 8, 2015 at 19:09

1 Answer 1

1
$\begingroup$

No solution, just some heuristics:

Assume we have $0<n<10^k$ such that $n^2$ ends in $k$ digits $\{0,1\}$. Then for the numbers $n+10^kd$, $d\in\{0,\ldots,9\}$, we have $(n+10^kd)^2=n^2+2\cdot d\cdot 10^k+10^{2k}d^2$, which may or may not end in $k+1$ digits $\{0,1\}$. Success happens for exactly two choices of $d$, which only depend on the "next" digit of $n^2$. The two choices of $d$ differ by $5$ and produce the same next 0-1-digit in the square. This way, we obtain a binary tree of longer and longer possible ending sequences, starting from $1$: $$\begin{align} 1&\\&\to 01,51\\&\to 001,501,251,751\\&\to 0001,5001,0501,5501,4251,9251,3751,8751\\&\to\ldots\end{align}$$ [Another way to state this, is to note that $n^2\equiv a\pmod{10^k}$ has four solutions for any 0-1 remainder $a$ ending in $001$]

The question is if at some stage we are "lucky" and the next $k$ digits happen to be $0$s and $1$s. Very heuristically, the probaility for such an event is $5^{-k}$ and in each "generation" we have $2^k$ candidates. Thus each generation contributes $(\frac25)^k$ solutions on average, hence all generations together contribute $1+\frac25+\frac4{25}+\ldots=\frac53$ solutions, one of which is $1^2=1$. Thus we might expect that at most one extra solution might be found, and that relatively early ...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .