|
%I #18 Jun 27 2021 04:42:16
%S 3,4,8,16,31,61,122,244,487,973,1946,3892,7783,15565,31130,62259,
%T 124517,249033,498066,996131,1992262,3984524,7969047,15938093,
%U 31876185,63752369,127504737,255009473,510018945,1020037890,2040075780
%N Number of bits necessary to represent u(n) in binary, where u is the Lucas-Lehmer sequence: u(0) = 100 (in binary); for n>0, u(n) = u(n-1)^2 - 2.
%C a(0)=3, a(1)=4 and for n>=1, a(n+1) is 2*a(n) or 2*a(n)-1.
%C It seems the rule to decide between the 2 is not straightforward. So you actually need to compute u(n) to have its required number of bits.
%C Yet, for n>=1, we have a lower bound: a(n) >= 2^n and an upper bound: a(n) <= 2^(n+1).
%F a(n) = E(log_2(u(n))) + 1, where E(x) is the integer part of x and u is defined by: u(0) = 4 (or 100 in binary) and for n>0, u(n) = u(n-1)^2 - 2.
%F a(n) = A070939(A003010(n)). - _Michel Marcus_, Apr 04 2016
%e For n=2, u(2) = 194, log_2(u(2)) is between 7.5 and 7.6, so E(log_2(u(2))) = 7, so a(2) = E(log_2(u(2))) + 1 = 8. And indeed, u(2) = 194 (in base 10) = 11000010 in base 2 requires 8 bits (all bits above are 0).
%o (PARI) lista(nn) = {a = 4; print1(#binary(a), ", "); for (n=1, nn, a = a^2-2; print1(#binary(a), ", "););} \\ _Michel Marcus_, Apr 04 2016
%Y Cf. A003010, A070939, A227608.
%K nonn,base
%O 0,1
%A _Olivier de Mouzon_, Jul 17 2013
%E Terms from a(19) on from _Michel Marcus_, Apr 04 2016
|
