A227608 -id:A227608 - cp's OEIS frontend

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

Olivier de Mouzon, Jul 17 2013

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

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

Cf. A003010, A070939, A227608.

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

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

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

A227616 Number of bits set to 1 in the binary representation of the n-th term of the Lucas-Lehmer sequence (A003010).

Original entry on oeis.org

1, 3, 3, 5, 12, 30, 58, 128, 237, 476, 975, 1956, 3899, 7798, 15534, 31270, 62262, 124635, 248944, 497797, 995730, 1990576, 3983767, 7969049, 15935289, 31870309, 63739461, 127519282, 254994762, 510016513, 1020092276, 2040066241, 4080236749

Offset: 0

Olivier de Mouzon, Jul 17 2013

			For n = 2, A003010(2) = 11000010 (in binary), so a(2) = 3.

Cf. A003010, A227608, A227615.

read("transforms") :
A227616 := proc(n)
    wt(A003010(n)) ;
end proc: # R. J. Mathar, Jul 20 2013

First@ DigitCount[#, 2] & /@ NestList[#^2 - 2 &, 4, 28] (* Michael De Vlieger, Apr 04 2016 *)

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

a(n) = A000120(A003010(n)).

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions