login
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.
6
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,2
LINKS
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)
EXAMPLE
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
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 *)
PROG
(PARI) a(n) = sum(k=1, n, gcd(fibonacci(k), fibonacci(n)) == 1); \\ Michel Marcus, Nov 13 2017
CROSSREFS
KEYWORD
nonn,mult,easy
AUTHOR
Leroy Quet, Mar 08 2007
EXTENSIONS
More terms from Emeric Deutsch, Mar 24 2007
More terms from Gary W. Adamson, Apr 17 2007
STATUS
approved