A114477 Smallest Fibonacci number with Hamming weight n (i.e., smallest number with exactly n ones when written in binary), or -1 if no such number exists.

0, 1, 3, 13, 89, 55, 377, 1597, 987, 121393, 39088169, 28657, 514229, 3524578, 24157817, 1134903170, 102334155, 165580141, 701408733, 2504730781961, 956722026041, 1836311903, 139583862445, 6557470319842, 591286729879, 17167680177565, 4052739537881, 806515533049393

Offset: 0

Author

Jonathan Vos Post, Jun 24 2007

Keywords

• nonn
• base

Comments

Among the first 10^5 Fibonacci numbers, none have Hamming weight 44, 45, 61, 62, 76, 92, or 95. - T. D. Noe, Jun 25 2007

Links

• Amiram Eldar, Table of n, a(n) for n = 0..43

Crossrefs

Cf. A000045, A000120, A011373.

Programs

Mathematica

a[ n_ ] := Module[ {}, k = 0; While[ Not[ Plus @@ IntegerDigits[ Fibonacci[ k ], 2 ] == n ], k++ ]; Fibonacci[ k ] ]; Table[ a[ i ], {i, 0, 40} ] (* Stefan Steinerberger *)

Formula

a(n) = MIN{A000045(k): A000120(A000045(k)) = n}.

Extensions

Extended by Stefan Steinerberger, Jun 25 2007