OFFSET
0,1
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).
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.
EXAMPLE
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).
PROG
(PARI) lista(nn) = {a = 4; print1(#binary(a), ", "); for (n=1, nn, a = a^2-2; print1(#binary(a), ", "); ); } \\ Michel Marcus, Apr 04 2016
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Olivier de Mouzon, Jul 17 2013
EXTENSIONS
Terms from a(19) on from Michel Marcus, Apr 04 2016
STATUS
approved