A074934 Number of integers in {1, 2, ..., Fibonacci(n)} that are coprime to n.

1, 1, 2, 2, 4, 3, 12, 11, 23, 22, 81, 48, 216, 162, 325, 494, 1504, 861, 3961, 2706, 6256, 8051, 27412, 15456, 60020, 56028, 130946, 136205, 496497, 221878, 1302841, 1089155, 2136108, 2683712, 6327404, 4976784, 23504904, 18515449, 38920607, 40933662, 161541601

Offset

1,3

Comments

Compare the definition to phi(n) = number of integers in {1, 2, ..., n} that are coprime to n (A000010).

Links

Sean A. Irvine, Table of n, a(n) for n = 1..1000

Formula

a(n) = Sum_{d|n} mu(d)*floor(Fibonacci(n)/d). - Ridouane Oudra, Apr 03 2025

Example

There are four integers in {1, 2, ..., Fibonacci(5) = 5} that are coprime to 5, i.e. 1, 2, 3, 4. Hence a(5) = 4.

Maple

with(numtheory): seq(add(mobius(d)*floor(combinat[fibonacci](n)/d), d in divisors(n)), n=1..80) ; # Ridouane Oudra, Apr 03 2025

Mathematica

h[n_] := Module[{l}, l = {}; For[i = 1, i <= Fibonacci[n], i++, If[GCD[i, n] == 1, l = Append[l, i]]]; l]; Table[Length[h[i]], {i, 1, 21}]
Table[Count[Range[Fibonacci[n]], _?(CoprimeQ[#, n]&)], {n, 25}] (* Harvey P. Dale, Oct 31 2011 *)

Crossrefs

Cf. A000010, A000045, A008683.

Sequence in context: A241580 A323257 A054529 * A376908 A376339 A089886

Adjacent sequences: A074931 A074932 A074933 * A074935 A074936 A074937

Keyword

nonn

Author

Joseph L. Pe, Oct 04 2002

Extensions

More terms from Harvey P. Dale, Oct 31 2011

a(26)-a(41) from Donovan Johnson, Nov 03 2011

Status

approved