A074723 Largest power of 2 dividing F(3n) where F(k) is the k-th Fibonacci number.

2, 8, 2, 16, 2, 8, 2, 32, 2, 8, 2, 16, 2, 8, 2, 64, 2, 8, 2, 16, 2, 8, 2, 32, 2, 8, 2, 16, 2, 8, 2, 128, 2, 8, 2, 16, 2, 8, 2, 32, 2, 8, 2, 16, 2, 8, 2, 64, 2, 8, 2, 16, 2, 8, 2, 32, 2, 8, 2, 16, 2, 8, 2, 256, 2, 8, 2, 16, 2, 8, 2, 32, 2, 8, 2, 16, 2, 8, 2, 64, 2, 8, 2, 16, 2, 8, 2, 32, 2, 8, 2

Offset: 1

Author

Benoit Cloitre, Sep 04 2002

Keywords

• nonn

Comments

If m == 1 or 2 (mod 3) then F(m) is odd.

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000045, A001620, A006519, A014445, A297402.

Programs

Maple

seq(`if`(n::odd,2,2^(2+padic:-ordp(n,2))),n=1..100); # Robert Israel, Oct 10 2016

Mathematica

Table[2^(Length@ NestWhileList[#/2 &, Fibonacci[3 n], IntegerQ] - 2), {n, 120}] (* Michael De Vlieger, Oct 10 2016 *)
a[n_] := If[EvenQ[n], 2^(FactorInteger[n][[1]][[2]] + 2), 2]; Array[a, 90] (* Frank M Jackson, Jul 28 2018 *)

PARI

a(n) = 2^valuation(fibonacci(3*n), 2); \\ Michel Marcus, Oct 10 2016

Formula

It appears that 4 never appears and : a(2k+1)=2 a(2^m*(2k+1))=2^(m+2) for k>=0 and m >=1.

From Robert Israel, Oct 10 2016: (Start)

a(2k+1)=2 follows from F(n+6) = 5 F(n) + 8 F(n+1) == F(n) mod 4.

a(2*(2k+1))=8 follows from F(n+12) = 89 F(n) + 144 F(n+1) == 9 F(n) mod 16.

a(2^m*(2k+1)) = 2^(m+2) for m > 2 follows from F(2n) = F(n) (2 F(n-1) + F(n)).

G.f. 2*x/(1-x^2) + Sum_{m>=1} 2^(m+2)*x^(2^m)/(1 - x^(2^(m+1))). (End)

a(n) = A006519(A014445(n)). - Michel Marcus, Oct 10 2016

As proved above, for m > 0, a(2m-1) = 2 and a(2m) = 2^(k+2) where k is the exponent of the even prime in the prime factorization of 2m. Also a(n) = 2*A297402(n). - Frank M Jackson, Jul 28 2018

Sum_{k=1..n} a(k) ~ (2*n/log(2)) * (log(n) + gamma + log(2) - 1), where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 27 2023