cp's OEIS Frontend

A011373 Number of 1's in binary expansion of Fibonacci(n).

%I A011373 #52 Jul 04 2025 02:30:36
%S A011373 0,1,1,1,2,2,1,3,3,2,5,4,2,5,6,4,8,7,4,5,8,6,8,11,6,6,9,11,11,12,8,11,
%T A011373 9,13,12,11,12,14,10,12,16,17,14,16,18,15,21,13,12,18,18,17,17,17,16,
%U A011373 22,21,16,24,20,16,19,26,23,20,25,19,26,15,23,23,22,25,27,24,23,23,22
%N A011373 Number of 1's in binary expansion of Fibonacci(n).
%H A011373 Alois P. Heinz, <a href="/A011373/b011373.txt">Table of n, a(n) for n = 0..10000</a> (first 1001 terms from T. D. Noe)
%H A011373 C. L. Stewart, <a href="https://eudml.org/doc/152278">On the representation of an integer in two different bases</a>, Journal für die reine und angewandte Mathematik 319 (1980): 63-72.
%H A011373 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F A011373 a(n) = A000120(A000045(n)). - _Michel Marcus_, Dec 27 2014
%F A011373 a(n) = [x^Fibonacci(n)] (1/(1 - x))*Sum_{k>=0} x^(2^k)/(1 + x^(2^k)). - _Ilya Gutkovskiy_, Mar 27 2018
%F A011373 Conjecture: Limit_{n->oo} a(n)/n = log_2(phi)/2 = A242208/2 = 0.3471209568... . - _Amiram Eldar_, May 13 2022
%F A011373 Limit_{n->oo} a(n) = oo by a result of C. L. Stewart, linked above. - _David Radcliffe_, Jul 03 2025
%e A011373 a(8) = 3 because Fibonacci(8) = 21, which in binary is 11001 and that has 3 on bits.
%e A011373 a(9) = 2 because Fibonacci(9) = 34, which in binary is 100010 and that only has 2 on bits.
%p A011373 A000120 := proc(n) add(d,d=convert(n,base,2)) ; end proc:
%p A011373 A011373 := proc(n) A000120(combinat[fibonacci](n)) ; end proc:
%p A011373 seq(A011373(n),n=0..50) ; # _R. J. Mathar_, Mar 22 2011
%t A011373 DigitCount[#, 2, 1]&/@Fibonacci[Range[0, 79]] (* _Harvey P. Dale_, Mar 14 2011 *)
%t A011373 Table[Plus@@IntegerDigits[Fibonacci[n], 2], {n, 0, 79}]
%o A011373 (PARI) a(n)=hammingweight(fibonacci(n)) \\ _Charles R Greathouse IV_, Mar 02 2014
%o A011373 (Scala) def fibonacci(n: BigInt): BigInt = {
%o A011373   val zero = BigInt(0)
%o A011373   def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {
%o A011373     case `zero` => a
%o A011373     case _ => fibTail(n - 1, b, a + b)
%o A011373   }
%o A011373   fibTail(n, 0, 1)
%o A011373 } // Based on tail recursion by Dario Carrasquel
%o A011373 (0 to 79).map(fibonacci(_).bitCount) // _Alonso del Arte_, Apr 13 2019
%o A011373 (Python) from sympy import fibonacci
%o A011373 def a(n): return int(fibonacci(n)).bit_count() # _David Radcliffe_, Jul 03 2025
%Y A011373 Cf. A000045, A000120, A059016, A242208.
%K A011373 nonn,base
%O A011373 0,5
%A A011373 _N. J. A. Sloane_