A011373 -id:A011373 - cp's OEIS frontend

A242934 Numbers which are not in A011373 = Hamming weights of Fibonacci numbers.

44, 45, 61, 62, 76, 92, 95, 143, 152, 174, 195, 215, 220, 239, 291, 342, 345, 400, 435, 443, 478, 533, 535, 569, 572, 583, 597, 610, 623, 635, 643, 657, 684, 718, 724, 762, 808, 819, 821, 828, 832, 872, 891, 892, 905, 919, 939, 944, 1009, 1038, 1067, 1127, 1149

Offset: 1

M. F. Hasler, May 27 2014

nonn

To compute this sequence efficiently, it would be useful to have good upper and lower bounds on A011373. The scatterplot of that sequence could help to find a good guess.

M. Olkowski and others, Consider the sequence of sums of the digits in the binary representations of the Fibonacci numbers. Does every natural number occur in this sequence?, Number Theory group on LinkedIn.com, May 2014.

Cf. A000045, A000120, A011373.

More terms from Alois P. Heinz, Apr 14 2019

A222295 Conjectured number of Fibonacci numbers with exactly n bits set in their binary representation.

Original entry on oeis.org

1, 4, 4, 2, 3, 3, 4, 1, 4, 2, 1, 5, 5, 2, 2, 2, 5, 4, 3, 2, 2, 2, 3, 5, 3, 3, 2, 4, 2, 1, 4, 3, 2, 3, 3, 1, 6, 3, 2, 3, 3, 4, 4, 5, 0, 0, 3, 3, 2, 2, 5, 4, 3, 1, 5, 2, 2, 2, 5, 7, 3, 0, 0, 1, 2, 7, 3, 3, 2, 4, 3, 1, 2, 4, 4, 2, 0, 3, 1, 3, 7, 3, 4, 1, 3, 4, 3

Offset: 0

T. D. Noe, Feb 22 2013

			We set a(1) = 4 because Fib(1) = 1, Fib(2) = 1, Fib(3) = 2, and Fib(6) = 8.

T. D. Noe, Table of n, a(n) for n = 0..1000

Cf. A004685 (Fibonacci numbers in binary), A221158 (two bits set), A222296.
Cf. A011373 (number of bits set in each Fibonacci number).
Cf. A222601, A222602, A222757, A222758.

