0
$\begingroup$

Yesterday I gave my 10-year-old son the following problem:

"Given an arbitrary positive integer, find the nearest perfect square."

This is his solution (pseudocode):

int tal = input("Enter an integer: ")
float x = sqrt(tal)
int a = round(x)
print(a*a)

When I saw the solution I immediately told him it was wrong.

But is it?

His solution is obviously wrong if tal isn't restricted to the positive integers.

However if tal is a positive integer I haven't found any counterexample that proves that my sons algorithm is wrong. In fact I have tested all integers 1 to 10^9. However, I haven't been able to prove that the algorithm is correct, or incorrect. (This is annoying since my intention was to teach him exactly that the algorithm he came up with is incorrect. The restriction of the domain to the positive integers was to make it easier to parse the input to the program.)

There are two possible perfect squares to consider.

I only consider "rounding up", since the other case is similar.

If tal = x^2 is a positive integer and (x+r) is an integer for some 0 < r < 1/2, then we have (x + r)^2 = x^2 + r^2 + 2xr, which is a perfect square.

The "other" perfect square to consider is, with s = 1-r: (x - s)^2 = x^2 + s^2 - 2xs

The difference of the differences to x^2 is: dd(r,x) = d1 + d2 = 1 + 2r^2 + 4xr - 2r - 2x = = 1 - 2r + 4xr - 2x + 2r^2 -> 1/2 as r -> 1/2, for any x.

However, the limit is a simplifications, and not correct, since in reality x=f(tal) and r = g(x).

Nevertheless if the algorithm is correct then dd < 0.

For 2x(2r -1) it seems that when tal = x^2 is an integer if I try to make r as close to 1/2 as possible x grows "fast" enough to offset (2r - 1) tending to 0, thus making abs(ddb) > r^2 - 2r + 1.

Anyway, if my sons algorithm is correct it must rely on tal being a positive integer (and nothing in my reasoning above is applicable only if tal is a positive integer).

Is the algorithm incorrect or not?


The answer (fixed some typos and added small changes), from @fleablood

For all positive numbers $m$ there is a non-negative integer $n$ such that $n^2 \le m < (n+1)^2= n^2 + 2n + 1$.

If $n^2 \le m \lt n^2 + n + \frac 12$ then the nearest square is $n^2$. If $n^2 + n + \frac 12 < m < n^2 + 2n + 1$ then the nearest square is $(n+1)^2$. Thus for an integer $m$ if $n^2 \le m \le n^2 + n$ the nearest square is $n^2$, and if $n^2 + n + 1 \le m < n^2 + 2n + 1$ the nearest square is $(n + 1)^2$.

Taking square roots: $n \le \sqrt{m} < n+1$.

When we round $\sqrt{m}$ we will get $n$ if $n \le \sqrt{m} \lt n+ \frac 12$ and $n+1$ if $\sqrt{m} > n + \frac 12$.

If $n \le \sqrt{m} \lt n+ \frac 12$ then $n^2 \le m \lt n^2 + n + \frac 14 $. However since $m$ is an integer $m \le n^2 + n$. Thus for all m where round($\sqrt{m}$) is $n$, $m$ is closer to $n^2$ than to $(n+1)^2$.

If $ n+ \frac 12 < \sqrt{m} < n+1$ then $n^2 + n + \frac 14 < m < (n+1)^2 = n^2 + 2n + 1$. Since $m$ is an integer, $m \ge n^2 + n + 1$. Thus for all integers m where round($\sqrt{m}$) is $(n + 1)$, $m$ is closer to $(n + 1)^2$ than to $n^2$.

For non integers there is a range from $n^2 + n + \frac 14 < m < n^2 + n + \frac 12$ where the algorithm fails and returns the upper square even though the lower square is closer to m.

$\endgroup$
  • $\begingroup$ First off, tal can't be negative unless you want to deal with imaginary numbers. Second, there are no integer counterexamples to your son's algorithm, which you can verify by taking $$\bigg(\frac{2n+1/2\bigg)^2$$A non-integer counterexample is tal=12.3 $\endgroup$ – Don Thousand Nov 4 '18 at 20:33
  • $\begingroup$ "Given an arbitrary positive integer, find the nearest perfect square." and "His solution is obviously wrong if tal isn't restricted to the positive integers." BUt... tal is so you don't need to consider that. "When I saw the solution I immediately told him it was wrong." That was mean of you. Why did you do that? $\endgroup$ – fleablood Nov 4 '18 at 20:43
  • $\begingroup$ If $tal$ is negative there are no negative perfect squares so the nearest perfect square is $0$. So if the question had been worded to allow negative integers (which it wasn't) then an simple "if tal < 0 return 0" would "fix" your son's unbroken algorithm. $\endgroup$ – fleablood Nov 4 '18 at 20:57
  • $\begingroup$ @fleablood I wanted to give him a problem that he could solve using programming and I wanted to teach him that given an arbitrary positive real number t, (round(sqrt(t))^2 would not always result in the nearest perfect square. Then I restricted the domain to the positive integers, since they would be easier to parse when he wrote the program, not thinking it would change the result. That's also the reason I directly responded that the solution was wrong - I hadn't thought about the problem when restricting the domain to the positive integers. $\endgroup$ – E Persson Nov 4 '18 at 22:42
4
$\begingroup$

As for all positive integers $m$ there is an $n$ so that $n^2 \le m < (n+1)^2= n^2 + 2n + 1$.

If $n^2 \le m \le n^2 + n$ then the nearest square is $n^2$. If $n^2 + n < m < n^2 + 2n + 1$ then then nearest square is $(n+1)^2$.

Taking square roots. $n \le \sqrt{m} < n+1$. When we round:

this will give $n$ if $\sqrt{m} \le n+ \frac 12$ and will give $n+1$ if $\sqrt{m} > n + \frac 12$.

And if $n \le \sqrt{m} \le n+ \frac 12$ then $n^2 \le m \le n^2 + n + \frac 14$. And if $ n+ \frac 12 < \sqrt{m} < n+1$ then $n^2 + n + \frac 14 < m < (n+1) = n^2 + 2n + 1$.

As $m$ is an integer these give precisely the correct nearest perfect squares. (For non integers there is a range from $n^2 + n + \frac 14 < m < n^2 + n + \frac 12$ where this algorithm fails.)

SO your son's algorithm works perfectly. I'm a little perplexed as to why you thought it was wrong.

$\endgroup$
  • $\begingroup$ Thank you! I added your answer to my question above (and fixed some minor typos). $\endgroup$ – E Persson Nov 4 '18 at 23:35

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.