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

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, 9, 13, 12, 11, 12, 14, 10, 12, 16, 17, 14, 16, 18, 15, 21, 13, 12, 18, 18, 17, 17, 17, 16, 22, 21, 16, 24, 20, 16, 19, 26, 23, 20, 25, 19, 26, 15, 23, 23, 22, 25, 27, 24, 23, 23, 22

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)

C. L. Stewart, On the representation of an integer in two different bases, Journal für die reine und angewandte Mathematik 319 (1980): 63-72.

Index entries for sequences related to binary expansion of n.

Formula

a(n) = A000120(A000045(n)). - Michel Marcus, Dec 27 2014

a(n) = [x^Fibonacci(n)] (1/(1 - x))*Sum_{k>=0} x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Mar 27 2018

Conjecture: Limit_{n->oo} a(n)/n = log_2(phi)/2 = A242208/2 = 0.3471209568... . - Amiram Eldar, May 13 2022

Limit_{n->oo} a(n) = oo by a result of C. L. Stewart, linked above. - David Radcliffe, Jul 03 2025

Example

a(8) = 3 because Fibonacci(8) = 21, which in binary is 11001 and that has 3 on bits.
a(9) = 2 because Fibonacci(9) = 34, which in binary is 100010 and that only has 2 on bits.

Maple

A000120 := proc(n) add(d, d=convert(n, base, 2)) ; end proc:
A011373 := proc(n) A000120(combinat[fibonacci](n)) ; end proc:
seq(A011373(n), n=0..50) ; # R. J. Mathar, Mar 22 2011

Mathematica

DigitCount[#, 2, 1]&/@Fibonacci[Range[0, 79]] (* Harvey P. Dale, Mar 14 2011 *)
Table[Plus@@IntegerDigits[Fibonacci[n], 2], {n, 0, 79}]

Prog

(PARI) a(n)=hammingweight(fibonacci(n)) \\ Charles R Greathouse IV, Mar 02 2014
(Scala) def fibonacci(n: BigInt): BigInt = {
  val zero = BigInt(0)
  def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {
    case `zero` => a
    case _ => fibTail(n - 1, b, a + b)
  }
  fibTail(n, 0, 1)
} // Based on tail recursion by Dario Carrasquel
(0 to 79).map(fibonacci(_).bitCount) // Alonso del Arte, Apr 13 2019
(Python) from sympy import fibonacci
def a(n): return int(fibonacci(n)).bit_count() # David Radcliffe, Jul 03 2025

Crossrefs

Cf. A000045, A000120, A059016, A242208.

Sequence in context: A348331 A035387 A242308 * A321783 A327035 A177352

Adjacent sequences: A011370 A011371 A011372 * A011374 A011375 A011376

Keyword

nonn,base

Author

N. J. A. Sloane

Status

approved