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

%I M0569 N0206 #95 May 18 2024 14:57:41

%S 1,2,3,4,6,9,13,19,27,38,54,77,109,154,218,309,437,618,874,1236,1748,

%T 2472,3496,4944,6992,9888,13984,19777,27969,39554,55938,79108,111876,

%U 158217,223753,316435,447507,632871,895015,1265743,1790031,2531486,3580062,5062972

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

%C 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 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 R. L. Graham, D. E. Knuth and O. Pataschnic, Concrete Mathematics, Addison-Wesley, Reading (1994) 2nd Ed., Ex. 3.46.

%D 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.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 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 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 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 Kival Ngaokrajang, <a href="/A001521/a001521_1.pdf">Illustration for some initial terms</a>

%H 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 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 a(n) = floor( sqrt(2)^(n-1) ) + floor( sqrt(2)^(n-2) ), n>1. - _Ralf Stephan_, Sep 18 2004

%F 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 Digits:=200;

%p f:=proc(n) option remember;

%p if n=1 then 1 else floor(sqrt(2*f(n-1)*(f(n-1)+1))); fi; end;

%p [seq(f(n),n=1..200)];

%t With[{c=Sqrt[2]},Table[Floor[c^(n-1)+c^(n-2)],{n,1,50}]] (* _Harvey P. Dale_, May 11 2011 *)

%t NestList[Floor[Sqrt[2#(#+1)]]&,1,50] (* _Harvey P. Dale_, Aug 28 2013 *)

%o (Haskell)

%o a001521 n = a001521_list !! (n-1)

%o a001521_list = 1 : (map a000196 $ zipWith (*)

%o (map (* 2) a001521_list) (map (+ 1) a001521_list))

%o -- _Reinhard Zumkeller_, Dec 16 2013

%o (Magma) [Floor(Sqrt(2)^(n-1)+Sqrt(2)^(n-2)): n in [1..45]]; // _Vincenzo Librandi_, May 24 2015

%o (Sage) [floor(sqrt(2)^(n-1))+ floor(sqrt(2)^(n-2)) for n in (1..50)] # _Bruno Berselli_, May 25 2015

%o (PARI) a(n)=if(n>1, sqrtint(2^(n-1)) + sqrtint(2^(n-2)), 1) \\ _Charles R Greathouse IV_, Nov 27 2016

%o (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 Cf. A000196.

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

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_

%E Additional comments from Torsten Sillke, Apr 06 2001