cp's OEIS Frontend

A003686 Number of genealogical 1-2 rooted trees of height n.

%I A003686 #65 Sep 06 2023 21:23:06
%S A003686 1,2,3,5,11,41,371,13901,5033531,69782910161,351229174914190691,
%T A003686 24509789089655802510792656021,
%U A003686 8608552999157278575508415639286249242844899051
%N A003686 Number of genealogical 1-2 rooted trees of height n.
%C A003686 Let u(n), v(n) be defined by u(1) = v(1) = 1, u(n+1) = u(n) + v(n) and v(n+1) = u(n)*v(n) for n >= 1; then a(n) = u(n) and A064847(n) = v(n). - _Benoit Cloitre_, Apr 01 2002 [Edited by _Petros Hadjicostas_, May 11 2020]
%C A003686 Consider the mapping f(a/b) = (a + b)/(a*b). Taking a = 1 and b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the following sequence 1/1, 2/1, 3/2, 5/6, 11/30, ... The current sequence contains the numerators. - _Amarnath Murthy_, Mar 24 2003
%C A003686 An infinite coprime sequence defined by recursion. - _Michael Somos_, Mar 19 2004
%D A003686 D. Parisse, The Tower of Hanoi and the Stern-Brocot Array, Thesis, Munich, 1997.
%H A003686 Franklin T. Adams-Watters, <a href="/A003686/b003686.txt">Table of n, a(n) for n = 1..19</a>
%H A003686 <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%H A003686 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A003686 Limit_{n -> infinity} a(n)^phi/A064847(n) = 1, where phi = (1 + sqrt(5))/2 is the golden ratio. - _Benoit Cloitre_, May 08 2002
%F A003686 Numerator of b(n), where b(n) = 1/numerator(b(n-1)) + 1/denominator(b(n-1)) for n >= 2 with b(1) = 1.
%F A003686 a(n+1) = a(n) + a(1)*a(2)*...*a(n-1) for n >= 2. Also a(n+1) = a(n) + a(n-1)*(a(n) - a(n-1)) for n >= 2. In both cases, we start with a(1) = 1 and a(2) = 2.
%F A003686 a(n) ~ c^(phi^n), where c = 1.22508584062304325811405322247537613534139348463831009881946422737141574647... and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - _Vaclav Kotesovec_, May 21 2015
%t A003686 RecurrenceTable[{a[1]==1, a[2]==2, a[n]==a[n-1]+a[n-2](a[n-1]-a[n-2])}, a[n],{n,15}] (* _Harvey P. Dale_, Jul 27 2011 *)
%t A003686 Re[NestList[Re@#+(1+I Re@#)Im@#&, 1+I, 15]] (* _Vladimir Reshetnikov_, Jul 18 2016 *)
%o A003686 (PARI) a(n) = local(an); if(n<1, 0, an=vector(max(2,n)); an[1]=1; an[2]=2; for(k=3, n, an[k]=an[k-1] - an[k-2]^2 + an[k-1]*an[k-2]); an[n])
%o A003686 (Magma) I:=[1,2]; [n le 2 select I[n] else Self(n-1)+Self(n-2)*(Self(n-1)-Self(n-2)): n in [1..14]]; // _Vincenzo Librandi_, Jul 19 2016
%Y A003686 Cf. A001622, A001685, A064526, A064847, A070231, A070233, A070234, A094303.
%K A003686 nonn,easy,nice
%O A003686 1,2
%A A003686 _Vsevolod F. Lev_, c. 1998
%E A003686 Additional description from _Andreas M. Hinz_ and _Daniele Parisse_