

A330808


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


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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 11/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, n1).


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



