21
$\begingroup$

Why a $20$ digit number starting with eleven $1$'s cannot be a perfect square?

I haven't been able to figure out which properties of perfect squares disallows such a number from being a perfect square.

$\endgroup$
9
  • 2
    $\begingroup$ Of interest here: oeis.org/A034979 $\endgroup$ Jun 26, 2017 at 11:51
  • $\begingroup$ @BarryCipra So, does something prevent a 2n digit perfect square from starting with >n ones? $\endgroup$
    – JollyJoker
    Jun 26, 2017 at 13:22
  • 1
    $\begingroup$ To answer my own question, apparently not. 11111111111111115805344390916 has 16 ones with 29 digits. $\endgroup$
    – JollyJoker
    Jun 26, 2017 at 13:42
  • 2
    $\begingroup$ @JollyJoker: I'm not sure that 29 counts as 2n... $\endgroup$
    – Chris
    Jun 26, 2017 at 14:32
  • 3
    $\begingroup$ @Chris, yes, JollyJoker's example caused me to doubt my answer. It was only when I couldn't find a mistake in what I'd done that it occurred to me that $29$ is odd. $\endgroup$ Jun 26, 2017 at 14:37

7 Answers 7

63
$\begingroup$

That's because\begin{align*}3\,333\,333\,333^2&<11\,111\,111\,111\,000\,000\,000\\&<11\,111\,111\,111\,999\,999\,999\\&<3\,333\,333\,334^2.\end{align*}

$\endgroup$
10
  • 4
    $\begingroup$ how did you arrive at this conclusion? could you tell me the first time you solved it how did approach the solution to this problem? $\endgroup$
    – rm92
    Jun 26, 2017 at 10:56
  • 16
    $\begingroup$ @rm92 I used a computer to comput the square roots $11\,111\,111\,111\,000\,000\,000$. It is slightly larger than $n=3\,333\,333\,333$. Then I computed $n^2$ and $(n+1)^2$. $\endgroup$ Jun 26, 2017 at 11:02
  • 2
    $\begingroup$ Just a comment on finding the square root with a computer: if the question happened to involve larger numbers such that a computer was infeasible, or if computer access was lacking, one could start with a very small case (6-digit number starting with 4 ones) and see the pattern. $\endgroup$
    – 6005
    Jun 26, 2017 at 23:06
  • 1
    $\begingroup$ If |a|<1 then $1-|a|/(2+|a|) \leq \sqrt {1+a}\; \leq1+|a|/2$..... If $n$ is a $20$-digit number starting with $11$ ones then $n=(1+a)10^{20}/9$ with $|a|<10^{-10}.$ So $(1-|a|/(2+|a|))10^{10}/3\leq \sqrt n\;\leq (1+|a|/2)10^{10}/3$, yielding the inequality in the A above. $\endgroup$ Jun 27, 2017 at 0:47
  • $\begingroup$ @DanielWainfleet Why don't you publish this as an answer, instead of being simply a comment? $\endgroup$ Jun 27, 2017 at 6:59
22
$\begingroup$

Adding onto the answer by José Carlos Santos, here's a way to compute the approximate square root by hand efficiently:

$$\sqrt{11111111111000000000} < \sqrt{11111111111111111111 + \frac{1}{9}} < \sqrt{11111111111999999999}$$ $$\sqrt{11111111111111111111 + \frac{1}{9}} = \sqrt{\frac{10^{20}}{9}} = \frac{10^{10}}{3} = 3333333333 + \frac{1}{3}$$

Then, how to check that the neighboring squares fall outside the desired range, by hand:

\begin{align*} \left\lfloor\frac{10^{10}}{3}\right\rfloor^2 &= \left(\frac{10^{10}}{3} - \frac{1}{3}\right)^2 \\ &= \left(\frac{10^{10}}{3}\right)^2 - 2\left(\frac{10^{10}}{3}\right)\left(\frac{1}{3}\right) + \left(\frac{1}{3}\right)^2 \\ &= \frac{10^{20}}{9} - \frac{2\times10^{10} - 1}{9} \\ &< \frac{10^{20}}{9} - \frac{10^9}{9} \\ &= 11111111111000000000 \end{align*}

\begin{align*} \left\lceil\frac{10^{10}}{3}\right\rceil^2 &= \left(\frac{10^{10}}{3} + \frac{2}{3}\right)^2 \\ &= \left(\frac{10^{10}}{3}\right)^2 + 2\left(\frac{10^{10}}{3}\right)\left(\frac{2}{3}\right) + \left(\frac{2}{3}\right)^2 \\ &> \frac{10^{20}}{9} + \frac{4\times10^{10}}{9} \\ &> \frac{10^{20}}{9} + \frac{8\times10^9}{9} \\ &= \frac{10^{20}}{9} - \frac{10^9}{9} + 10^{9}\\ &= 11111111111000000000 + 10^{9} \\ &> 11111111111999999999 \end{align*}

