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,3

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).

Links

Table of n, a(n) for n=1..103.

Formula

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

Example

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.

Sequence in context: A322418 A019569 A003434 * A097849 A100678 A026834

Adjacent sequences: A330805 A330806 A330807 * A330809 A330810 A330811

Keyword

nonn

Author

Jon E. Schoenfield, Jan 11 2020

Status

approved