29
$\begingroup$

The title says it all. I'm simply looking for a proof to my answer of 2582. I used an obscure method that I perceived would yield the answer but I have no idea why it works.

I first calculated the square of the ceiling value of the square root of 6666. That didn't work so my intuition told me to repeat that process with 66660 instead of 6666. That still didn't work. It took me till the iteration with replacing 6666 with 6666000 to find that the square of the ceiling function of the square root of 6666000 is 6666724, the integer responsible being 2582.

Can someone please help? I found the answer but I want a more mathematical reasoning to my answer.

$\endgroup$
  • 26
    $\begingroup$ I wouldn't call "trial-and-error"—even educated trial-and-error—an obscure method. It has solved many a problem in the past. Strictly speaking, computing $2582^2 = 6666724$ is a proof, and quite an irrefutable one at that. What exactly are you looking for? $\endgroup$ – Brian Tung Oct 23 '15 at 1:47
  • 3
    $\begingroup$ I'm not quite sure myself; I'm pretty new to this kind of mathematics. I guess I was hoping for something more beautiful. This seemed so algorithmic: I didn't quite like it. $\endgroup$ – Adrian Mungroo Oct 23 '15 at 1:52
  • 8
    $\begingroup$ I believe he wants a more constructive proof of how one would "create" this number 2582. $\endgroup$ – Jake Oct 23 '15 at 1:52
68
$\begingroup$

You need $6666\times 10^k \leq x^2<6667\times 10^k$

If $k=2n$ is even, then this means:

$$10^{n}\sqrt{6666}\leq x\leq 10^{n}\sqrt{6667}$$

$\sqrt{6666}\approx 81.646$ and $\sqrt{6667}\approx 81.652$, so we can see that for $n=2$, $x=8165$ will work.

If $k=2n+1$ is odd, then you need:

$$10^{n}\sqrt{66660}\leq x\leq 10^{n}\sqrt{66670}$$

$\sqrt{66660}\approx 258.186$ and $\sqrt{66670}\approx 258.205$ and we get for $n=1$ that $x=2582$.

If you want to start with $D$, note that $\sqrt{D+1}-\sqrt{D}=\frac{1}{\sqrt{D+1}+\sqrt{D}} > \frac{1}{\sqrt{4D+2}}$. So at the very least, if $k>\log_{10}(4D+2)$ then $10^{k/2}\sqrt{D+1}-10^{k/2}\sqrt{D}>1$ so there must be an integer $x$ such that:

$$10^{k/2}\sqrt{D}\leq x<10^{k/2}\sqrt{D+1}$$ This technique would work for cubes, too, but you'd have to separate the question into three cases, $k=3n,k=3n+1,k=3n+2$. For $m$th powers, you consider $m$ cases.

For example, the smallest integer such that $x^7$ starts with $6666$ is $x=4888$.

$\endgroup$
  • 4
    $\begingroup$ This is what I was looking for. Thank you. $\endgroup$ – Adrian Mungroo Oct 23 '15 at 2:01
  • $\begingroup$ Did you mean "so we can see that for $n = 2$" for the first case? $\endgroup$ – jeremy radcliff Jan 18 '17 at 14:22
  • $\begingroup$ Yep, shoulda been $n=2$. Fixing. $\endgroup$ – Thomas Andrews Jan 18 '17 at 14:28
7
$\begingroup$

Theoretically, you are essentially using the formula $\sqrt{100x}=10\sqrt{x}$.

Your iterations are, essentially, first compute $\sqrt{6666}=81.6455...$. You multiply exponentials of $10$ to get larger numbers, and apparently the second just works: $8165^2=66667225$.

There are two types of solutions: numbers starting from $\sqrt{6666}=81.6455...$ and numbers starting from $\sqrt{66660}=258.1859...$ and your answer is the second case. The "third" case would be numbers starting from $\sqrt{666600}$ which is just the same as the first case.

$\endgroup$
5
$\begingroup$

I'm both a programmer and a (quite amateur) mathematician. I wrote this python 3 program before looking at the answers just for fun (I hand calculated that the answer must start with either 81 or 25):

from math import sqrt

