A061446 Primitive part of Fibonacci(n).

1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 46, 15005, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 321, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441

Offset: 1

Author

David Broadhurst, Jun 10 2001

Keywords

• nonn

Comments

Fib(n) = A000045(n) = Product_{d|n} a(d), Lucas(n) = A000204(n) = Product_{d|2n and 2^m|d iff 2^m|2n} a(d) (e.g., Lucas(4) = 7 = a(8), Lucas(6) = 18 = a(12)*a(4)). - Len Smiley, Nov 11 2001

A 2001 Iranian Mathematical Olympiad question shows such a sequence exists whenever gcd(a(m),a(n)) = a(gcd(m,n)).

The problem of the characterization of the family of all GCD-morphic sequences F, i.e., F such that GCD(F(m),F(n)) = F(GCD(m,n)), was posed by A. K. Kwasniewski (GCD-morphic Problem). Dziemianczuk and Bajguz (2008) showed that any GCD-morphic sequence is coded by a certain natural number-valued sequence. - Maciej Dziemianczuk, Jan 15 2009

This is the LCM-transform of the Fibonacci numbers (cf. Nowicki). - N. J. A. Sloane, Jan 02 2016

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• N. Bliss, B. Fulan, S. Lovett, and J. Sommars, Strong Divisibility, Cyclotomic Polynomials, and Iterated Polynomials, Amer. Math. Monthly, 120 (2013), 519-536.
• John Brillhart, Peter L. Montgomery and Robert D. Silverman, Tables of Fibonacci and Lucas factorizations, Math. Comp. 50 (1988), pp. 251-260, S1-S15. Math. Rev. 89h:11002.
• C. K. Caldwell, Lucas Aurifeuillian primitive part
• R. D. Carmichael, On the numerical factors of the arithmetic forms alpha*n+-beta*n, Annals of Math., 2nd ser., 15 (1/4) (1913/14) 30-48.
• Johann Cigler and Hans-Christian Herbig, Factorization of spread polynomials, arXiv:2412.18958 [math.NT], 2024.
• M. Dziemianczuk and W. Bajguz, On GCD-morphic sequences, arXiv:0802.1303 [math.CO], 2008.
• A. K. Kwasniewski, Cobweb posets as noncommutative prefabs, arXiv:math/0503286 [math.CO], 2007; Adv. Stud. Contemp. Math. vol.14 (1) 2007. pp. 37-47.
• Rohit Nagpal and A. Snowden, The module theory of divided power algebras, arXiv preprint arXiv:1606.03431 [math.AC], 2016.
• A. Nowicki, Strong divisibility and LCM-sequences, arXiv:1310.2416 [math.NT], 2013.
• A. Nowicki, Strong divisibility and LCM-sequences, Am. Math. Mnthly 122 (2015), 958-966.

Crossrefs

Cf. A008683, A061447, A061254, A061445, A061442, A061443, A105602, A126025, A126069.

Cf. A000010 (comments on product formulas).

Programs

Maple

N:= 200; # to get a(1) to a(N)
L[0]:= 1:
for i from 1 to N do L[i]:=ilcm(L[i-1],combinat:-fibonacci(i)) od:
seq(L[i]/L[i-1],i=1..N); # Robert Israel, Aug 03 2015

Mathematica

t={1}; Do[f=Fibonacci[n]; Do[f=f/GCD[f,t[[d]]], {d,Most[Divisors[n]]}]; AppendTo[t,f], {n,2,100}]; t
(* Second program: *)
a[n_] := Product[Fibonacci[d]^MoebiusMu[n/d], {d, Divisors[n]}];
Array[a, 45] (* Jean-François Alcover, Jul 04 2019 *)

PARI

a(n)=my(d=divisors(n)); fibonacci(n)/lcm(apply(fibonacci,d[1..#d-1])) \\ Charles R Greathouse IV, Oct 06 2016

Formula

Let r=(1+sqrt(5))/2. For n>2, the primitive part of F(n)=(r^n-(-1/r)^n)/sqrt(5) is Phi_n(-r^2)/r^phi(n) where Phi_n is n-th cyclotomic polynomial and phi is Euler's totient function A000010.

a(n) = Product_{d|n} Fib(d)^mu(n/d), where mu = A008683 (Bliss, Fulan, Lovett, Sommars, eq. (7)). - Jonathan Sondow, Jun 11 2013

a(n) = lcm(Fib(1),Fib(2),...,Fib(n))/lcm(Fib(1),Fib(2),...,Fib(n-1)). - Thomas Ordowski, Aug 03 2015

a(n) = Product_{k=1..n} Fib(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} Fib(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))) where mu = A008683, phi = A000010. - Richard L. Ollerton, Nov 08 2021

Extensions

More terms from Vladeta Jovovic, Nov 09 2001

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, May 29 2007

Edited by Charles R Greathouse IV, Oct 28 2009