OFFSET
0,2
COMMENTS
Number of fractions in Farey series of order 2^n-1.
LINKS
D. T. Ashley, J. P. DeVoe, K. Perttunen, C. Pratt, and A. Zhigljavsky, On Best Rational Approximations Using Large Integers
Wikipedia, Farey Sequence
FORMULA
a(n) ~ (2^n-1)^2 / Pi.
a(n) = 2+A015614(2^n-1).
a(n) = A005728 (2^n-1). - Michel Marcus, Feb 27 2015
EXAMPLE
For each n, measure the size of the set of reduced fractions with a denominator less than 2^n:
a(0) = 1 since the set of reduced fractions with denominator less than 2^0 = 1 is {0}.
a(1) = 2 since the set of reduced fractions with denominator less than 2^1 = 2 is {0, 1}.
a(2) = 5 since the set of reduced fractions with denominator less than 2^2 = 4 is {0, 1/3, 1/2, 2/3, 1}.
a(3) = 19 since the set of reduced fractions with denominator less than 2^3 = 8 is {0, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1}.
MATHEMATICA
k = s = 1; lst = {}; Do[While[k < 2^n, s = s + EulerPhi@ k; k++]; AppendTo[lst, s], {n, 0, 26}]; lst
a[n_] := 1 + (1/2) Sum[ MoebiusMu[k]*Floor[n/k]*Floor[1 + n/k], {k, n}]; Array[a, 27, 0]
CROSSREFS
KEYWORD
nonn
AUTHOR
Robert G. Wilson v, Feb 24 2015
STATUS
approved