0

An egyptian fraction

$\frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} ...$

is greedy if each $a_n$ is as small as possible, given its predecessors. Every real number between 0 and 1 has exactly one representation as a greedy egyptian fraction.

(similar to continued fractions, for rational numbers this sequence is finite; for irrational numbers it's infinite)

Eg. $\frac12 + \frac1{12}$ is greedy; $\frac13 + \frac14$ is not

Clearly, for an egyptian fraction to be greedy it is necessary for each $a_{n+1}$ to be greater than $a_n \times (a_{n}-1)$ but is it also sufficient?

dspyz
  • 850
  • You're right. I did mean as small as possible. I edited it – dspyz Nov 22 '21 at 16:36
  • Not sure what you mean by sufficient. Are you suggesting that every positive rational number has a representation as a greedy sum of egyptian fractions? Or perhaps rationals in $[0,1]$? This is underspecified. – Rushabh Mehta Nov 22 '21 at 16:37
  • @DonThousand Added clarification – dspyz Nov 22 '21 at 16:44
  • I believe the answer is yes and that it follows directly from your definition of greedy. A proof would certainly name the real number $x$ being expressed as an Egyptian fraction. — That being said, you should revisit what the greedy algorithm does to real numbers greater than $1$, because the $a_n(a_n-1)$ phenomenon doesn't kick in immediately. What is the greedy-algorithm Egyptian fraction for $3$ or $\pi$, for example? – Greg Martin Nov 22 '21 at 16:48
  • @GregMartin The greedy Egyptian fraction for $3$ is $1,1,1$ which does satisfy the criterion – dspyz Nov 22 '21 at 16:50
  • @GregMartin $\frac11+\frac11+\frac11+\frac17+\cdots$ seems work well – Hagen von Eitzen Nov 22 '21 at 16:50
  • Also, @GregMartin I see that $a_n$ places this constraint on $a_{n+1}$, but each of $a_{n-1}$, $a_{n-2}$... also place some constraint on $a_{n+1}$ and I don't see that the constraints placed by the previous terms are necessarily weaker than the constraint placed by the last one – dspyz Nov 22 '21 at 16:52
  • An Egyptian fraction (in its modern mathematical sense) cannot have repeated denominators, so the Egyptian fraction representation of $3$ is $\frac11+\frac12+\cdots+\frac1{10}+\frac1{15}+\frac1{230}+\frac1{57960}$. – Greg Martin Nov 22 '21 at 21:57
  • @GregMartin Edited the question to just be about numbers between 0 and 1. It doesn't really change anything – dspyz Nov 22 '21 at 21:59

1 Answers1

1

I would say it is sufficient too. Assume that we have a sequence $\{a_n\}$ satisfying the property $a_{n+1}\geq a_n\cdot (a_n-1)+1$. Our number is: $$ a=\sum_{n=0}^\infty \frac{1}{a_n} $$ Assume this egyptian fraction is not greedy. Then, there exists an $N$ such that we didn't choose $a_N$ in an appropiate way, that is, we could have written $a_N-1$ because: $$ \sum_{n=N}^\infty \frac{1}{a_n} \geq \frac{1}{a_N-1} $$ Well, then consider $b_m=\frac{1}{a_N-1}-\sum_{n=N}^{m} \frac{1}{a_n}$. Let's see that $b_m\geq \frac{1}{a_m\cdot(a_m-1)}>0$ for every $m$ to generate a contradiction. We will prove it by induction. The base case: $$ b_N=\frac{1}{a_N-1}-\frac{1}{a_N}=\frac{1}{a_N\cdot (a_N-1)} $$ Now, suppose it is true that $b_m\geq \frac{1}{a_m\cdot (a_m-1)}$. Let's prove it for $b_{m+1}$: $$ b_{m+1}=\frac{1}{a_N-1}-\sum_{n=N}^{m+1} \frac{1}{a_n}=b_m-\frac{1}{a_{m+1}}$$ $$ \geq \frac{1}{a_m\cdot (a_m-1)}-\frac{1}{a_{m+1}}\geq \frac{1}{a_{m+1}-1}-\frac{1}{a_{m+1}}=\frac{1}{(a_{m+1}-1)a_{m+1}} $$ where we have used the induction hypothesis in the first inequality and the greedy assumption $a_{m+1}-1\geq a_m\cdot (a_m-1)$ in the second inequality.

Then $b_m\geq 0$ for every $m$. This clearly creates a contradiction with the initial hypothesis that the egyptian fraction is not greedy.

joaquindt
  • 39
  • As you stated it seems not neccesary that the number is between 0 and 1. Furthermore, I didn't indicate it, but this argument is valid also if the egyptian fraction is finite (just consider $b_m$ up to the last term). – joaquindt Nov 22 '21 at 23:38