A119983 Number of ways to partition 1 into reduced fractions i/j with j <= n.

1, 2, 4, 7, 13, 22, 36, 59, 107, 189, 244, 494, 594, 1063, 3276, 5508, 5804, 12427, 12916, 42411, 131773, 167588, 168842, 428013, 839368, 1015502, 1968162, 5787287, 5791851, 15163759, 15170600, 28838713, 75983560, 82753548, 486356263, 1158442727, 1158464363

Offset: 1

Author

Franklin T. Adams-Watters, Aug 01 2006

Keywords

• nonn

Comments

The reduced fractions are the Farey fractions of order n (A005728). - Robert G. Wilson v, Aug 30 2010

Examples

			a(3) = 4; 1 = 1/1 = 1/2 + 1/2 = 2/3 + 1/3 = 1/3 + 1/3 + 1/3.
		

Crossrefs

Cf. A000041, A020473, A115855 (one less), A115856.

Cf. A154886, A154888. - Reinhard Zumkeller, Jan 17 2009

Programs

Mathematica

Farey[n_] := Union@ Flatten@ Table[a/b, {b, n}, {a, b}]; f[n_] := Length@ IntegerPartitions[1, All, Farey@ n]; Array[f, 27] (* Robert G. Wilson v, Aug 30 2010 *)

Formula

For p prime, a(p) = a(p-1) + P(p) - 1, where P is the partition function (A000041).

Extensions

Definition corrected by Reinhard Zumkeller, Jan 17 2009

a(21)-a(27) from Robert G. Wilson v, Aug 30 2010

More terms from Jinyuan Wang, Dec 12 2024