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)
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
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved