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
Examples
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.
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.
Programs
-
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}]
-
PARI
a(n)=hammingweight(fibonacci(n)) \\ Charles R Greathouse IV, Mar 02 2014
-
Python
from sympy import fibonacci def a(n): return int(fibonacci(n)).bit_count() # David Radcliffe, Jul 03 2025
-
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
Formula
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
Comments