20
$\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$
  • 2
    $\begingroup$ Of interest here: oeis.org/A034979 $\endgroup$ – Barry Cipra Jun 26 '17 at 11:51
  • $\begingroup$ @BarryCipra So, does something prevent a 2n digit perfect square from starting with >n ones? $\endgroup$ – JollyJoker Jun 26 '17 at 13:22
  • 1
    $\begingroup$ To answer my own question, apparently not. 11111111111111115805344390916 has 16 ones with 29 digits. $\endgroup$ – JollyJoker Jun 26 '17 at 13:42
  • 2
    $\begingroup$ @JollyJoker: I'm not sure that 29 counts as 2n... $\endgroup$ – Chris Jun 26 '17 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$ – Barry Cipra Jun 26 '17 at 14:37
23
$\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$
  • $\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 '17 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 '17 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 '17 at 15:49
  • 2
    $\begingroup$ Oh, I see. I misread it as multiplying the two values! $\endgroup$ – Chris Jun 26 '17 at 16:20
  • 3
    $\begingroup$ Yes, adding in a $+$ sign there would really improve the readability of this answer. I was confused too. $\endgroup$ – R.. Jun 27 '17 at 2:56
56
$\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$
  • 3
    $\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 '17 at 10:56
  • 14
    $\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$ – José Carlos Santos Jun 26 '17 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 '17 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$ – DanielWainfleet Jun 27 '17 at 0:47
  • $\begingroup$ @DanielWainfleet Why don't you publish this as an answer, instead of being simply a comment? $\endgroup$ – José Carlos Santos Jun 27 '17 at 6:59
19
$\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 an $2n+1$ digits can begin with more than $n+1$ $1$'s.

$\endgroup$
5
$\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$
4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ yes. I am looking for a way to arrive at what you said without manual calculation. $\endgroup$ – rm92 Jun 26 '17 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 '17 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 '17 at 12:35
  • 1
    $\begingroup$ @stity my mistake, I miscounted the 1s $\endgroup$ – Hugh Jun 26 '17 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$
  • 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$ – James Waldby - jwpat7 Jun 26 '17 at 20:37
  • $\begingroup$ @JamesWaldby-jwpat7 Good point! I included that as an alternative. $\endgroup$ – Joonas Ilmavirta Jun 26 '17 at 20:41
  • 1
    $\begingroup$ Numbers like $1111111111^2$ are called wonderful Demlo numbers. $\endgroup$ – Jeppe Stig Nielsen Jun 26 '17 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.