|
%I #37 Jan 01 2024 09:09:06
%S 1,2,2,3,4,4,6,6,6,8,10,6,12,12,8,12,16,12,18,12,12,20,22,12,20,24,18,
%T 18,28,16,30,24,20,32,24,18,36,36,24,24,40,24,42,30,24,44,46,24,42,40,
%U 32,36,52,36,40,36,36,56,58,24,60,60,36,48,48,40,66,48,44,48,70,36,72
%N a(n) is the number of Fibonacci numbers among (F(1),F(2),F(3),...,F(n)) which are coprime to F(n), where F(n) is the n-th Fibonacci number.
%H Harvey P. Dale, <a href="/A126246/b126246.txt">Table of n, a(n) for n = 1..1000</a>
%F Equals A054523 * (1, 1, 0, 0, 0, ...). - _Gary W. Adamson_, Apr 17 2007
%F From _Jud McCranie_, Nov 11 2017: (Start)
%F Multiplicative with a(p^e) = phi(p^e) = p^(e-1)*(p - 1), except when p = 2, then a(2) = 2, because F(1) = F(2) = 1 and a(2^e) = 3*(2^(e-2)), (e > 1, all smaller Fibonacci numbers are coprime, except ones that are multiples of 3, i.e., every 4th one).
%F If n is odd, then a(n) = phi(n) (Euler's totient function).
%F If n is a multiple of 4 then a(n) = 3*phi(n)/2.
%F If n is congruent to 2 mod 4 then a(n) = 2*phi(n). (End)
%F From _Amiram Eldar_, Aug 21 2023: (Start)
%F Dirichlet g.f.: (1 + 1/2^s) * zeta(s-1)/zeta(s).
%F Sum_{k = 1..n} a(k) ~ c * n^2, where c = 15/(4*Pi^2) = 0.379954... . (End)
%F From _Peter Bala_, Dec 31 2023: (Start)
%F a(n) = Sum_{k = 1..n, gcd(k,n) = 1 or 2} 1 (since gcd(F(k),F(n)) = F(gcd(k,n)) = 1 iff gcd(k,n) = 1 or 2). Cf. phi(n) = A000010(n) = Sum_{k = 1..n, gcd(k,n) = 1} 1. See also A345082.
%F Sum_{d divides n} a(d) = n if n is odd, else 3*n/2 if n is even. See A080512.
%F The Lambert series Sum_{n >= 1} a(n)*x^n/(1 - x^n) = (1 + 3*x + x^2)/(1 - x^2)^2.
%F If n divides m then a(n) divides 2*a(m). (End)
%e F(12) = 144. The six Fibonacci numbers which are coprime to 144 and are <= 144 are F(1) = 1, F(2) = 1, F(5) = 5, F(7) = 13, F(10) = 55 and F(11) = 89. So a(12) = 6.
%e The six numbers k = 1, 2, 5, 7, 10 and 11 are <= 12 and satisfy gcd(k,12) divides 2. So a(12) = 6. - _Peter Bala_, Dec 31 2023
%p with(combinat): a:=proc(n) local ct,i: ct:=0: for i from 1 to n do if gcd(fibonacci(i),fibonacci(n))=1 then ct:=ct+1 else ct:=ct fi: od: ct: end: seq(a(n),n=1..90); # _Emeric Deutsch_, Mar 24 2007
%p # alternative program based on the above
%p with(numtheory): a := proc(n) local ct, i: ct := 0: for i from 1 to n do if gcd(i,n) in divisors(2) then ct := ct + 1 else ct := ct fi: od: ct: end: seq(a(n), n = 1..90); # _Peter Bala_, Dec 31 2023
%t Table[Count[CoprimeQ[Fibonacci[n],#]&/@Fibonacci[Range[n]],True],{n,80}] (* _Harvey P. Dale_, Mar 09 2013 *)
%t a[n_] := {1, 2, 1, 3/2}[[Mod[n, 4, 1]]]*EulerPhi[n]; Array[a, 100] (* _Amiram Eldar_, Aug 21 2023 *)
%o (PARI) a(n) = sum(k=1, n, gcd(fibonacci(k), fibonacci(n)) == 1); \\ _Michel Marcus_, Nov 13 2017
%Y Cf. A000010, A000045, A054523, A080512, A345082.
%K nonn,mult,easy
%O 1,2
%A _Leroy Quet_, Mar 08 2007
%E More terms from _Emeric Deutsch_, Mar 24 2007
%E More terms from _Gary W. Adamson_, Apr 17 2007
|