$\endgroup$
6
  • $\begingroup$ Thank you. I was trying the same approach now after another answer pointed it out to me but with inequalities. But this is a neater way to put it. $\endgroup$
    – rm92
    Jun 26, 2017 at 12:50
  • $\begingroup$ I'm not sure I understand your first equality of your second line... It seems to say that $11111111111111111111$ is equal to $10^{20}$. Is there meant to be inequailities or something else there? $\endgroup$
    – Chris
    Jun 26, 2017 at 14:40
  • $\begingroup$ @Chris, $a\frac{b}{c}$ is a mixed fraction and has a value of $a+\frac{b}{c}$ $\endgroup$
    – Phu Ngo
    Jun 26, 2017 at 15:49
  • 2
    $\begingroup$ Oh, I see. I misread it as multiplying the two values! $\endgroup$
    – Chris
    Jun 26, 2017 at 16:20
  • 4
    $\begingroup$ Yes, adding in a $+$ sign there would really improve the readability of this answer. I was confused too. $\endgroup$ Jun 27, 2017 at 2:56
20
$\begingroup$

Let's show more generally that a $2n$-digit square cannot begin with $n+1$ $1$'s.

Note that the smallest $2n$-digit number beginning with $n+1$ $1$'s is

$$11{\ldots}110{\ldots}0={10^{2n}-10^{n-1}\over9}$$

and the largest is

$$11{\ldots}119{\ldots}9={10^{2n}-10^{n-1}\over9}+10^{n-1}-1={10^{2n}+8\cdot10^{n-1}-9\over9}$$

Since $10^{n-1}\lt2\cdot10^n-1$ while $8\cdot10^{n-1}-9\lt2\cdot10^n+1$, we obtain

$$\left(10^n-1\over3 \right)^2={10^{2n}-2\cdot10^n+1\over9}\lt{10^{2n}-10^{n-1}\over9}=11{\ldots}110{\ldots}0$$

while

$$11{\ldots}119{\ldots}9={10^{2n}+8\cdot10^{n-1}-9\over9}\lt{10^{2n}+2\cdot10^n+1\over9}=\left(10^n+1\over3\right)^2$$

Thus if $11{\ldots}110{\ldots}0\le N\le11{\ldots}119{\ldots}9$, then

$${10^n-1\over3}\lt\sqrt N\lt{10^n+1\over3}\lt{10^n+2\over3}$$

But $(10^n-1)/3$ and $(10^n+2)/3$ are consecutive integers (their difference is $1$). So $\sqrt N$ cannot be an integer.

Remark 1: This answer owes much of its logic to a now-deleted answer by achille hui.

Remark 2: This answer was motivated by JollyJoker's first comment beneath the OP. JJ's follow-up comment there makes it clear that squares with $2n+1$ digits can begin with more than $n+1$ $1$'s.

$\endgroup$
7
$\begingroup$

If $|a|<1$ then $1-\frac {|a|}{2+|a|}\leq \sqrt {1+a}\;\leq 1+\frac {|a|}{2}.$

If $n$ is a $20$-digit number beginning with $11$ ones then $n=(1+a)10^{20}/9$ with $|a|<10^{-10},$ so $$\left(1-\frac {|a|}{2+|a|}\right)10^{10}/3 \leq\sqrt n\;\leq \left(1+\frac {|a|}{2}\right)10^{10}/3$$ which immediately implies $3 333 333 333<\sqrt n\;<3 333 333 334.$

$\endgroup$
5
$\begingroup$

There is no integer between $\sqrt{11111111111000000000}$ and $\sqrt{ 11111111112000000000}$

$\endgroup$
4
  • 2
    $\begingroup$ yes. I am looking for a way to arrive at what you said without manual calculation. $\endgroup$
    – rm92
    Jun 26, 2017 at 10:47
  • 1
    $\begingroup$ Surely your second number should have a nines as the remaining digits instead of a 2 or 0s $\endgroup$
    – Hugh
    Jun 26, 2017 at 11:56
  • 1
    $\begingroup$ @Hugh if there is no integer between $\sqrt{11111111111000000000}$ and $\sqrt{11111111112000000000}$ then there is no integer between $\sqrt{11111111111000000000}$ and $\sqrt{11111111111999999999}$ $\endgroup$
    – stity
    Jun 26, 2017 at 12:35
  • 1
    $\begingroup$ @stity my mistake, I miscounted the 1s $\endgroup$
    – Hugh
    Jun 26, 2017 at 12:52
