Cody

# Problem 2838. Optimum Egyptian Fractions

Solution 1259687

Submitted on 30 Aug 2017 by Alfonso Nieto-Castanon
• Size: 33
• This is the leading solution.
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

### Test Suite

Test Status Code Input and Output
1   Pass
A = 1; B = 4; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),4);

Sum of C: 4, best 4

2   Pass
A = 2; B = 6; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),3);

Sum of C: 3, best 3

3   Pass
A = 3; B = 7; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),59);

Sum of C: 245, best 59

4   Pass
A = 11; B = 30; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),11);

Sum of C: 33, best 11

5   Pass
% random for k = 3:7; C_min = unique(randi([2 30],1,k)); A = 0; B = 1; for l = C_min A = round((A*l + B)/gcd(l,B)); B = lcm(B,l); end C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Choosen A: %d, B: %d\nbased on random C: [%s\b]\n Sum of C: %d, best is %d or less\n',A,B,sprintf(' %d,',C_min),sum(C),sum(C_min)); end

Choosen A: 83, B: 540 based on random C: [ 12, 27, 30,] Sum of C: 416116933, best is 69 or less Choosen A: 223, B: 700 based on random C: [ 7, 10, 25, 28,] Sum of C: 544, best is 70 or less Choosen A: 649, B: 2340 based on random C: [ 12, 15, 18, 26, 30,] Sum of C: 249001838739142, best is 101 or less Choosen A: 1081, B: 3060 based on random C: [ 9, 10, 17, 20, 30,] Sum of C: 3114, best is 86 or less Choosen A: 126713, B: 178640 based on random C: [ 4, 5, 11, 14, 16, 29,] Sum of C: 2.375459e+142, best is 79 or less

6   Pass
A = 2; B = 101; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),1212);

Sum of C: 5202, best 1212

7   Pass
A = 11; B = 28; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),11);

Sum of C: 1448, best 11

8   Pass
A = 17; B = 24; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),15);

Sum of C: 127, best 15

9   Pass
A = 25; B = 36; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),16);

Sum of C: 44, best 16

10   Pass
A = 1805; B = 1806; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),55);

Sum of C: 55, best 55

11   Pass
A = 287; B = 396; C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) && all(C>1) && isequal(sort(C),unique(C)) && abs(fra-fra_correct)<10*eps(fra)); fprintf('Sum of C: %d, best %d',sum(C),49);

Sum of C: 11368048, best 49

12   Pass
% Scoring. % by courtesy of LY Cao fid = fopen('score.p','wb'); fwrite(fid,sscanf('7630312E30307630302E30300008501CD77E9FB100000035000001110000018422762999A8C1DE50537BEE443F4D73651F830FC6C78ADFB7DF68DF98823F565884DC58E21C7E397E3D26E4FFEA9A0D83589ABB5C0B0B553B44CFD79C9B272D11DF1965AD538598E8319529727DF4C4CF36A6016DD7816544AE5A8F64C9B2D9D0C4B94DD5EDF14595CBFE3D402647499EA3D9D125AC927454ED85973BCD1AAEA536D5A6CDDCD78A0211E8179603FFE12E4AB0E4704EA195704428700BAE5C4DFD42FF1A8760EDF2721F9724498ECC9F957735E7A3CDB9630DB17DF92ACE8F486706020E0A8D022D14BC313879724760AE20D67F572DD85211E4BEA45CDF3E22976253F113AEA96C1FF907329E4BD429BCFC6331077DA21F05D791DA6ECCF680D2E23AC77DFCE5C1D9869D3098F5B89FF92A','%2x')); fclose(fid); % Those lists may be extended and scoring mechanism may be changed a bit listA = [2 2 2 2 3 3 3 3 4 5 5 13 31 1805]; listB = [5 7 21 25 5 7 8 71 71 121 17 42 311 1806]; S = 0; try for k = 1:numel(listA), A = listA(k); B = listB(k); C = egyptian(A,B); fra = sum(1./double(C)); fra_correct = A/B; assert(~any(mod(C,1)) ... && all(C>1) ... && isequal(sort(C),unique(C)) ... && abs(fra-fra_correct)<10*eps(fra)); S = S + sum(C); end score(round(20*log10(double(S)))); catch score(1e4); error+1; end

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!