A001521 a(1) = 1; thereafter a(n+1) = floor(sqrt(2*a(n)*(a(n)+1))).

1, 2, 3, 4, 6, 9, 13, 19, 27, 38, 54, 77, 109, 154, 218, 309, 437, 618, 874, 1236, 1748, 2472, 3496, 4944, 6992, 9888, 13984, 19777, 27969, 39554, 55938, 79108, 111876, 158217, 223753, 316435, 447507, 632871, 895015, 1265743, 1790031, 2531486, 3580062, 5062972

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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.
• F. K. Hwang, 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.

Crossrefs

Cf. A000196.

First, second, and third differences give A017911, A190660, A241576.

Programs

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

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

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

Sage

[floor(sqrt(2)^(n-1))+ floor(sqrt(2)^(n-2)) for n in (1..50)] # Bruno Berselli, May 25 2015

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

Extensions

Additional comments from Torsten Sillke, Apr 06 2001