|
%I #74 Jul 03 2021 16:18:25
%S 1,1,2,5,41,2306,8143397,94592167328105,13345346031444632841427643906,
%T 258159204435047592104207508169153297050209383336364487461
%N a(n) = a(n-1)^2 + a(n-2)^4, a(0) = a(1) = 1.
%C a(n) and a(n+1) are relatively prime for n >= 0.
%C The number of independent sets on a complete binary tree with 2^(n-1)-1 nodes. - Jonathan S. Braunhut (jonbraunhut(AT)usa.net), May 04 2004. For example, when n=3, the complete binary tree with 2 levels has 2^2-1 nodes and has 5 independent sets so a(3)=5. The recursion for number of independent sets splits in two cases, with or without the root node being in the set.
%C a(10) has 113 digits and is too large to include.
%H Robert Israel, <a href="/A076725/b076725.txt">Table of n, a(n) for n = 0..13</a>
%H Karl Petersen, Ibrahim Salama, <a href="https://arxiv.org/abs/1712.02251">Tree shift complexity</a>, arXiv:1712.02251 [math.DS], 2017.
%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>
%F If b(n) = 1 + 1/b(n-1)^2, b(1)=1, then b(n) = a(n)/a(n-1)^2.
%F Lim_{n->inf} a(n)/a(n-1)^2 = A092526 (constant).
%F a(n) is asymptotic to c1^(2^n) * c2.
%F c1 = 1.2897512927198122075..., c2 = 1/A092526 = A263719 = (1/6)*(108 + 12*sqrt(93))^(1/3) - 2/(108 + 12*sqrt(93))^(1/3) = 0.682327803828019327369483739711... is the root of the equation c2*(1 + c2^2) = 1. - _Vaclav Kotesovec_, Dec 18 2014
%e a(2) = a(1)^2 + a(0)^4 = 1^2 + 1^4 = 2.
%e a(3) = a(2)^2 + a(1)^4 = 2^2 + 1^4 = 5.
%e a(4) = a(3)^2 + a(2)^4 = 5^2 + 2^4 = 41.
%e a(5) = a(4)^2 + a(3)^4 = 41^2 + 5^4 = 2306.
%e a(6) = a(5)^2 + a(4)^4 = 2306^2 + 41^4 = 8143397.
%e a(7) = a(6)^2 + a(5)^4 = 8143397^2 + 2306^4 = 94592167328105.
%p A[0]:= 1: A[1]:= 1:
%p for n from 2 to 10 do
%p A[n]:= A[n-1]^2 + A[n-2]^4;
%p od:
%p seq(A[i],i=0..10); # _Robert Israel_, Aug 21 2017
%t RecurrenceTable[{a[n] == a[n-1]^2 + a[n-2]^4, a[0] ==1, a[1] == 1}, a, {n, 0, 10}] (* _Vaclav Kotesovec_, Dec 18 2014 *)
%t NestList[{#[[2]],#[[1]]^4+#[[2]]^2}&,{1,1},10][[All,1]] (* _Harvey P. Dale_, Jul 03 2021 *)
%o (PARI) {a(n) = if( n<2, 1, a(n-1)^2 + a(n-2)^4)}
%o (PARI) {a=[0,0];for(n=1,99,iferr(a=[a[2],log(exp(a*[4,0;0,2])*[1,1]~)],E,return([n,exp(a[2]/2^n)])))} \\ To compute an approximation of the constant c1 = exp(lim_{n->oo} (log a(n))/2^n). \\ _M. F. Hasler_, May 21 2017
%o (PARI) a=vector(20); a[1]=1;a[2]=2; for(n=3, #a, a[n]=a[n-1]^2+a[n-2]^4); concat(1, a) \\ _Altug Alkan_, Apr 04 2018
%Y Cf. A000283, A005154, A112969, A114793.
%K nonn,nice
%O 0,3
%A _Michael Somos_, Oct 29 2002
%E Edited by _N. J. A. Sloane_ at the suggestion of _Andrew S. Plewe_, Jun 15 2007
| 