1
$\begingroup$

I found that the square root of any prime number S can be approximated, at the n-th order, as a rational number represented by the polynomials shown below. $x_0$ is an initial seed, which is a rational number chosen “close” to $\sqrt S$. I used the iterative method, not the continued fractions

enter image description here

My question: Is someone aware of this result? Is it already known and has been published elsewhere? If affirmative, please post the reference!

$\endgroup$
5
  • 6
    $\begingroup$ Someone might already be aware of the result if there was a natural way how this result would come up, or if the result somehow had "practical" significance. Maybe it would help to add some context why the given formula is special or useful, and how you derived it. $\endgroup$
    – TMM
    May 5 at 16:13
  • 7
    $\begingroup$ Surely this works for any number $S$, not just prime numbers? Could it be a version of Newton's method? $\endgroup$
    – Will Sawin
    May 5 at 18:28
  • 1
    $\begingroup$ If you call $F_n(t) = (x_0+t \sqrt{S}) ^n$, it seems like both the numerator and the denominator can be expressed in terms of $F_n $ and its antiderivative in $\pm 1$. Is this the way you found the formula? $\endgroup$ May 5 at 21:01
  • $\begingroup$ @Andrea, what does "its antiderivative in $\pm1$" mean? $\endgroup$ May 5 at 23:53
  • $\begingroup$ For antiderivative I mean $G_n(t)=\frac{(x_0+t\sqrt{S}) ^{n+1}}{\sqrt{S}(n+1)}$. This has the property that $G_n'(t) =F_n(t) $. It seems like you can express the numerator as something like $F_{2^n}(1) +F_{2^n}(-1) $ and the denominator as $G_{2^n}(1) +G_{2^n}(-1) $. $\endgroup$ May 6 at 9:06

1 Answer 1

6
$\begingroup$

My impression is that you have developed $(x_0-\sqrt{S})^{2^n}$ with Newton binomial formula, separated the terms with even index from the terms with odd index to get an expression of the form $A_n-\sqrt{S}B_n$ to approach $\sqrt{S}$ by $A_n/B_n$.

More precisely, you have $$A_n = \frac{(x_0+\sqrt{S})^{2^n}+ (x_0-\sqrt{S})^{2^n}}{2}$$ and $$B_n = \frac{(x_0+\sqrt{S})^{2^n}-(x_0-\sqrt{S})^{2^n}}{2\sqrt{S}}.$$

The successive approximations you get are the same as approximations provided by Newton method applied to the function $f : x \mapsto x^2-s$. Indeed, $A_0/B_0=x_0$ and for every $n \ge 0$, $$\frac{A_n}{B_n} - \frac{f(A_n/B_n)}{f'(A_n/B_n)} = \frac{A_n}{B_n} - \frac{A_n^2/B_n^2 - s}{2A_n/B_n} = \frac{A_n^2+sB_n^2}{2A_nB_n} = \frac{A_{n+1}}{B_{n+1}},$$ since $4(A_n^2+sB_n^2) = 2A_{n+1}$ and $4A_nB_n = 2B_{n+1}$.

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