cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-1 of 1 results.

A256097 Numerators of a rational guess r(n) for the input for Newton's algorithm to find sqrt(n).

Original entry on oeis.org

1, 3, 2, 2, 9, 5, 11, 3, 3, 19, 10, 7, 11, 23, 4, 4, 33, 17, 35, 9, 37, 19, 39, 5, 5, 51, 26, 53, 27, 11, 28, 57, 29, 59, 6, 6, 73, 37, 25, 19, 77, 13, 79, 20, 27, 41, 83, 7, 7, 99, 50, 101, 51, 103, 52, 15, 53, 107, 54, 109, 55, 111, 8, 8, 129, 65, 131, 33, 133, 67
Offset: 1

Views

Author

Wolfdieter Lang, Mar 24 2015

Keywords

Comments

The corresponding denominators are given in A256098.
This educated guess for the rational input R(n) = x(n;k=0) for the so-called Babylonian (also called Heron's) iteration to find sqrt(n) (Newton's method for sqrt(n)), x(n; k+1) = (x(n; k) + n/x(n; k))/2, k >= 0, was used in Vedic Mathematics (see the H.-W. Alhen et al. reference, pp. 145-146, and the MacTutor link on Sulbasutras). In the Wikipedia link on Shulba Sutras another suggestion is given how the approximation 1 + 1/3 + 1/(3*4) - 1/(3*4*34) for sqrt(2) was obtained in Sulbasutras. The explanation given in the H.-W. Alten et al. reference seems to me more convincing.
This R(n) is obtained by n = s(n)^2 + r(n) with s(n)^2 = A048760(n) (largest square not exceeding n) and the remainder r(n). Then the approximation of the square root is used sqrt(n) = sqrt(s(n)^2 + r(n)) approximately s(n)*(1 + r(n)/(2*s(n)^2)) = s(n) + r(n)/(2*s(n)). Note that A048760(n) = A000196(n)^2, that is, s(n) = floor(sqrt(n)).

Examples

			n = 2: s(n) = floor(sqrt(2)) = sqrt(A048760(2)) = 1, r(n) = 2 - 1^2 = 1. R(2) = s(2) + r(2)/(2*s(2)) = 1 + 1/(2*1) = 3/2. That is a(2) = 3 and A256098(2) = 2.
n = 17: s(n) = floor(sqrt(17)) = sqrt(A048760(17)) = 4 , r(n) = 17 - 4^2 = 1. R(17) = s(17) + r(17)/(2*s(17)) = 4 + 1/(2*4) = 33/8. That is, a(n) = 33 and A256098(17) = 8.
The rationals R(n) for n = 1..60 are: [1, 3/2, 2, 2, 9/4, 5/2, 11/4, 3, 3, 19/6, 10/3, 7/2, 11/3, 23/6, 4, 4, 33/8, 17/4, 35/8, 9/2, 37/8, 19/4, 39/8, 5, 5, 51/10, 26/5, 53/10, 27/5, 11/2, 28/5, 57/10, 29/5, 59/10, 6, 6, 73/12, 37/6, 25/4, 19/3, 77/12, 13/2, 79/12, 20/3, 27/4, 41/6, 83/12, 7, 7, 99/14, 50/7, 101/14, 51/7, 103/14, 52/7, 15/2, 53/7, 107/14, 54/7, 109/14,...]
For n=2 the Newton (Babylonian also called Heron) iteration produces. with x(2; k=0) = R(2) = 3/2: x(2; 1) = (3/2 + 4/3)/2 = 17/12 = 1 + 5/2  = 1 + 1/3 + 1/(3*4).
  x(2; 2) = (17/12 + 24/17)/2 = 577/408 = 17/12 + (577/408 - 17*34/408)  = 17/12 - 1/408 = 1 + 1/3 + 1/(3*4) - 1/(3*4*34) = 1.4142156... versus sqrt(2) = 1.4142135... (see A002193).

References

  • H.-W. Alten et al., 4000 Jahre Algebra, 2. Auflage, Springer, 2014, p. 145-146.

Links

Crossrefs

Cf. A000196, A002193, A048760, A048761, A256098.

Programs

Formula

a(n) = numerator(R(n)) with the rational (in lowest terms) R(n) = f(n) + (n - f(n)^2)/(2*f(n)) = (f(n) + n/f(n))/2 with f(n) := floor(sqrt(n)) = A000196(n), for n >= 1. See the comment above for this formula.

Extensions

a(61)-a(70) from Stefano Spezia, Feb 15 2025
Showing 1-1 of 1 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.