A319053 a(n) is the exponent of the largest power of 2 that appears in the factorization of the entries in the matrix {{3,1},{1,-1}}^n.

0, 1, 5, 3, 4, 8, 6, 7, 12, 9, 10, 15, 12, 13, 18, 15, 16, 20, 18, 19, 25, 21, 22, 28, 24, 25, 31, 27, 28, 32, 30, 31, 36, 33, 34, 39, 36, 37, 42, 39, 40, 44, 42, 43, 50, 45, 46, 53, 48, 49, 56, 51, 52, 56, 54, 55, 60, 57, 58, 63, 60, 61, 66, 63, 64, 68, 66, 67, 73, 69

Offset: 1

Author

Greg Dresden, Sep 09 2018

Keywords

• nonn

Comments

a(n) appears to equal n-1 for n not a multiple of 3.

The matrix entries of M^n, with n >= 0, are M^n(1, 1) = 2^(n-1)*F(n+3) = A063782(n), M^n(2, 2) = 2^(n-1)*F(n-3) = A319196(n), M^n(1, 2) = M^n(2, 1) = 2^(n-1)*F(n) = A085449(n), where i = sqrt(-1), F = A000045, and F(-1) = 1, F(-2) = -1, F(-3) = 2. Proof by Cayley-Hamilton, with S(n, -i) = (-i)^n*F(n+1), where S(n, x) is given in A049310. - Wolfdieter Lang, Oct 08 2018

The above conjecture is true. From the preceding formulas for the elements of M^n this claims that the Fibonacci numbers F(n-3), F(n) and F(n+3) are always odd for n == 1 or 2 (mod 3). This is true because F(n) is even iff n == 0 (mod 3) (see e.g. Vajda, p.73), and each of the three indices is == 1 or 2 (mod 3) for n == 1 or 2 (mod 3), respectively. - Wolfdieter Lang, Oct 09 2018

Examples

			For n = 3, the matrix {{3,1},{1,-1}}^3 = {{32,8},{8,0}} and the largest power of 2 appearing in the factorization of any entry is 2^5 = 32. Hence, a(3) = 5.
		

References

• S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989, p. 73.

Crossrefs

Cf. A000045, A049310, A063782, A085449, A130481, A319196.

Programs

Mathematica

Join[{0, 1, 5}, Table[Max[ IntegerExponent[Flatten[MatrixPower[{{3, 1}, {1, -1}}, n]], 2]], {n, 4, 40}]]

PARI

a(n) = vecmax(apply(x->if (x, valuation(x, 2), 0), [3,1;1,-1]^n)); \\ Michel Marcus, Sep 09 2018