|
%I #13 Jan 11 2020 15:23:16
%S 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,
%T 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,
%U 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
%N Minimum number of unit fractions that must be added to 1/n to reach 1.
%C The unit fraction 1/n and the unit fractions to be added to it need not be distinct.
%C After a(1)=0, this sequence first differs from A097849 at n=42.
%C 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:
%C 1 - 1/1 = 0;
%C 1 - 1/2 = 1/2;
%C 1 - 1/3 = 2/3 = 1/2 + 1/6;
%C 1 - 1/5 = 4/5 = 1/2 + 1/4 + 1/20;
%C 1 - 1/11 = 10/11 = 1/2 + 1/3 + 1/14 + 1/231;
%C 1 - 1/17 = 16/17 = 1/2 + 1/3 + 1/10 + 1/128 + 1/32640;
%C 1 - 1/103 = 102/103 = 1/2 + 1/3 + 1/7 + 1/71 + 1/61430 + 1/4716994695;
%C 1 - 1/733 = 732/733 = 1/2 + 1/3 + 1/7 + 1/45 + 1/4484 + 1/33397845 + 1/2305193137933140;
%C 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).
%F a(n) = A097847(n, n-1).
%e For n=1, 1/n = 1/1 = 1, which is already at 1, so no additional unit fractions are needed, thus a(1)=0.
%e For n=2, 1/n = 1/2; adding the single unit fraction 1/2 gives 1/2 + 1/2 = 1, so a(2)=1.
%e 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.
%e 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.
%e 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.
%Y Cf. A097048, A097049, A097847, A192881, A285261.
%K nonn
%O 1,3
%A _Jon E. Schoenfield_, Jan 11 2020
|
