Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

Himitsu's blog

By Himitsu, history, 19 months ago, In English,


I was reading about Egyptian fractions and I could not understand the reason behind taking the ceiling of D/N (the original fraction is N/D) as the largest unit fraction using the Sylvester's sequence. Can someone explain in easier terms?

Thank You

  • Vote: I like it
  • +16
  • Vote: I do not like it

19 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Not sure what exactly the problem is, but here some thoughts about it.

We have the original fraction . We can represent it as a fraction with numerator 1: . However, the denominator of this fraction is, in most cases, not an integer. We can make it an integer by rounding up. Since the denominator is now bigger, the complete fraction is smaller. It is simply the biggest unit fraction smaller than or equal to .

This has not much to do with the Sylvester's sequence. It's just a fact that you can generate Sylvester's sequence using a modification of the above discussed algorithm.