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

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

Author

Stanislav Sykora, Dec 07 2015

Keywords

• nonn

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

Examples

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

Links

• Stanislav Sykora, Table of n, a(n) for n = 1..1000
• Wikipedia, Fibonacci number
• Wikipedia, Gray code

Crossrefs

Cf. A000045, A003188, A265385, A265386.

Programs

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.