login
The OEIS is supported by the many generous donors to the OEIS 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 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

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

Andrey O. Matveev, Farey Sequences, De Gruyter, 2017, Table 1.7.

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]

Brady Haran and Grant Sanderson, Prime Pyramid (with 3Blue1Brown), Numberphile video (2022).

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.

Andrey O. Matveev, Farey Sequences: Errata + Haskell code

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).

Vladimir Sukhoy and Alexander Stoytchev, Formulas and algorithms for the length of a Farey sequence, Scientific Reports, Vol. 11 (2021), Article No. 22218.

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..n} a(floor(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 *)

a[n_] := If[n == 0, 1, FareySequence[n] // Length];

Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 16 2022 *)

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,changed

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 26 04:47 EST 2022. Contains 358353 sequences. (Running on oeis4.)