cp's OEIS Frontend

A022290 Replace 2^k in binary expansion of n with Fibonacci(k+2).

%I A022290 #70 Mar 28 2024 21:54:12
%S A022290 0,1,2,3,3,4,5,6,5,6,7,8,8,9,10,11,8,9,10,11,11,12,13,14,13,14,15,16,
%T A022290 16,17,18,19,13,14,15,16,16,17,18,19,18,19,20,21,21,22,23,24,21,22,23,
%U A022290 24,24,25,26,27,26,27,28,29,29,30,31,32,21,22,23,24,24,25,26
%N A022290 Replace 2^k in binary expansion of n with Fibonacci(k+2).
%H A022290 Reinhard Zumkeller, <a href="/A022290/b022290.txt">Table of n, a(n) for n = 0..10000</a>
%F A022290 G.f.: (1/(1-x)) * Sum_{k>=0} F(k+2)*x^2^k/(1+x^2^k), where F = A000045.
%F A022290 a(n) = Sum_{k>=0} A030308(n,k)*A000045(k+2). - _Philippe Deléham_, Oct 15 2011
%F A022290 a(A003714(n)) = n. - _R. J. Mathar_, Jan 31 2015
%F A022290 a(A000225(n)) = A001911(n). - _Philippe Deléham_, Jun 05 2015
%F A022290 From _Jeffrey Shallit_, Jul 17 2018: (Start)
%F A022290 Can be computed from the recurrence:
%F A022290 a(4*k)   = a(k) + a(2*k),
%F A022290 a(4*k+1) = a(k) + a(2*k+1),
%F A022290 a(4*k+2) = a(k) - a(2*k) + 2*a(2*k+1),
%F A022290 a(4*k+3) = a(k) - 2*a(2*k) + 3*a(2*k+1),
%F A022290 and the initial terms a(0) = 0, a(1) = 1. (End)
%F A022290 a(A003754(n)) = n-1. - _Rémy Sigrist_, Jan 28 2020
%F A022290 From _Rémy Sigrist_, Aug 04 2022: (Start)
%F A022290 Empirically:
%F A022290 - a(2*A003714(n)) = A022342(n+1),
%F A022290 - a(3*A003714(n)) = a(4*A003714(n)) = A026274(n) for n > 0.
%F A022290 (End)
%e A022290 n=4 = 2^2 is replaced by A000045(2+2) = 3. n=5 = 2^2 + 2^0 is replaced by A000045(2+2) + A000045(0+2) = 3+1 = 4. - _R. J. Mathar_, Jan 31 2015
%e A022290 From _Philippe Deléham_, Jun 05 2015: (Start)
%e A022290 This sequence regarded as a triangle with rows of lengths 1, 1, 2, 4, 8, 16, ...:
%e A022290   0
%e A022290   1
%e A022290   2, 3
%e A022290   3, 4, 5, 6
%e A022290   5, 6, 7, 8, 8, 9, 10, 11
%e A022290   8, 9, 10, 11, 11, 12, 13, 14, 13, 14, 15, 16, 16, 17, 18, 19
%e A022290   ...
%e A022290 (End)
%p A022290 A022290 := proc(n)
%p A022290     dgs := convert(n,base,2) ;
%p A022290     add( op(i,dgs)*A000045(i+1),i=1..nops(dgs)) ;
%p A022290 end proc: # _R. J. Mathar_, Jan 31 2015
%p A022290 # second Maple program:
%p A022290 b:= (n, i, j)-> `if`(n=0, 0, j*irem(n, 2, 'q')+b(q, j, i+j)):
%p A022290 a:= n-> b(n, 1$2):
%p A022290 seq(a(n), n=0..127);  # _Alois P. Heinz_, Jan 26 2022
%t A022290 Table[Reverse[#].Fibonacci[1 + Range[Length[#]]] &@ IntegerDigits[n, 2], {n, 0, 54}] (* IWABUCHI Yu(u)ki, Aug 01 2012 *)
%o A022290 (Haskell)
%o A022290 a022290 0 = 0
%o A022290 a022290 n = h n 0 $ drop 2 a000045_list where
%o A022290    h 0 y _      = y
%o A022290    h x y (f:fs) = h x' (y + f * r) fs where (x',r) = divMod x 2
%o A022290 -- _Reinhard Zumkeller_, Oct 03 2012
%o A022290 (PARI) my(m=Mod('x,'x^2-'x-1)); a(n) = subst(lift(subst(Pol(binary(n)), 'x,m)), 'x,2); \\ _Kevin Ryde_, Sep 22 2020
%o A022290 (Python)
%o A022290 def A022290(n):
%o A022290     a, b, s = 1,2,0
%o A022290     for i in bin(n)[-1:1:-1]:
%o A022290         s += int(i)*a
%o A022290         a, b = b, a+b
%o A022290     return s # _Chai Wah Wu_, Sep 10 2022
%Y A022290 Other sequences that are built by replacing 2^k in the binary representation with other numbers: A029931 (naturals), A054204 (even-indexed Fibonacci numbers), A062877 (odd-indexed Fibonacci numbers), A059590 (factorials), A089625 (primes).
%Y A022290 Cf. A003754, A022342, A026274.
%K A022290 nonn,tabf,base
%O A022290 0,3
%A A022290 _Marc LeBrun_