login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

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

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

Named after the English geologist and writer John Farey, Sr. (1766-1826). - Amiram Eldar, Jun 17 2021

REFERENCES

Martin Gardner, The Last Recreations, 1997, chapter 12.

Ronald L. Graham, Donald E. Knuth and Oren 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.

William Judson LeVeque, Topics in Number Theory, Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

Leo Moser, Solution to Problem P42, Canadian Mathematical Bulletin, Vol. 5, No. 3 (1962), pp. 312-313.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Antoine Mathys, Table of n, a(n) for n = 0..20000 (terms 0 to 1000 from T. D. Noe)

Richard K. Guy, Letter to N. J. A. Sloane, 1986.

Richard K. Guy, Letter to N. J. A. Sloane, 1987.

Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712.

Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]

Sameen Ahmed Khan, Mathematica notebook.

Sameen Ahmed Khan, How Many Equivalent Resistances?, RESONANCE, May 2012.

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

Sameen Ahmed Khan, Beginning to count the number of equivalent resistances, Indian Journal of Science and Technology, Vol. 9, No. 44 (2016), pp. 1-7.

Shmuel Schreiber and N. J. A. Sloane, Correspondence, 1980.

N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021. (Includes this sequence)

Vladimir Sukhoy and Alexander Stoytchev, Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle, Scientific Reports, Vol. 10, Article No. 4852 (2020).

Eric Weisstein's World of Mathematics, Farey Sequence.

Wikipedia, 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.

MAPLE

A005728 := proc(n)

    1+add(numtheory[phi](i), i=1..n) ;

end proc:

seq(A005728(n), n=0..80) ; # R. J. Mathar, Nov 29 2017

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

(GAP) List([0..60], n->Sum([1..n], i->Phi(i)))+1; # Muniru A Asiru, Jul 31 2018

(Python)

from functools import lru_cache

@lru_cache(maxsize=None)

def A005728(n): # based on second formula in A018805

    if n == 0:

        return 1

    c, j = -2, 2

    k1 = n//j

    while k1 > 1:

        j2 = n//k1 + 1

        c += (j2-j)*(2*A005728(k1)-3)

        j, k1 = j2, n//j2

    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

CROSSREFS

For the Farey series see A006842/A006843.

Essentially the same as A049643.

Cf. 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 12:38 EST 2021. Contains 349463 sequences. (Running on oeis4.)