f = Fibonacci[Range[0,500]]; Table[Length[Select[f, Total[IntegerDigits[#, 2]] == n &]], {n, 0, 87}]

A353986 Numbers k such that Fibonacci(k) and Fibonacci(k+1) have the same binary weight (A000120).

Original entry on oeis.org

1, 2, 4, 7, 24, 27, 49, 51, 52, 69, 75, 114, 130, 131, 158, 169, 186, 217, 250, 263, 292, 335, 340, 345, 374, 474, 500, 507, 520, 547, 565, 583, 600, 604, 627, 717, 760, 791, 828, 831, 908, 996, 997, 1011, 1023, 1061, 1081, 1114, 1242, 1641, 1660, 1763, 1780

Offset: 1

Amiram Eldar, May 13 2022

Numbers k such that A011373(k) = A011373(k+1).

The corresponding values of A011373(k) are 1, 1, 2, 3, 6, 11, 18, 17, 17, 23, 23, 43, 42, 42, 51, ...

			1 is a term since A011373(1) = A011373(2) = 1.
4 is a term since A011373(4) = A011373(5) = 2.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000045, A000120, A011373.

A353987 is a subsequence.

s[n_] := s[n] = DigitCount[Fibonacci[n], 2, 1]; Select[Range[2000], s[#] == s[# + 1] &]

isok(k) = hammingweight(fibonacci(k)) == hammingweight(fibonacci(k+1)); \\ Michel Marcus, May 13 2022

from itertools import islice
def A353986_gen(): # generator of terms
        a, b, k, ah = 1, 1, 1, 1
        while True:
            if ah == (bh := b.bit_count()):
                yield k
            a, b, ah = b, a+b, bh
            k += 1
A353986_list = list(islice(A353986_gen(),30)) # Chai Wah Wu, May 13 2022

A059016 Number of 0's in binary expansion of Fibonacci(n).

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 3, 1, 2, 4, 1, 3, 6, 3, 3, 6, 2, 4, 8, 8, 5, 8, 7, 4, 10, 11, 8, 7, 8, 7, 12, 10, 13, 9, 11, 13, 12, 11, 16, 14, 11, 11, 14, 13, 12, 16, 10, 19, 21, 15, 16, 18, 18, 19, 21, 16, 17, 23, 16, 20, 25, 23, 16, 20, 24, 19, 26, 20, 32, 24, 25, 27, 24, 23, 27, 28, 29, 31

Offset: 0

Patrick De Geest, Jan 15 2001

Records are 1, 3, 4, 6, 8, 10, 11, 12, 13, 16, 19, 21, 23, 25, 26, 32, ... at positions 0, 6, 9, 12, 18, 24, 25, 30, 32, 38, 47, 48, 57, ... - R. J. Mathar, Nov 05 2012

T. D. Noe, Table of n, a(n) for n = 0..1000

Cf. A011373.

with(combinat): a := proc (n) local fbin: fbin := convert(fibonacci(n), base, 2): nops(fbin)-add(fbin[j], j = 1 .. nops(fbin)) end proc: seq(a(n), n = 0 .. 80); # Emeric Deutsch, Jul 09 2009

a(n)={ my(k=fibonacci(n)); if (k==0, 1, #select(x->!x,  binary(k)))} \\ Harry J. Smith, Jun 24 2009

a(n) = A023416(A000045(n)). - R. J. Mathar, Nov 05 2012

A353987 Numbers k such that F(k), F(k+1) and F(k+2) have the same binary weight (A000120), where F(k) is the k-th Fibonacci number (A000045).

Original entry on oeis.org

1, 51, 130, 996, 3224, 4287, 9951, 12676, 72004, 53812945, 141422620

Offset: 1

Amiram Eldar, May 13 2022

Numbers k such that A011373(k) = A011373(k+1) = A011373(k+2).

The corresponding values of A011373(k) are 1, 17, 42, 354, 1110, 1490, 3451, 4383, 24988, 18678035, ...

			1 is a term since A011373(1) = A011373(2) = A011373(3) = 1.
51 is a term since A011373(51) = A011373(52) = A011373(53) = 17.

Cf. A000045, A000120, A011373.

Subsequence of A353986.

s[n_] := s[n] = DigitCount[Fibonacci[n], 2, 1]; Select[Range[10^4], s[#] == s[# + 1] == s[# + 2] &]

hf(k) = hammingweight(fibonacci(k)); \\ A011373
isok(k) = my(h=hf(k)); (h == hf(k+1)) && (h == hf(k+2)); \\ Michel Marcus, May 13 2022

# if Python version < 3.10, replace c.bit_count() with bin(c).count('1')
from itertools import islice
def A353987_gen(): # generator of terms
        b, c, k, ah, bh = 1, 2, 1, 1, 1
        while True:
            if ah == (ch := c.bit_count()) == bh:
                yield k
            b, c, ah, bh = c, b+c, bh, ch
            k += 1
A353987_list = list(islice(A353987_gen(),7)) # Chai Wah Wu, May 14 2022

a(11) from Dennis Yurichev, Jul 10 2024

A379151 The binary weights of the Catalan numbers (A000108).

Original entry on oeis.org

1, 1, 1, 2, 3, 3, 2, 6, 6, 9, 6, 8, 8, 12, 9, 16, 13, 17, 12, 17, 13, 18, 15, 25, 20, 17, 20, 24, 28, 25, 26, 25, 25, 32, 27, 34, 29, 32, 33, 29, 35, 29, 31, 36, 35, 44, 44, 49, 40, 46, 48, 44, 38, 50, 43, 44, 46, 47, 55, 50, 52, 58, 59, 60, 65, 68, 56, 62, 68

Offset: 0

Amiram Eldar, Dec 16 2024

			a(10) = 6 because Catalan(10) = 16796 = 100000110011100_2, which has 6 one bits. - _Vincenzo Librandi_, Feb 05 2025

Amiram Eldar, Table of n, a(n) for n = 0..10000
Amiram Eldar, Plot of (1/n^2) * Sum_{k=1..n} a(k) for n = 2^(8..23).
Florian Luca and Igor E. Shparlinski, On the g-ary expansions of middle binomial coefficients and Catalan numbers, The Rocky Mountain Journal of Mathematics, Vol. 41, No. 4 (2011), pp. 1291-1301.

Cf. A000102, A000108.

Similar sequences: A011373, A079584, A082481, A379152, A379153.

[&+Intseq(Catalan(n), 2): n in [0..100]]; // Vincenzo Librandi, Feb 05 2025

a[n_] := DigitCount[CatalanNumber[n], 2, 1]; Array[a, 100, 0]

a(n) = hammingweight(binomial(2*n, n)/(n+1));

a(n) = A000120(A000108(n)).
Two formulas from Luca and Shparlinski (2011):
a(n) >= 3 for all but finitely many positive integers n.
a(n) >> eps(n) * sqrt(log(n)), for all n <= X with at most o(X) exceptions as X -> oo, where eps(n) is a function tending to zero as n -> oo.
Conjecture: Sum_{k=1..n} a(k) ~ n^2 / 2 (see the plot in the Links section).

A379153 The binary weights of the Apéry numbers (A005259).

Original entry on oeis.org

1, 2, 3, 6, 6, 14, 15, 15, 20, 19, 23, 23, 27, 34, 35, 44, 40, 36, 40, 44, 41, 48, 52, 62, 64, 66, 57, 66, 72, 79, 71, 75, 77, 78, 79, 78, 88, 86, 92, 100, 103, 103, 92, 116, 96, 116, 117, 113, 129, 117, 123, 128, 123, 126, 130, 133, 129, 142, 147, 134, 135, 148

Offset: 0

Amiram Eldar, Dec 17 2024

Amiram Eldar, Table of n, a(n) for n = 0..10000
Arnold Knopfmacher and Florian Luca, Digit sums of binomial sums, Journal of Number Theory, Vol. 132, No. 2 (2012), pp. 324-331.
Florian Luca and Igor E. Shparlinski, On the g-ary expansions of Apéry, Motzkin, Schröder and other combinatorial numbers, Annals of Combinatorics, Vol. 14 (2010), pp. 507-524.

Cf. A000120, A005259.

Similar sequences: A011373, A079584, A082481, A379151, A379152.

a[n_] := DigitCount[Sum[(Binomial[n, k] * Binomial[n+k, k])^2, {k, 0, n}], 2, 1]; Array[a, 100, 0]

a(n) = hammingweight(sum(k=0, n, (binomial(n, k)*binomial(n+k, k))^2));

a(n) = A000120(A005259(n)).
a(n) > c * (log(n)/log(log(n)))^(1/4) holds on a set of n of asymptotic density 1, where c > 0 is a constant (Luca and Shparlinski, 2010).
a(n) > c * log(n)/log(log(n)) holds on a set of n of asymptotic density 1, where c > 0 is a constant (Knopfmacher and Luca, 2012).
Conjecture: Limit_{m->oo} (1/m^2) * Sum_{k=1..m} a(k) = log(sqrt(2) + 1)/log(2) = 1.2715533... (Knopfmacher and Luca, 2012).

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.

Original entry on oeis.org

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

Jonathan Vos Post, Jun 24 2007

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

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

Cf. A000045, A000120, A011373.

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

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

Extended by Stefan Steinerberger, Jun 25 2007

A379152 The binary weights of the odd Catalan numbers.

Original entry on oeis.org

1, 1, 2, 6, 16, 25, 60, 127, 244, 494, 1010, 2015, 4076, 8086, 16281, 32818, 65518, 131059, 262348, 524448, 1047643, 2097675, 4194133, 8386693, 16776916, 33554390, 67114125, 134214652, 268452748

Offset: 0

Amiram Eldar, Dec 17 2024

Florian Luca and Paul Thomas Young, On the binary expansion of the odd Catalan numbers, Proceedings of the XIVth International Conference on Fibonacci Numbers, Morelia, Mexico, 2010, pp. 185-190; ResearchGate link.

Cf. A000108, A000120, A038003.

Similar sequences: A011373, A079584, A082481, A379151, A379153.

a[n_] := DigitCount[CatalanNumber[2^n-1], 2, 1]; Array[a, 23, 0]

a(n) = my(m = -1 + 1 << n); hammingweight(binomial(2*m, m)/(m+1));

from itertools import count, islice
def A379152_gen(): # generator of terms
    yield from [1,1]
    c, s = 1, 3
    for n in count(2):
        c = (c*((n<<2)-2))//(n+1)
        if n == s:
            yield c.bit_count()
            s = (s<<1)|1
A379152_list = list(islice(A379152_gen(),10)) # Chai Wah Wu, Dec 17 2024

a(n) = A000120(A038003(n)) = A000120(A000108(2^n-1)).

a(n) = A379151(2^n-1).

A307451 Sum of binary weights of two consecutive Fibonacci numbers minus the binary weight of the following Fibonacci number.

Original entry on oeis.org

0, 1, 0, 1, 3, 0, 1, 4, 0, 3, 7, 1, 1, 7, 2, 5, 11, 6, 1, 7, 6, 3, 13, 11, 3, 4, 9, 10, 15, 9, 10, 7, 10, 14, 11, 9, 16, 12, 6, 11, 19, 15, 12, 19, 12, 23, 22, 7, 12, 19, 18, 17, 18, 11, 17, 27, 13, 20, 28, 17, 9, 22, 29, 18, 26, 18, 30, 18, 15, 24, 20, 20, 28, 28, 24, 24, 18, 21, 28

Offset: 2

Alonso del Arte, Apr 08 2019

The binary weight of a positive Fibonacci number is at least 1 (and at least 2 for positive Fibonacci numbers other than 1, 2, 8) but not more than the sum of the binary weights of the previous two Fibonacci numbers.
Therefore a(n) is at least 0, at most n - 1.
Number of carries in base-2 addition of A000045(n-2)+A000045(n-1)=A000045(n). - Robert Israel, Apr 14 2019

			Fibonacci(8) = 21 = 10101 in binary.
Fibonacci(9) = 34 = 100010 in binary.
Fibonacci(10) = 55 = 110111 in binary, which has five 1s. We see that 10101 has three 1s and 100010 just two. Thus a(10) = 0.

Robert Israel, Table of n, a(n) for n = 2..10000
Dario Carrasquel, 5 ways to solve Fibonacci in Scala - Tail Recursion, Memoization, The Pisano Period & More, August 26, 2016.

Cf. A000045, A000120, A011373.

B:= map(t -> convert(convert(combinat:-fibonacci(t),base,2),`+`), [$0..100]):
B[1..-3]-B[2..-2]-B[3..-1]; # Robert Israel, Apr 14 2019

Table[(DigitCount[Fibonacci[n - 2], 2, 1] + DigitCount[Fibonacci[n - 1], 2, 1]) - DigitCount[Fibonacci[n], 2, 1], {n, 2, 100}]

f(n) = hammingweight(fibonacci(n)); \\ A011373
a(n) = f(n-1) + f(n-2) - f(n); \\ Michel Marcus, Apr 14 2019

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 "Case 3: Tail Recursion" from Carrasquel (2016) link
(2 to 100).map(n => (fibonacci(n - 2).bitCount + fibonacci(n - 1).bitCount) - fibonacci(n).bitCount)

a(n) = (A011373(n - 2) + A011373(n - 1)) - A011373(n).

cp's OEIS Frontend

A242934 Numbers which are not in A011373 = Hamming weights of Fibonacci numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A222295 Conjectured number of Fibonacci numbers with exactly n bits set in their binary representation.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A353986 Numbers k such that Fibonacci(k) and Fibonacci(k+1) have the same binary weight (A000120).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A059016 Number of 0's in binary expansion of Fibonacci(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

A353987 Numbers k such that F(k), F(k+1) and F(k+2) have the same binary weight (A000120), where F(k) is the k-th Fibonacci number (A000045).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A379151 The binary weights of the Catalan numbers (A000108).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A379153 The binary weights of the Apéry numbers (A005259).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Comments