login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005728 Number of fractions in Farey series of order n.
(Formerly M0661)
48
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.

Consecutively, a(n) is a prime number for n = 1, 2, 3, 4, 5, 6, 7, 8, 9. - Altug Alkan, Sep 26 2015

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, Addison-Wesley Publishing Co., Reading, Mass., 1989.

W. J. LeVeque, Topics in Number Theory. Addison-Wesley, 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

R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.

S. A. Khan, Mathematica notebook

S. A. Khan, How Many Equivalent Resistances?, RESONANCE, May 2012.

S. A. Khan, Farey sequences and resistor networks, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 122, No. 2, May 2012, pp. 153-162.

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(n-1) + phi(n) with a(0) = 1. - Arkadiusz Wesolowski, Oct 13 2012

a(n) = 1 + A002088(n). - Robert G. Wilson v, Sep 26 2015.

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

f[n_] := 1 + Sum[ EulerPhi[m], {m, n}]; Array[f, 55, 0] (* or *)

f[n_] := (Sum[ MoebiusMu[m] Floor[n/m]^2, {m, n}] + 3)/2; f[0] = 1; Array[f, 55, 0] (* or *)

f[n_] := n (n + 3)/2 - Sum[f[Floor[n/m]], {m, 2, n}]; f[0] = 1; Array[f, 55, 0] (* Robert G. Wilson v, Sep 26 2015 *)

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

(MAGMA) [1] cat [n le 1 select 2 else Self(n-1)+EulerPhi(n): n in [1..60]]; // Vincenzo Librandi, Sep 27 2015

CROSSREFS

Essentially the same as A049643. Cf. A006843, A002088, A055197, A055201.

Sequence in context: A079151 A274335 A049643 * A050437 A096246 A106639

Adjacent sequences:  A005725 A005726 A005727 * A005729 A005730 A005731

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 2 13:12 EST 2016. Contains 278678 sequences.