1

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'$?)

James Faulcon
  • 263
  • 8
    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}$$

     –  Mar 04 '14 at 21:24
  • @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$? – James Faulcon Mar 04 '14 at 21:32
  • 1
    @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. – Steven Stadnicki Mar 04 '14 at 22:28
  • @StevenStadnicki: Oh, I agree! If you have two squares then it's all gravy. – James Faulcon Mar 04 '14 at 22:33

3 Answers3

3

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.

Jack M
  • 27,819
  • 7
  • 63
  • 129
1

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

Amemiya Fuyuki
  • 11
1

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$

Neil W
  • 2,495
  • 1
  • 13
  • 16