login

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 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of fractions in Farey series of order n.
(Formerly M0661)
106

%I M0661 #130 Nov 15 2022 09:17:49

%S 1,2,3,5,7,11,13,19,23,29,33,43,47,59,65,73,81,97,103,121,129,141,151,

%T 173,181,201,213,231,243,271,279,309,325,345,361,385,397,433,451,475,

%U 491,531,543,585,605,629,651,697,713,755,775,807,831,883,901,941,965

%N Number of fractions in Farey series of order n.

%C Sometimes called Phi(n).

%C Leo Moser found an interesting way to generate this sequence, see Gardner.

%C 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

%C Named after the English geologist and writer John Farey, Sr. (1766-1826). - _Amiram Eldar_, Jun 17 2021

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

%D 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.

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

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

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

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

%H Antoine Mathys, <a href="/A005728/b005728.txt">Table of n, a(n) for n = 0..20000</a> (terms 0 to 1000 from T. D. Noe)

%H Richard K. Guy, <a href="/A005727/a005727.pdf">Letter to N. J. A. Sloane, 1986</a>.

%H Richard K. Guy, <a href="/A005728/a005728.pdf">Letter to N. J. A. Sloane, 1987</a>.

%H Richard K. Guy, <a href="http://www.jstor.org/stable/2322249">The strong law of small numbers</a>. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712.

%H Richard K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]

%H Brady Haran and Grant Sanderson, <a href="https://www.youtube.com/watch?v=NsjsLwYRW8o">Prime Pyramid (with 3Blue1Brown)</a>, Numberphile video (2022).

%H Sameen Ahmed Khan, <a href="/A005728/a005728.nb">Mathematica notebook</a>.

%H Sameen Ahmed Khan, <a href="http://www.ias.ac.in/resonance/May2012/p468-475.pdf">How Many Equivalent Resistances?</a>, RESONANCE, May 2012.

%H Sameen Ahmed Khan, <a href="http://www.ias.ac.in/mathsci/vol122/may2012/pmsc-d-10-00141.pdf">Farey sequences and resistor networks</a>, Proc. Indian Acad. Sci. (Math. Sci.), Vol. 122, No. 2 (May 2012), pp. 153-162.

%H Sameen Ahmed Khan, <a href="http://dx.doi.org/10.17485/ijst%2F2016%2Fv9i44%2F88086">Beginning to count the number of equivalent resistances</a>, Indian Journal of Science and Technology, Vol. 9, No. 44 (2016), pp. 1-7.

%H Andrey O. Matveev, <a href="https://github.com/andreyomatveev/farey-sequences">Farey Sequences: Errata + Haskell code</a>

%H Shmuel Schreiber and N. J. A. Sloane, <a href="/A006368/a006368.pdf">Correspondence, 1980</a>.

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021. (Includes this sequence)

%H Vladimir Sukhoy and Alexander Stoytchev, <a href="https://doi.org/10.1038/s41598-020-60878-7">Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle</a>, Scientific Reports, Vol. 10, Article No. 4852 (2020).

%H Vladimir Sukhoy and Alexander Stoytchev, <a href="https://doi.org/10.1038/s41598-021-99545-w">Formulas and algorithms for the length of a Farey sequence</a>, Scientific Reports, Vol. 11 (2021), Article No. 22218.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FareySequence.html">Farey Sequence</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Farey_sequence">Farey sequence</a>.

%F a(n) = 1 + Sum_{i=1..n} phi(i).

%F a(n) = n*(n+3)/2 - Sum_{k=2..n} a(floor(n/k)). - _David W. Wilson_, May 25 2002

%F a(n) = a(n-1) + phi(n) with a(0) = 1. - _Arkadiusz Wesolowski_, Oct 13 2012

%F a(n) = 1 + A002088(n). - _Robert G. Wilson v_, Sep 26 2015

%e 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.

%p A005728 := proc(n)

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

%p end proc:

%p seq(A005728(n),n=0..80) ; # _R. J. Mathar_, Nov 29 2017

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

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

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

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

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

%t Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Jul 16 2022 *)

%o (Haskell)

%o a005728 n = a005728_list

%o a005728_list = scanl (+) 1 a000010_list

%o -- _Reinhard Zumkeller_, Aug 04 2012

%o (PARI) a(n)=1+sum(k=1,n,eulerphi(k)) \\ _Charles R Greathouse IV_, Jun 03 2013

%o (Magma) [1] cat [n le 1 select 2 else Self(n-1)+EulerPhi(n): n in [1..60]]; // _Vincenzo Librandi_, Sep 27 2015

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

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

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

%o if n == 0:

%o return 1

%o c, j = -2, 2

%o k1 = n//j

%o while k1 > 1:

%o j2 = n//k1 + 1

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

%o j, k1 = j2, n//j2

%o return (n*(n-1)-c+j)//2 # _Chai Wah Wu_, Mar 24 2021

%Y For the Farey series see A006842/A006843.

%Y Essentially the same as A049643.

%Y Cf. A002088, A055197, A055201.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_