%I #25 Mar 10 2023 08:26:56

%S 0,1,3,2,4,5,4,3,5,6,7,6,5,6,5,4,6,7,8,7,8,9,8,7,6,7,8,7,6,7,6,5,7,8,

%T 9,8,9,10,9,8,9,10,11,10,9,10,9,8,7,8,9,8,9,10,9,8,7,8,9,8,7,8,7,6,8,

%U 9,10,9,10,11,10,9,10,11,12,11,10,11,10,9,10,11,12,11,12,13,12,11,10,11,12

%N a(0) = 0, a(1) = 1; thereafter, a(2n) = a(n) + 1 + (n mod 2), a(2n+1) = a(n) + 2 - (n mod 2).

%C Let S be a set containing 0 and let S grow in generations G(i), defined by these rules: If x is in S then 2x is in S and 1 - x is in S. So G(0) = 0, G(1) = {1}, G(2) = {2}, G(3) = {-1,4}, ... Then a(n) is the generation containing the integer k where n = 2k - 1 for k>0 and -2k for k <= 0. The question posed by Clark Kimberling was "Does each generation contain a Fibonacci number or its negative?" It has been proved that every integer occurs in some G(i). - _Karyn McLellan_, Aug 16 2018

%D C. Kimberling, Problem proposals, Proceedings of the Sixteenth International Conference on Fibonacci Numbers and Their Applications, P. Anderson, C. Ballot and W. Webb, eds. The Fibonacci Quarterly, 52.5(2014), 5-14.

%H Chai Wah Wu, <a href="/A286298/b286298.txt">Table of n, a(n) for n = 0..10000</a>

%H Danielle Cox and K. McLellan, <a href="https://www.fq.math.ca/Papers1/55-2/CoxMcLellan021717.pdf">A problem on generation sets containing Fibonacci numbers</a>, Fib. Quart., 55 (No. 2, 2017), 105-113.

%F a(n) = A005811(n) + A000523(n) for n >= 1. - _Karyn McLellan_, Aug 16 2018

%e For k = -5, n = 10 and f(10) = 7, so -5 first appears in G(7). - _Karyn McLellan_, Aug 16 20 18

%p f:=proc(n) option remember;

%p if n <= 1 then n

%p elif (n mod 2) = 0 then f(n/2)+1+((n/2) mod 2);

%p else f((n-1)/2) + 2 - ((n-1)/2 mod 2); end if;

%p end proc;

%p [seq(f(n),n=0..120)];

%o (Python)

%o def A286298(n):

%o if n <= 1:

%o return n

%o a, b = divmod(n, 2)

%o return A286298(a) + 1 + b + (-1)**b*(a % 2) # _Chai Wah Wu_, Jun 02 2017

%o (PARI) a(n) = if (n==0, 0, logint(n, 2) + hammingweight(bitxor(n, n>>1))); \\ _Michel Marcus_, Aug 21 2018

%Y Cf. A000523, A005811, A286299 (first differences).

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, Jun 02 2017