cp's OEIS Frontend

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

%I A001521 M0569 N0206 #98 Apr 20 2025 03:46:08
%S A001521 1,2,3,4,6,9,13,19,27,38,54,77,109,154,218,309,437,618,874,1236,1748,
%T A001521 2472,3496,4944,6992,9888,13984,19777,27969,39554,55938,79108,111876,
%U A001521 158217,223753,316435,447507,632871,895015,1265743,1790031,2531486,3580062,5062972
%N A001521 a(1) = 1; thereafter a(n+1) = floor(sqrt(2*a(n)*(a(n)+1))).
%C A001521 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).
%C A001521 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
%D A001521 R. L. Graham, D. E. Knuth and O. Pataschnic, Concrete Mathematics, Addison-Wesley, Reading (1994) 2nd Ed., Ex. 3.46.
%D A001521 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.
%D A001521 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001521 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001521 Harvey P. Dale, <a href="/A001521/b001521.txt">Table of n, a(n) for n = 1..5000</a> (first 200 terms from T. D. Noe)
%H A001521 R. L. Graham and H. O. Pollak, <a href="http://www.jstor.org/stable/2688390">Note on a nonlinear recurrence related to sqrt(2)</a>, Mathematics Magazine, Volume 43, Pages 143-145, 1970. Zbl 201.04705.
%H A001521 R. L. Graham and H. O. Pollak, <a href="/A001521/a001521_2.pdf">Note on a nonlinear recurrence related to sqrt(2)</a> (annotated and scanned copy)
%H A001521 R. K. Guy, <a href="http://www.jstor.org/stable/2322249">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
%H A001521 R. K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
%H A001521 Kival Ngaokrajang, <a href="/A001521/a001521_1.pdf">Illustration for some initial terms</a>
%H A001521 S. Rabinowitz and P. Gilbert, <a href="http://www.jstor.org/stable/2691296">A nonlinear recurrence yielding binary digits</a>, Math. Mag. 64 (1991), no. 3, 168-171.
%H A001521 Th. Stoll, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Stoll/stoll56.html">On Families of Nonlinear Recurrences Related to Digits</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.2.
%F A001521 a(n) = floor( sqrt(2)^(n-1) ) + floor( sqrt(2)^(n-2) ), n>1. - _Ralf Stephan_, Sep 18 2004
%F A001521 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
%p A001521 Digits:=200;
%p A001521 f:=proc(n) option remember;
%p A001521 if n=1 then 1 else floor(sqrt(2*f(n-1)*(f(n-1)+1))); fi; end;
%p A001521 [seq(f(n),n=1..200)];
%t A001521 With[{c=Sqrt[2]},Table[Floor[c^(n-1)+c^(n-2)],{n,1,50}]] (* _Harvey P. Dale_, May 11 2011 *)
%t A001521 NestList[Floor[Sqrt[2#(#+1)]]&,1,50] (* _Harvey P. Dale_, Aug 28 2013 *)
%o A001521 (Haskell)
%o A001521 a001521 n = a001521_list !! (n-1)
%o A001521 a001521_list = 1 : (map a000196 $ zipWith (*)
%o A001521                     (map (* 2) a001521_list) (map (+ 1) a001521_list))
%o A001521 -- _Reinhard Zumkeller_, Dec 16 2013
%o A001521 (Magma) [Floor(Sqrt(2)^(n-1)+Sqrt(2)^(n-2)): n in [1..45]]; // _Vincenzo Librandi_, May 24 2015
%o A001521 (Sage) [floor(sqrt(2)^(n-1))+ floor(sqrt(2)^(n-2)) for n in (1..50)] # _Bruno Berselli_, May 25 2015
%o A001521 (PARI) a(n)=if(n>1, sqrtint(2^(n-1)) + sqrtint(2^(n-2)), 1) \\ _Charles R Greathouse IV_, Nov 27 2016
%o A001521 (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
%Y A001521 Cf. A000196.
%Y A001521 First, second, and third differences give A017911, A190660, A241576.
%K A001521 nonn,nice,easy
%O A001521 1,2
%A A001521 _N. J. A. Sloane_
%E A001521 Additional comments from Torsten Sillke, Apr 06 2001