Skip to main content
3 of 6
deleted 2 characters in body
AnttiP
  • 7.9k
  • 15
  • 61

Python 3, 159 144 bytes

lambda x:min(f(x),key=len)
f=lambda x,s={1},i=1,p=1,l=[]:i<7*x**x**x**x**x and f(x,s^{i},1+i*(i in s),p*i,l+[s]*(sum(p//y for y in s)==x*p))or l

Try it online!

Bruteforces trough all Egyptian fractions, in order of maximum denominator. A limit of \$7x^{x^{x^{x^{x}}}}\$ is used to stop the program. Then the shortest fraction is picked.

Now the elephant in the room is the upper bound \$7x^{x^{x^{x^{x}}}}\$. This corresponds to the maximum denominator in an optimal solution. Let's see how this bound is obtained.

Let's first make an upper bound for the length of the Egyptian fraction. To construct the egyptian fraction for x, we first greedily pick unit fractions, until the next one would get us over x. For example, if x is 2, then we would do \$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}\$, stopping before \$\frac{1}{4}\$, since that would result in a sum greater then 2. Note that this initial tail has length less than \$e^x\$.

Now we have \$2-\frac{1}{1}+\frac{1}{2}+\frac{1}{3}=\frac{1}{6}\$. Here we got lucky, and the difference is already a unit fraction. If it isn't, we can use the greedy algorithm to turn the difference into a unit fraction. The amount of fractions that the greedy algorithm introduces is at most the denominator of the difference. The denominator is less than the numerator which is less than \$e^x!<(e^x)^{e^x}=e^{xe^x}<x^{x^x}\$ for \$x\ge 4\$.

Finally, if we have an integer egyptian fraction of length l, the numerator can be at most l^l. To see why, note that the numerator of the last fraction can't be greater than the product of the other numerators.

Now we have the upper bound \$(x^{x^x})^{x^{x^x}}=x^{x^xx^{x^x}}<x^{x^{x^{x^{x}}}}\$. when \$x\ge 4\$. To fix the lower ones just multiply the power tower monstrosity with 7, for a final bound of \$7x^{x^{x^{x^{x}}}}\$

This has to be the worst upper bound I've ever seen in my life. If someone can come up with a better bound, please tell me.

AnttiP
  • 7.9k
  • 15
  • 61