A061446 - OEIS

%I #70 Apr 03 2023 10:36:10

%S 1,1,2,3,5,4,13,7,17,11,89,6,233,29,61,47,1597,19,4181,41,421,199,

%T 28657,46,15005,521,5777,281,514229,31,1346269,2207,19801,3571,141961,

%U 321,24157817,9349,135721,2161,165580141,211,433494437,13201,109441

%N Primitive part of Fibonacci(n).

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

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

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

%C This is the LCM-transform of the Fibonacci numbers (cf. Nowicki). - _N. J. A. Sloane_, Jan 02 2016

%H T. D. Noe, <a href="/A061446/b061446.txt">Table of n, a(n) for n = 1..1000</a>

%H N. Bliss, B. Fulan, S. Lovett, and J. Sommars, <a href="http://dx.doi.org/10.4169/amer.math.monthly.120.06.519">Strong Divisibility, Cyclotomic Polynomials, and Iterated Polynomials</a>, Amer. Math. Monthly, 120 (2013), 519-536.

%H John Brillhart, Peter L. Montgomery and Robert D. Silverman, <a href="http://dx.doi.org/10.1090/S0025-5718-1988-0917832-6">Tables of Fibonacci and Lucas factorizations</a>, Math. Comp. 50 (1988), pp. 251-260, S1-S15. Math. Rev. 89h:11002.

%H C. K. Caldwell, <a href="https://t5k.org/top20/page.php?id=21">Lucas Aurifeuillian primitive part</a>

%H R. D. Carmichael, <a href="http://www.jstor.org/stable/1967797">On the numerical factors of the arithmetic forms alpha*n+-beta*n</a>, Annals of Math., 2nd ser., 15 (1/4) (1913/14) 30-48.

%H M. Dziemianczuk and W. Bajguz, <a href="http://arxiv.org/abs/0802.1303"> On GCD-morphic sequences</a>, arXiv:0802.1303 [math.CO], 2008.

%H A. K. Kwasniewski, <a href="http://arxiv.org/abs/math/0503286">Cobweb posets as noncommutative prefabs</a>, Adv. Stud. Contemp. Math. vol.14 (1) 2007. pp. 37-47.

%H Rohit Nagpal and A. Snowden, <a href="https://arxiv.org/abs/1606.03431">The module theory of divided power algebras</a>, arXiv preprint arXiv:1606.03431 [math.AC], 2016.

%H A. Nowicki, <a href="http://arxiv.org/abs/1310.2416">Strong divisibility and LCM-sequences</a>, arXiv:1310.2416 [math.NT], 2013.

%H A. Nowicki, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.122.10.958">Strong divisibility and LCM-sequences</a>, Am. Math. Mnthly 122 (2015), 958-966.

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

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

%F a(n) = lcm(Fib(1),Fib(2),...,Fib(n))/lcm(Fib(1),Fib(2),...,Fib(n-1)). - _Thomas Ordowski_, Aug 03 2015

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

%p N:= 200; # to get a(1) to a(N)

%p L[0]:= 1:

%p for i from 1 to N do L[i]:=ilcm(L[i-1],combinat:-fibonacci(i)) od:

%p seq(L[i]/L[i-1],i=1..N); # _Robert Israel_, Aug 03 2015

%t t={1}; Do[f=Fibonacci[n]; Do[f=f/GCD[f,t[[d]]], {d,Most[Divisors[n]]}]; AppendTo[t,f], {n,2,100}]; t

%t (* Second program: *)

%t a[n_] := Product[Fibonacci[d]^MoebiusMu[n/d], {d, Divisors[n]}];

%t Array[a, 45] (* _Jean-François Alcover_, Jul 04 2019 *)

%o (PARI) a(n)=my(d=divisors(n)); fibonacci(n)/lcm(apply(fibonacci,d[1..#d-1])) \\ _Charles R Greathouse IV_, Oct 06 2016

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

%Y Cf. A000010 (comments on product formulas).

%K nonn

%O 1,3

%A _David Broadhurst_, Jun 10 2001

%E More terms from _Vladeta Jovovic_, Nov 09 2001

%E Edited by _N. J. A. Sloane_ at the suggestion of _Andrew S. Plewe_, May 29 2007

%E Edited by _Charles R Greathouse IV_, Oct 28 2009