login
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_