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

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,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 number of the circle curvature (rounded down) inscribing in 45-45-90 triangle arranged as spiral form. See illustration in links. - 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

Cf. A000196.

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

Sequence in context: A017824 A343942 A094054 * A003143 A221718 A251571

Adjacent sequences: A001518 A001519 A001520 * A001522 A001523 A001524

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

Additional comments from Torsten Sillke, Apr 06 2001

Status

approved