1
$\begingroup$

Given a square number $s = n^2$, is there a way to find the next square $s'$ without knowing $n$? (That is, if you can't take the square root of $s$ to determine $n$, can you compute $s'$?)

$\endgroup$
  • 8
    $\begingroup$ Note that $$s' - s = (n + 1)^2 - n^2 = 2n + 1$$ So knowing the next square is really equivalent to knowing what $n$ is, since $$n = \frac{s' - s - 1}{2}$$ $\endgroup$ – user61527 Mar 4 '14 at 21:24
  • $\begingroup$ @T.Bongers Right, once you know the next square (or rather any two adjacent squares), you can compute the rest. I'm asking whether, if you only know one square, can you compute another without taking the square root to deduce $n$? $\endgroup$ – James Faulcon Mar 4 '14 at 21:32
  • 1
    $\begingroup$ @JamesFaulcon T.Bongers' point is that if you know one square and you compute the next, then you have computed the square root and deduced $n$! That is to say, an algorithm for finding the next square is exactly equivalent (nitpick: plus some constant number of operations) to an algorithm for finding the square root. $\endgroup$ – Steven Stadnicki Mar 4 '14 at 22:28
  • $\begingroup$ @StevenStadnicki: Oh, I agree! If you have two squares then it's all gravy. $\endgroup$ – James Faulcon Mar 4 '14 at 22:33
3
$\begingroup$

Well, there's at least no real rational function that does what you want.

Suppose $f(n^2)=(n+1)^2=n^2+2n+1$ for all $n\in\mathbb N$ (or even just for an infinite number of $n$). Then $\frac{f(n^2)-n^2-1}{2}=n$, so the rational function $\frac{f(x)-x-1}{2}$ intersects $\sqrt x$ an infinite number of times, which is impossible, since rational functions are asymptotically equivalent to polynomials, and $\sqrt x$ is either infinitesimal to any particular polynomial or the other way around (iff the polynomial is constant).

So if it's possible at all, it's going to take more than just multiplying, adding and dividing.

$\endgroup$
  • 2
    $\begingroup$ Very convincing argument! Sounds like you always need at least two squares to figure it out. $\endgroup$ – James Faulcon Mar 4 '14 at 22:38
1
$\begingroup$

I assume that all you wanted was not taking any square roots- we could actually determine n without doing that.

Suppose $s=n^2$, then write $s-1=n^2-1=(n+1)(n-1)$. Given any such factorisation (ie. $s-1=(m-1)(m+1)$ for some m), we must have m = n as we require $m^2-1=s-1=n^2-1$. Hence the n obtained in the factorisation is unique, and we are done.

eg. Given $s=49$, write $s-1=48=8*6$ and your $n$ must be $7$.

$\endgroup$
  • $\begingroup$ If you're allowed to factor (and then look through the divisors for a pair of the form $n+1$, $n-1$) why not just factor $s$ and look for two equal divisors? $\endgroup$ – Jack M Mar 4 '14 at 21:53
  • $\begingroup$ Yeah don't know why but that actually slipped my mind. Thanks for pointing that out! $\endgroup$ – Amemiya Fuyuki Mar 4 '14 at 22:03
  • $\begingroup$ @JackM, computing square roots is easier than factoring... $\endgroup$ – vonbrand Mar 4 '14 at 23:58
1
$\begingroup$

A semi-answer perhaps.

$(n+1)^2 = (e^{\frac{ln(n^2)}{2}}+1)^2$

Technically I did not take a square root, however I did implicitly compute $n$ by using the term $e^{\frac{ln(n^2)}{2}}$


Addendum: You can avoid ever computing $n$ by using the function$f(x) = (e^{\frac{3}{2}ln(x)}+x)^2/x^2$

$f(n^2) = (e^{\frac{3}{2}ln(n^2)}+n^2)^2/(n^2)^2= (n+1)^2$

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