A330808 Minimum number of unit fractions that must be added to 1/n to reach 1.

0, 1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 4, 3, 4, 5, 3, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 5, 4, 4, 5, 5, 5, 4, 5, 3, 4, 4, 4, 4, 5, 4, 4, 5, 4, 5, 5, 4, 5, 4, 5, 5, 5, 4, 5, 5, 4, 5, 5, 5, 5, 5, 5, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 4, 4, 5, 5, 5, 5, 4, 5, 5, 4, 4, 5, 5, 6

Offset: 1

Author

Jon E. Schoenfield, Jan 11 2020

Keywords

• nonn

Comments

The unit fraction 1/n and the unit fractions to be added to it need not be distinct.

After a(1)=0, this sequence first differs from A097849 at n=42.

Record high values begin with a(1)=0, a(2)=1, a(3)=2, a(5)=3, a(11)=4, a(17)=5, a(103)=6, a(733)=7, a(27539)=8; of these, the greedy algorithm finds a decomposition of 1-1/n into a(n) unit fractions for all except the last:

1 - 1/1 = 0;

1 - 1/2 = 1/2;

1 - 1/3 = 2/3 = 1/2 + 1/6;

1 - 1/5 = 4/5 = 1/2 + 1/4 + 1/20;

1 - 1/11 = 10/11 = 1/2 + 1/3 + 1/14 + 1/231;

1 - 1/17 = 16/17 = 1/2 + 1/3 + 1/10 + 1/128 + 1/32640;

1 - 1/103 = 102/103 = 1/2 + 1/3 + 1/7 + 1/71 + 1/61430 + 1/4716994695;

1 - 1/733 = 732/733 = 1/2 + 1/3 + 1/7 + 1/45 + 1/4484 + 1/33397845 + 1/2305193137933140;

for 1 - 1/27539 = 27538/27539, the greedy algorithm gives 1/2 + 1/3 + 1/7 + 1/43 + 1/1933 + 1/14893663 + 1/1927127616646187 + 1/4212776934617443752169071350384 + 1/305910674290876542045680841765889946094783697598408841178664976, the sum of 9 unit fractions, but decompositions using only 8 unit fractions exist (e.g., 1/2 + 1/3 + 1/7 + 1/55 + 1/245 + 1/671 + 1/51423 + 1/758368982).

Examples

			For n=1, 1/n = 1/1 = 1, which is already at 1, so no additional unit fractions are needed, thus a(1)=0.
For n=2, 1/n = 1/2; adding the single unit fraction 1/2 gives 1/2 + 1/2 = 1, so a(2)=1.
There is no integer k such that 1/3 + 1/k = 1 (solving for k would give k = 3/2), so a(3) > 1. However, 1/3 + 1/2 + 1/6 = 1, so a(3)=2.
There is no integer k such that 1/5 + 1/k = 1, nor are there any two (not necessarily distinct) integers k1,k2 such that 1/5 + 1/k1 + 1/k2 = 1; however, 1/5 + 1/2 + 1/4 + 1/20 = 1, so a(5)=3.
There is no integer k such that 1/11 + 1/k = 1, no pair of integers k1,k2 such that 1/11 + 1/k1 + 1/k2 = 1, and no set of three integers k1,k2,k3 such that 1/11 + 1/k1 + 1/k2 + 1/k3 = 1, but 1/11 + 1/2 + 1/3 + 1/14 + 1/231 = 1, so a(11)=4.
		

Crossrefs

Cf. A097048, A097049, A097847, A192881, A285261.

Formula

a(n) = A097847(n, n-1).