A227615 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.

3, 4, 8, 16, 31, 61, 122, 244, 487, 973, 1946, 3892, 7783, 15565, 31130, 62259, 124517, 249033, 498066, 996131, 1992262, 3984524, 7969047, 15938093, 31876185, 63752369, 127504737, 255009473, 510018945, 1020037890, 2040075780

Offset: 0

Author

Olivier de Mouzon, Jul 17 2013

Keywords

• nonn
• base

Comments

a(0)=3, a(1)=4 and for n>=1, a(n+1) is 2*a(n) or 2*a(n)-1.

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.

Yet, for n>=1, we have a lower bound: a(n) >= 2^n and an upper bound: a(n) <= 2^(n+1).

Examples

			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).
		

Crossrefs

Cf. A003010, A070939, A227608.

Programs

PARI

lista(nn) = {a = 4; print1(#binary(a), ", "); for (n=1, nn, a = a^2-2; print1(#binary(a), ", "););} \\ Michel Marcus, Apr 04 2016

Formula

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.

a(n) = A070939(A003010(n)). - Michel Marcus, Apr 04 2016

Extensions

Terms from a(19) on from Michel Marcus, Apr 04 2016