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