4
$\begingroup$

Let me explain how I would approach this manually (without excessive calculations or calculators); the conclusion will be the same as in the answer by José Carlos Santos. Some amount of computation is inevitable since the numbers are large. In fact, even more is true than your problem asserts; there is no 20-digit number with ten leading ones which is a perfect square.

First, observe that $$ (0.333\dots)^2=(1/3)^2=1/9=0.111\dots $$ A 20-digit number with many leading ones will be close to $10^{20}\times0.111\dots$, so its square root will be close to $10^{10}\times0.333\dots\approx3\,333\,333\,333$.

This means that we have an approximate square root $a=3\,333\,333\,333$. So far, we don't know how good this approximation is. Now, computing the square of this $a$ is a bit laborious. First, you can hopefully convince yourself that $$ (1\,111\,111\,111)^2=1\,234\,567\,900\,987\,654\,321. $$ To see this, multiply the number $1\dots1$ with $1$, $10$, $100$ and so forth, and sum these up — a pattern will emerge. To get the square of $a$, multiply by $3^2=10-1$. This is fairly simple, given the structure of the number above, so that $$ a^2=11\,111\,111\,108\,888\,888\,889. $$ An alternative method for squaring $a$ was suggested in a comment by James Waldby: Since $a=\frac13(10^{10}-1)$, we have $a^2=\frac19(10^{20}-2\cdot10^{10}+1)$.

The next integer square is $$ (a+1)^2=a^2+2a+1=11\,111\,111\,155\,555\,555\,556, $$ which again is pretty easy to calculate mentally since the numbers are so nice.

Since the two numbers $$ 11\,111\,111\,108\,888\,888\,889\text{ and}\\ 11\,111\,111\,155\,555\,555\,556\phantom{\text{ and}} $$ are consecutive integer squares, no integer square of 20 digits starts with a run of more than nine ones.

If instead of precise calculations you used crude approximations, you would still get the desired result for eleven ones.

$\endgroup$
3
  • 1
    $\begingroup$ I think computing the square of a=3333333333 as follows is easier: a=(10^10-1)/3, a^2 = (10^20 - 2*10^k +1)/9 $\endgroup$ Jun 26, 2017 at 20:37
  • $\begingroup$ @JamesWaldby-jwpat7 Good point! I included that as an alternative. $\endgroup$ Jun 26, 2017 at 20:41
  • 1
    $\begingroup$ Numbers like $1111111111^2$ are called wonderful Demlo numbers. $\endgroup$ Jun 26, 2017 at 21:56
2
$\begingroup$

Let $x$ be a positive integer with $2n$ digits when written in base $b>1$, where the $n+1$ first digits are 1's, and where we will assume that $b-1=d^2$ is a perfect square. Note that this holds in the decimal system ($b=10$), as $10-1=9=3^2$. It also holds in the binary system ($b=2$), and with respect to several other bases.

Assume that $x$ is a perfect square, $x=c^2$. Then $$b^{2n-1}+\dots+b^{n-1}\leq c^2\leq b^{2n-1}+\dots +b^{n-1}+(b-1)\Bigl(b^{n-2}+\dots+1\Bigr)$$ Summing the geometric series, we get $$b^{n-1}{b^{n+1}-1\over b-1}\leq c^2\leq b^{n-1}{b^{n+1}-1\over b-1}+(b^{n-1}-1)$$ Multiply by $b-1=d^2$ and subtract $b^{2n}$. This gives $$-b^{n-1}\leq c^2d^2-b^{2n}\leq -b^{n-1}+(b-1)(b^{n-1}-1)$$ It follows that $$-b^{n-1}\leq (cd+b^n)(cd-b^n)<b^{n}$$ Now $d$ divides $b-1$, and hence $d$ cannot divide $b^n$. So $cd-b^n$ is a nonzero integer, but then one of the inequalities above must be violated. It follows that the assumption that $x$ was a perfect square cannot hold.

Edit: An example to show that the result is not true in all bases. Let $b=n=3$, and observe that $(111101)_3=1\cdot 3^5+1\cdot 3^4+1\cdot 3^3+1\cdot 3^2+1\cdot 3^0=361=19^2$ is a perfect square with $n+1=4$ initial 1's. But then $b-1=2$ is not a perfect square, as was required in the argument above.

$\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.