A049643 Number of fractions in Farey series of order n.

0, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43, 47, 59, 65, 73, 81, 97, 103, 121, 129, 141, 151, 173, 181, 201, 213, 231, 243, 271, 279, 309, 325, 345, 361, 385, 397, 433, 451, 475, 491, 531, 543, 585, 605, 629, 651, 697, 713, 755, 775, 807, 831, 883

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy
• nice

Comments

Essentially the same as A005728.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..5000
• R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
• N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Crossrefs

Cf. A000010.

Programs

Magma

[0] cat [n le 1 select 2 else Self(n-1)+EulerPhi(n): n in [1..60]]; // G. C. Greubel, Dec 06 2017

Mathematica

a[0] = 0; a[n_] := 1 + Sum[EulerPhi[k], {k, 1, n}]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Nov 27 2015 *)
a[0] = 0; a[1] = 2; a[n_] := a[n -1] + EulerPhi[n]; Array[a, 55, 0] (* Robert G. Wilson v, Dec 13 2017 *)
Join[{0},Rest[Accumulate[EulerPhi[Range[0,60]]]+1]] (* Harvey P. Dale, Oct 16 2018 *)
a[n_] := If[n == 0, 0, FareySequence[n] // Length];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 16 2022 *)

PARI

for(n=0, 30, print1(if(n==0, 0, 1+sum(k=1, n, eulerphi(k))), ", ")) \\ G. C. Greubel, Dec 06 2017

Formula

a(n) = A049641(2*n).

From G. C. Greubel, Dec 13 2017: (Start)

a(n) = 1 + Sum_{k=1..n} phi(k), with a(0)=0.

a(n) = A005728(n) for n >= 1. (End)

a(n) = a(n-1) + phi(n) for n > 1. - Robert G. Wilson v, Dec 13 2017