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)

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

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

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