login
A072183
Sequence arising from factorization of the Fibonacci numbers.
4
1, 1, 4, 3, 11, 2, 29, 7, 19, 5, 199, 6, 521, 13, 31, 47, 3571, 17, 9349, 41, 211, 89, 64079, 46, 15251, 233, 5779, 281, 1149851, 61, 3010349, 2207, 9901, 1597, 64681, 321, 54018521, 4181, 67861, 2161, 370248451, 421, 969323029, 13201, 97921
OFFSET
1,3
COMMENTS
For even n, F(n) = Product_{d|n}a(d) and for odd n, F(n) = Product_{d|n}a(2d).
For odd noncomposite n, a(n)=L(n), where L(n) is the n-th Lucas number. a(2)=1. Also a(2p)=F(p) for odd primes.
For even n, F(n) = Product_{d|n}a(d). So for even n, log(F(n)) = Sum_{d|n}log(a(d)). For odd n, L(n) = Product_{d|n}a(d). So for odd n, log(L(n)) = Sum_{d|n}log(a(d)). So we can use the Moebius transformation for getting a(n).
FORMULA
Let h = (1+sqrt(5))/2, K(n, x) = n-th cyclotomic polynomial, so that x^n-1 = Product_{d|n}K(d, x); f(d) is the order of K(d, x). a(n) = (h-1)^f(n)*K(n, h+1).
For odd n: log(a(n)) = Sum_{d|n}mu(n/d)*log(L(d)). For even n: log(a(n)) = Sum_{d|n, d even}mu(n/d)*log(F(d)) + Sum_{d|n, d odd}mu(n/d)*log(L(d)).
EXAMPLE
F(12) = a(1)*a(2)*a(3)*a(4)*a(6)*a(12) = 1*1*4*3*2*6 = 144 for even n, F(15) = a(2)*a(6)*a(10)*a(30) = 1*2*5*61 = 610 for odd n.
For even n: log(a(12)) = mu(6)*log(F(2)) + mu(3)*log(F(4)) + mu(2)*log(F(6)) + mu(1)*log(F(12)) + mu(12)*log(L(1)) + mu(4)*log(L(3)) = 0 - log(3) - log(8) + log(144) + 0 + 0 = log(144/3/8) = log(6): a(12)=6.
For odd n: log(a(15)) = mu(15)*log(L(1)) + mu(5)*log(L(3)) + mu(3)*log(L(5)) + mu(1)*log(L(15)) = 0 - log(4) - log(11) + log(1364) = log((1364/4)/11) = log(31) so a(15) = 31.
MATHEMATICA
F[n_] := Fibonacci[n]; L[n_] := F[n + 1] + F[n - 1]; a[2] = 1; a[n_] := a[n] = If[ PrimeQ[n] || n == 1, L[n], If[ PrimeQ[n/2] && OddQ[n/2], F[n/2], If[ EvenQ[n], F[n]/b[n], a[2n] = F[n]/b[n]; F[2n]/c[2n]]]]; b[n_] := (d = Delete[ Divisors[n], -1]; p = 1; k = 1; l = Length[d]; While[k < l + 1, p = p*If[EvenQ[n], a[ d[[k]]], a[ 2d[[k]]]]; k++ ]; p); c[n_] := (d = Delete[Divisors[n], -2]; p = 1; k = 1; l = Length[d]; While[k < l + 1, p = p*a[ d[[k]]]; k++ ]; p); Table[ a[n], {n, 1, 50}]
CROSSREFS
Sequence in context: A241862 A222510 A100492 * A353341 A375035 A346614
KEYWORD
nonn
AUTHOR
Miklos Kristof, Jul 01 2002
EXTENSIONS
Edited and extended by Robert G. Wilson v and Vladeta Jovovic, Jul 02 2002
STATUS
approved