|
| |
|
|
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.
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
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)
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)
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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
