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

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

Offset

1,2

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

References

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

Links

Table of n, a(n) for n=1..60.

The MacTutor History of Mathematics archive, Sulbasutras.

Wikipedia, Shulba Sutras.

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.

Example

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

Crossrefs

Cf. A256098, A048760, A000196, A002193.

Sequence in context: A011319 A177460 A091015 * A058147 A193344 A119954

Adjacent sequences: A256094 A256095 A256096 * A256098 A256099 A256100

Keyword

nonn,frac,easy

Author

Wolfdieter Lang, Mar 24 2015

Status

approved