login
Sequence defined by a(1)=a(2)=1 and a(n) = gray(a(n-1) + a(n-2)), with gray(m) = A003188(m).
3

%I #18 Jan 16 2016 18:01:31

%S 1,1,3,6,13,26,52,105,211,418,847,1673,3380,6755,13404,27104,53538,

%T 108163,216183,428935,867329,1713228,3461227,6917868,13725948,

%U 27754524,54823316,110759272,221371778,439230367,888144817,1754346232,3544296957,7083888783

%N Sequence defined by a(1)=a(2)=1 and a(n) = gray(a(n-1) + a(n-2)), with gray(m) = A003188(m).

%C This recurrence is reminiscent of Fibonacci's, except that the result of each step is passed through the binary-reflected Gray code mapping, which introduces a degree of pseudo-randomness.

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

%H Stanislav Sykora, <a href="/A265385/b265385.txt">Table of n, a(n) for n = 1..1000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci number</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Gray_code">Gray code</a>

%e r(10) = 2.000421531046..., r(1000) = 1.999999999903...

%e s(100) = 1.9841292..., s(101) = 2.0220518..., s(102) = 1.9752921...

%e s(10000) = 1.9841299..., s(10001) = 2.0220478..., s(10002) = 1.9752929...

%o (PARI) gray(m)=bitxor(m,m>>1);

%o a=vector(1000);a[1]=1;a[2]=1;for(n=3,#a,a[n]=gray(a[n-1]+a[n-2]));a

%Y Cf. A000045, A003188, A265386, A265387.

%K nonn

%O 1,3

%A _Stanislav Sykora_, Dec 07 2015