A255541 a(n) = 1+Sum_{k=1..2^n-1} A000010(k).

1, 2, 5, 19, 73, 309, 1229, 4959, 19821, 79597, 318453, 1274563, 5097973, 20397515, 81591147, 326371001, 1305482159, 5222040189, 20888133573, 83552798667, 334211074959, 1336845501841, 5347382348679, 21389531880435, 85558125961121, 342232529890275, 1368930120480617, 5475720508827645, 21902882035220391, 87611528574186091, 350446114129452131, 1401784457568941917, 5607137830212707769

Offset

0,2

Comments

Number of fractions in Farey series of order 2^n-1.

Links

Table of n, a(n) for n=0..32.

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

Cf. A007305, A007306, A000010, A049643, A006842/A006843 (Farey fractions).

Sequence in context: A148437 A106873 A014273 * A150026 A150027 A277969

Adjacent sequences: A255538 A255539 A255540 * A255542 A255543 A255544

Keyword

nonn

Author

Robert G. Wilson v, Feb 24 2015

Status

approved