11
$\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$
  • 3
    $\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 Apr 8 '15 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$ – Hagen von Eitzen Apr 8 '15 at 16:57
  • $\begingroup$ @ASKASK yeah. but i think every base >2 looks hard. $\endgroup$ – AlgRev Apr 8 '15 at 17:19
  • $\begingroup$ @HagenvonEitzen you seem to be suggesting that the likelihood increases... $\endgroup$ – Zach466920 Apr 8 '15 at 19:09
0
$\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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.