In a previous entry, we discussed egyptian fractions and, in particular, a greedy algorithm to convert them. We noticed that, once in a while, the greedy algorithm generates a really large denominator, despite harmless-looking fractions:
So, I had an idea to, maybe, minimize the size of the maximum denominator.
The idea I had was to remove a unit fraction that leaves an “easy” remainder, so that the remainder would need fewer unit fractions to be expressed. I started with the decomposition
where is the smallest integer such that divides . For example, with , we find , and we have
Now, does it work? Does it generates fewer terms? Are the denominator smaller?
Well, let us plot the number of fractions for the greedy algorithm vs the proposed decomposition:
We see that the proposed decomposition generates, very often, an absurdly high number of terms compared to the greedy algorithm. That’s not entirely surprising since the decomposition produces relatively small fractions. OK, what about we get the canonical factorization of the denominator and use the smallest prime raised to its maximum power? This one works seems to work better:
…except when the denominator is a prime number. It simply doesn’t work, because, for example, is expressed as , which is not a cromulent solution.
So what’s the conclusion? The conclusion is that heuristics do not always work. The greedy algorithm sometimes yield surprisingly large denominator, my first proposed solution using an integer to split a ratio sometimes generates a very large number of fractions while also generating absurdly large denominators (albeit somewhat more rarely than the greedy algorithm), and the factorization-based heuristics fails when the denominator is a prime number…
To be continued…