A005728 Number of fractions in Farey series of order n.

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

Examples

			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.
		

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.

Crossrefs

For the Farey series see A006842/A006843.

Essentially the same as A049643.

Cf. A002088, A055197, A055201.

Programs

GAP

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

Haskell

a005728 n = a005728_list
a005728_list = scanl (+) 1 a000010_list
-- Reinhard Zumkeller, Aug 04 2012

Magma

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

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

PARI

a(n)=1+sum(k=1,n,eulerphi(k)) \\ Charles R Greathouse IV, Jun 03 2013

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

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