login
A265387
Sequence defined by a(1)=a(2)=1 and a(n) = gray(a(n-1)) + gray(a(n-2)), with gray(m) = A003188(m).
3
1, 1, 2, 4, 9, 19, 39, 78, 157, 316, 629, 1265, 2520, 5053, 10135, 20159, 40508, 80642, 161701, 324346, 645118, 1296264, 2580557, 5174455, 10379095, 20643816, 41480472, 82577840, 165582588, 332131050, 660602145, 1327375184, 2642491049, 5298643189
OFFSET
1,3
COMMENTS
This recurrence is reminiscent of Fibonacci's, except that in each step the arguments are passed through the binary-reflected Gray code mapping, which introduces a degree of pseudo-randomness.
Conjecture: The mean growth rate r(n) = (a(2n)/a(n))^(1/n) appears to converge exactly to 2, with the consecutive-terms ratio s(n) = a(n)/a(n-1) exhibiting relatively small (~1%) but persistent fluctuations around the mean value. This contrasts what one might first expect, that sequence's growth rate were similar to that of the Fibonacci sequence, i.e., the golden ratio, since gray(m) just permutes every block of numbers ranging from 2^k to 2^l-1, for any 0<k<l.
LINKS
Wikipedia, Fibonacci number
Wikipedia, Gray code
EXAMPLE
r(10) = 2.000470476732..., r(1000) = 2.000000000203...
s(100) = 2.0058315..., s(101) = 1.9889791..., s(102) = 2.0093437...
s(10000) = 2.0058331..., s(10001) = 1.9889803..., s(10002) = 2.0093413...
PROG
(PARI) gray(m)=bitxor(m, m>>1);
a=vector(1000); a[1]=1; a[2]=1; for(n=3, #a, a[n]=gray(a[n-1])+gray(a[n-2])); a
CROSSREFS
KEYWORD
nonn
AUTHOR
Stanislav Sykora, Dec 07 2015
STATUS
approved