2
$\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!

Improve this question
$\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
    Commented May 5, 2022 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
    Commented May 5, 2022 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$
    – Andrea Marino
    Commented May 5, 2022 at 21:01
  • $\begingroup$ @Andrea, what does "its antiderivative in $\pm1$" mean? $\endgroup$
    – Gerry Myerson
    Commented May 5, 2022 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$
    – Andrea Marino
    Commented May 6, 2022 at 9:06

1 Answer 1

Reset to default
7
$\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}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .