A126246 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.

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, 18, 28, 16, 30, 24, 20, 32, 24, 18, 36, 36, 24, 24, 40, 24, 42, 30, 24, 44, 46, 24, 42, 40, 32, 36, 52, 36, 40, 36, 36, 56, 58, 24, 60, 60, 36, 48, 48, 40, 66, 48, 44, 48, 70, 36, 72

Offset: 1

Author

Leroy Quet, Mar 08 2007

Keywords

• nonn
• mult
• easy

Examples

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

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000010, A000045, A054523, A080512, A345082.

Programs

Maple

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
# alternative program based on the above
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

Mathematica

Table[Count[CoprimeQ[Fibonacci[n],#]&/@Fibonacci[Range[n]],True],{n,80}] (* Harvey P. Dale, Mar 09 2013 *)
a[n_] := {1, 2, 1, 3/2}[[Mod[n, 4, 1]]]*EulerPhi[n]; Array[a, 100] (* Amiram Eldar, Aug 21 2023 *)

PARI

a(n) = sum(k=1, n, gcd(fibonacci(k), fibonacci(n)) == 1); \\ Michel Marcus, Nov 13 2017

Formula

Equals A054523 * (1, 1, 0, 0, 0, ...). - Gary W. Adamson, Apr 17 2007

From Jud McCranie, Nov 11 2017: (Start)

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).

If n is odd, then a(n) = phi(n) (Euler's totient function).

If n is a multiple of 4 then a(n) = 3*phi(n)/2.

If n is congruent to 2 mod 4 then a(n) = 2*phi(n). (End)

From Amiram Eldar, Aug 21 2023: (Start)

Dirichlet g.f.: (1 + 1/2^s) * zeta(s-1)/zeta(s).

Sum_{k = 1..n} a(k) ~ c * n^2, where c = 15/(4*Pi^2) = 0.379954... . (End)

From Peter Bala, Dec 31 2023: (Start)

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.

Sum_{d divides n} a(d) = n if n is odd, else 3*n/2 if n is even. See A080512.

The Lambert series Sum_{n >= 1} a(n)*x^n/(1 - x^n) = (1 + 3*x + x^2)/(1 - x^2)^2.

If n divides m then a(n) divides 2*a(m). (End)

a(n) = Sum_{d|gcd(n,2)} phi(n/d). - Ridouane Oudra, May 06 2025

Extensions

More terms from Emeric Deutsch, Mar 24 2007

More terms from Gary W. Adamson, Apr 17 2007