login
Compressed fibbinary numbers (A003714), with rewrite 0->0, 01->1 applied to their binary expansion.
27

%I #36 Mar 18 2024 10:06:40

%S 0,1,2,4,3,8,5,6,16,9,10,12,7,32,17,18,20,11,24,13,14,64,33,34,36,19,

%T 40,21,22,48,25,26,28,15,128,65,66,68,35,72,37,38,80,41,42,44,23,96,

%U 49,50,52,27,56,29,30,256,129,130,132,67,136,69,70,144,73,74,76,39,160,81

%N Compressed fibbinary numbers (A003714), with rewrite 0->0, 01->1 applied to their binary expansion.

%C Permutation of the nonnegative integers (A001477); inverse permutation of A048680 i.e. A048679[ A048680[ n ] ] = n for all n.

%H Antti Karttunen, <a href="/A048679/b048679.txt">Table of n, a(n) for n = 0..10945</a> (terms 0..10000 from Alois P. Heinz)

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(n) = A106151(2*A003714(n)) for n > 0. - _Reinhard Zumkeller_, May 09 2005

%F a(n+1) = min{([a(n)/2]+1)*2^k} such that it is not yet in the sequence. - _Gerard Orriols_, Jun 07 2014

%F a(n) = A072650(A003714(n)) = A003188(A227351(n)). - _Antti Karttunen_, May 13 2018

%p a(n) = rewrite_0to0_x1to1(fibbinary(j)) (where fibbinary(j) = A003714[ n ])

%p rewrite_0to0_x1to1 := proc(n) option remember; if(0 = n) then RETURN(n); else RETURN((2 * rewrite_0to0_x1to1(floor(n/(2^(1+(n mod 2)))))) + (n mod 2)); fi; end;

%p fastfib := n -> round((((sqrt(5)+1)/2)^n)/sqrt(5)); fibinv_appr := n -> floor(log[ (sqrt(5)+1)/2 ](sqrt(5)*n)); fibinv := n -> (fibinv_appr(n) + floor(n/fastfib(1+fibinv_appr(n)))); fibbinary := proc(n) option remember; if(n <= 2) then RETURN(n); else RETURN((2^(fibinv(n)-2))+fibbinary_seq(n-fastfib(fibinv(n)))); fi; end;

%p # second Maple program:

%p b:= proc(n) is(n=0) end:

%p a:= proc(n) option remember; local h; h:= iquo(a(n-1), 2)+1;

%p while b(h) do h:= h*2 od; b(h):=true; h

%p end: a(0):=0:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Sep 22 2014

%t b[n_] := n==0; a[n_] := a[n] = Module[{h}, h = Quotient[a[n-1], 2] + 1; While[b[h], h = h*2]; b[h] = True; h]; a[0]=0; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Feb 27 2016, after _Alois P. Heinz_ *)

%o (PARI)

%o A072649(n) = { my(m); if(n<1, 0, m=0; until(fibonacci(m)>n, m++); m-2); }; \\ From A072649

%o A003714(n) = { my(s=0,w); while(n>2, w = A072649(n); s += 2^(w-1); n -= fibonacci(w+1)); (s+n); }

%o A007814(n) = valuation(n,2);

%o A000265(n) = (n/2^valuation(n, 2));

%o A106151(n) = if(n<=1,n,if(n%2,1+(2*A106151((n-1)/2)),(2^(A007814(n)-1))*A106151(A000265(n))));

%o A048679(n) = if(!n,n,A106151(2*A003714(n))); \\ _Antti Karttunen_, May 13 2018, after _Reinhard Zumkeller_'s May 09 2005 formula.

%o (Python)

%o from itertools import count, islice

%o def A048679_gen(): # generator of terms

%o return map(lambda n: int(bin(n)[2:].replace('01','1'),2),filter(lambda n:not (n<<1)&n,count(0)))

%o A048679_list = list(islice(A048679_gen(),20)) # _Chai Wah Wu_, Mar 18 2024

%Y Cf. A000045, A003714, A005203, A048678, A048680, A072650, A087808, A106151, A200714, A227351, A232559, A277006, A304100, A304101.

%K nonn,base

%O 0,3

%A _Antti Karttunen_