A265385 Sequence defined by a(1)=a(2)=1 and a(n) = gray(a(n-1) + a(n-2)), with gray(m) = A003188(m).
1, 1, 3, 6, 13, 26, 52, 105, 211, 418, 847, 1673, 3380, 6755, 13404, 27104, 53538, 108163, 216183, 428935, 867329, 1713228, 3461227, 6917868, 13725948, 27754524, 54823316, 110759272, 221371778, 439230367, 888144817, 1754346232, 3544296957, 7083888783
Offset: 1
Keywords
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
Keywords
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
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
Comments
Examples
Links
Crossrefs
Programs
PARI