def f(n):
    for d in range(10):
        for i in range(10**d):
            x = n * 10**d + i
            y = x * x
            if str(y)[0:4] == '6666':
                print (x, y)
                return

if __name__ == '__main__':
    f(81)
    f(25)

prints out:

2582 6666724
8165 66667225

and runs well under a tenth of a second on my laptop.

$\endgroup$
3
$\begingroup$

One methodical way to find the answer with just pencil and paper is to use the "long division" algorithm for extracting a square root.

The first step of this algorithm is to group the digits of your input number in pairs. For example, to take the square root of $6666$, we first write $$ \sqrt{66 \; 66}. $$

The first few steps of the algorithm result in

\begin{array}{r} 8 \;\phantom{0}1 \\[-3pt] 4 \sqrt{66 \; 66} \\[-3pt] \underline{64}\;\phantom{66} \\[-3pt] 16\underline1|\phantom{0}2 \; 66 \\[-3pt] \underline{1 \; 61}\\[-3pt] 162\underline{\ } |1 \; 05 \\[-3pt] \end{array}

The next step in the usual algorithm is to append a pair of zeros after the decimal point of the number under the square root in order to calculate one additional digit after the decimal point of the result. Alternatively, however, we can simply insert a pair of zeros to the left of the decimal point, that is, multiply the number under the square root sign by $100$. All the previous steps remain valid, and we can append one digit to the result; that is, if we had previously set up to calculate $\sqrt x$, we now calculate $\sqrt{100x} = 10 \sqrt x$:

\begin{array}{r} 8 \;\phantom{0}1 \;\phantom{0}6 \\[-3pt] 4 \sqrt{66 \; 66 \; 00} \\[-3pt] \underline{64}\; \phantom{66 \; 00} \\[-3pt] 16\underline1|\phantom{0}2 \; 66 \phantom{\; 00}\\[-3pt] \underline{1 \; 61} \phantom{\; 00}\\[-3pt] 162\underline{6} |1 \; 05 \; 00 \\[-3pt] \underline{97 \; 56} \\[-3pt] 7 \; 44 \end{array}

Now, in any "fully worked" example of the "long division" algorithm for the square root such as the example above, let $x$ be the number under the square root sign, let $y$ be the result (one digit for each pair of digits in $x$), and let $R$ be the result of the last subtraction step. In the example above, $x = 66600$, $y = 861$, and $R = 744$. Then in general, $$ y^2 = x - R.$$

This is an essential part of how the "long division" algorithm for the square root works. As a result, if we start with $x=6666$ and keep appending pairs of zeros to $x$, we will always have $y^2 = 6666 \times 10^n - R$, where $n$ is even. But because $6666$ is not a perfect square, $R$ will never be zero, so $y^2$ will always be somewhat less than $6666 \times 10^n$, and it will never have $6666$ as its first four digits.

So instead of $6666$, we can put $6667$ under the square root sign. Then we will compute $y$ such that $$y^2 = 6666 \times 10^n + 10^n - R,$$ so the first four digits of $y^2$ will be $6666$ if and only if $R \leq 10^n$. But we will never find that $R$ is an even power of ten (for the same reason that $6666 \times 10^n$ will never be a perfect square), so actually we require $R < 10^n$.

In short, we take the square root of $6667 \times 10^n$ for even $n$, using the "long division" square-root algorithm, increasing $n$ by two until the remainder of the last subtraction step has no more digits than the number of trailing zeros under the square root sign. At that point, the result of the algorithm is the desired number. This occurs when we have four digits in the result:

\begin{array}{r} 8 \;\phantom{0}1 \;\phantom{0}6 \;\phantom{0}5 \\[-3pt] 4 \sqrt{66 \; 67 \; 00 \; 00} \\[-3pt] \underline{64}\; \phantom{66 \; 00\; 00} \\[-3pt] 16\underline1|\phantom{0}2 \; 67 \phantom{\; 00\; 00}\\[-3pt] \underline{1 \; 61} \phantom{\; 00\; 00}\\[-3pt] 162\underline{6} |1 \; 06 \; 00 \phantom{\; 00}\\[-3pt] \underline{97 \; 56} \phantom{\; 00}\\[-3pt] 1632\underline{5} |\phantom{0}8 \; 44 \; 00 \\[-3pt] \underline{8 \; 16 \; 25}\\[-3pt] 27 \; 75 \end{array}

