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

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

Author

Alonso del Arte, Apr 08 2019

Keywords

• nonn
• easy
• base

Comments

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

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A000045, A000120, A011373.

Programs

Maple

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

Mathematica

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

PARI

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

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

Formula

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