

A005728


Number of fractions in Farey series of order n; a(n) = 1 + A002088(n).
(Formerly M0661)


35



1, 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, 901, 941, 965
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Sometimes called Phi(n).
Leo Moser found an interesting way to generate this sequence, see Gardner.


REFERENCES

M. Gardner, The Last Recreations, 1997, chap 12.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, a foundation for computer science, Chapter 4.5  Relative Primality, pages 118  120 and Chapter 9  Asymptotics, Problem 6, pages 448  449, AddisonWesley Publishing Co., Reading, Mass., 1989.
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697712.
S. A. Khan, How Many Equivalent Resistances?, RESONANCE, May 2012; http://www.ias.ac.in/resonance/May2012/p468475.pdf.  From N. J. A. Sloane, Oct 15 2012
S. A. Khan, Farey sequences and resistor networks, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 122, No. 2, May 2012, pp. 153162.  From N. J. A. Sloane, Oct 23 2012
W. J. LeVeque, Topics in Number Theory. AddisonWesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000
Sameen Ahmed KHAN, Mathematica notebook
Eric Weisstein's World of Mathematics, Farey Sequence.


FORMULA

a(n) = 1 + Sum_{i=1..n} phi(i).
a(n) = n(n+3)/2  Sum(k = 2 to n, a([n/k])).  David W. Wilson, May 25, 2002
a(n) = a(n1) + phi(n) with a(0) = 1.  Arkadiusz Wesolowski, Oct 13 2012


EXAMPLE

a(5)=11 because the fractions are 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.


MATHEMATICA

Accumulate@ Array[ EulerPhi, 54, 0] + 1


PROG

(Haskell)
a005728 n = a005728_list
a005728_list = scanl (+) 1 a000010_list
 Reinhard Zumkeller, Aug 04 2012
(PARI) a(n)=1+sum(k=1, n, eulerphi(k)) \\ Charles R Greathouse IV, Jun 03 2013


CROSSREFS

Essentially the same as A049643. Cf. A006843, A002088, A055197, A055201.
Sequence in context: A152900 A079151 A049643 * A050437 A096246 A106639
Adjacent sequences: A005725 A005726 A005727 * A005729 A005730 A005731


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane.


STATUS

approved