Checking the result, we find that indeed $$ 8165^2 = 66667225 = 6667 \times 10^4 - 2775,$$ as expected.

We can continue appending pairs of zeros to find larger numbers with the desired property. Actually, for any larger numbers of digits we will find a range of answers, the maximum being the number found by the algorithm and the minimum being $8165$ followed by some zeros.

Of course this gives us only numbers whose square is $6666$ followed by an even number of digits. To find numbers whose square is $6666$ followed by an odd number of digits, we need to start with $66670$ rather than $6667$. When applying the square root algorithm to a number with an odd number of digits, we treat the first digit as a "pair" by itself, so the algorithm proceeds like this:

\begin{array}{r} 2 \;\phantom{0}5 \;\phantom{0}8 \;\phantom{0}2 \\[-3pt] 4 \sqrt{6 \; 66 \; 70 \; 00} \\[-3pt] \underline{4}\; \;\phantom{6 \; 00\; 00} \\[-3pt] 4\underline5|2 \; 66 \phantom{\; 00\; 00}\\[-3pt] \underline{2 \; 25} \phantom{\; 00\; 00}\\[-3pt] 50\underline{8}|\phantom{0}\;41 \; 70 \phantom{\; 00}\\[-3pt] \underline{40 \; 64} \phantom{\; 00}\\[-3pt] 516\underline{2}|\phantom{0}1 \; 06 \; 00 \\[-3pt] \underline{1 \; 03 \; 24}\\[-3pt] 2 \; 76 \end{array}

So the algorithm comes up with your number $2582$ directly. And indeed we find that $$ 2582^2 = 6666724 = 6667 \times 10^3 - 276.$$

$\endgroup$
2
$\begingroup$

Let $\lceil x \rceil$ be the ceiling function applied to $x$. Thus, $\lceil x \rceil = x + \varepsilon$ for some $0 \leq \varepsilon < 1$.

$$\lceil \sqrt{x} \rceil^2 = (\sqrt{x} + \epsilon)^2 = x + 2 \sqrt{x} \varepsilon + \varepsilon^2$$

Your method of approximating the square root with the ceiling function therefore gives something whose square is relatively close to the original number; the error is smaller than $2 \sqrt{x} + 1$, which is much smaller than $x$.

You are using $x = 6666 \cdot 10^n$; consequently, and you win as soon as the error is less than $10^n$. We can guarantee this by finding an $n$ such that

$$ 2 \sqrt{6666 \cdot 10^n} + 1 < 10^n $$

We could actually solve this, as it is quadratic in $\sqrt{10^n}$, but it's far easier to just use trial and error; $n=5$ is the smallest value where this is true, and consequently, we must have

$$ \lceil \sqrt{666600000} \rceil^2 = 6666xxxxx $$

where the $x$'s stand in for unknown digits (although you could compute it).

It turns out that, by 'chance', this works with $n$ as low as $n=3$, as the corresponding $\varepsilon$ is relatively small.

$\endgroup$
1
$\begingroup$

Here's another computer program solution, but much faster than sysreq's answer.

import math

for k in range(8): # arbitrary upper limit
    # Find bounds on the sqrt of integers starting with 6666
    lower_bound = math.sqrt(6666 * 10**k)
    upper_bound = math.sqrt(6667 * 10**k)
    # Print any integers within this range
    n = math.ceil(lower_bound)
    while n <= upper_bound:
        print(n)
        n += 1
$\endgroup$
  • 1
    $\begingroup$ Even that computes too many square roots, since you only really need $\sqrt{6666},\sqrt{6667},\sqrt{66660},$ and $\sqrt{66670}$. ($\sqrt{666600}=10\sqrt{6666}$.) $\endgroup$ – Thomas Andrews Oct 24 '15 at 13:48
  • $\begingroup$ Better too many than too few. Also, it might be safer to add one to the upper bound. $\endgroup$ – marty cohen Oct 27 '15 at 23:41

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.