OFFSET
1,2
COMMENTS
Graham and Pollak give an elementary proof of the following result: For given m, define a(n) by a(1) = m and a(n+1) = floor(sqrt(2*a_n*(a_n + 1))), n >= 1. Then a(n) = tau_m(2^((n-1)/2) + 2^((n-2)/2)) where tau_m is the m-th smallest element of {1, 2, 3, ... } union { sqrt(2), 2*sqrt(2), 3*sqrt(2), ... }. For m=1 it follows as a curious corollary that a(2n+1) - 2*a(2n-1) is exactly the n-th bit in the binary expansion of sqrt(2) (A004539).
a(n) is also the curvature (rounded down) of the circle inscribed in the n-th 45-45-90 triangle arranged in a spiral as shown in the illustration in the links section. - Kival Ngaokrajang, Aug 21 2013
REFERENCES
R. L. Graham, D. E. Knuth and O. Pataschnic, Concrete Mathematics, Addison-Wesley, Reading (1994) 2nd Ed., Ex. 3.46.
Hwang, F. K., and Shen Lin. "An analysis of Ford and Johnson’s sorting algorithm." In Proc. Third Annual Princeton Conf. on Inform. Sci. and Systems, pp. 292-296. 1969.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Harvey P. Dale, Table of n, a(n) for n = 1..5000 (first 200 terms from T. D. Noe)
R. L. Graham and H. O. Pollak, Note on a nonlinear recurrence related to sqrt(2), Mathematics Magazine, Volume 43, Pages 143-145, 1970. Zbl 201.04705.
R. L. Graham and H. O. Pollak, Note on a nonlinear recurrence related to sqrt(2) (annotated and scanned copy)
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Kival Ngaokrajang, Illustration for some initial terms
S. Rabinowitz and P. Gilbert, A nonlinear recurrence yielding binary digits, Math. Mag. 64 (1991), no. 3, 168-171.
Th. Stoll, On Families of Nonlinear Recurrences Related to Digits, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.2.
FORMULA
a(n) = floor( sqrt(2)^(n-1) ) + floor( sqrt(2)^(n-2) ), n>1. - Ralf Stephan, Sep 18 2004
k * sqrt(2)^n - 2 < a(n) < k * sqrt(2)^n, where k = (1 + sqrt(2))/2 = A174968 = 1.2071.... Probably the first inequality can be improved (!). - Charles R Greathouse IV, Jan 23 2020
MAPLE
Digits:=200;
f:=proc(n) option remember;
if n=1 then 1 else floor(sqrt(2*f(n-1)*(f(n-1)+1))); fi; end;
[seq(f(n), n=1..200)];
MATHEMATICA
With[{c=Sqrt[2]}, Table[Floor[c^(n-1)+c^(n-2)], {n, 1, 50}]] (* Harvey P. Dale, May 11 2011 *)
NestList[Floor[Sqrt[2#(#+1)]]&, 1, 50] (* Harvey P. Dale, Aug 28 2013 *)
PROG
(Haskell)
a001521 n = a001521_list !! (n-1)
a001521_list = 1 : (map a000196 $ zipWith (*)
(map (* 2) a001521_list) (map (+ 1) a001521_list))
-- Reinhard Zumkeller, Dec 16 2013
(Magma) [Floor(Sqrt(2)^(n-1)+Sqrt(2)^(n-2)): n in [1..45]]; // Vincenzo Librandi, May 24 2015
(Sage) [floor(sqrt(2)^(n-1))+ floor(sqrt(2)^(n-2)) for n in (1..50)] # Bruno Berselli, May 25 2015
(PARI) a(n)=if(n>1, sqrtint(2^(n-1)) + sqrtint(2^(n-2)), 1) \\ Charles R Greathouse IV, Nov 27 2016
(PARI) first(n)=my(v=vector(n)); v[1]=1; for(k=2, n, v[k]=sqrtint(2*(v[k-1]+1)*v[k-1])); v \\ Charles R Greathouse IV, Jan 23 2020
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Additional comments from Torsten Sillke, Apr 06 2001
STATUS
approved