login
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.
2

%I #33 Oct 13 2018 03:27:05

%S 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,

%T 31,27,28,32,30,31,36,33,34,39,36,37,42,39,40,44,42,43,50,45,46,53,48,

%U 49,56,51,52,56,54,55,60,57,58,63,60,61,66,63,64,68,66,67,73,69

%N 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.

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

%C 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

%C 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

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

%e 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.

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

%o (PARI) a(n) = vecmax(apply(x->if (x, valuation(x, 2), 0), [3,1;1,-1]^n)); \\ _Michel Marcus_, Sep 09 2018

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

%K nonn

%O 1,3

%A _Greg Dresden_, Sep 09 2018