# Smallest 'm'

1. May 3, 2006

### bomba923

($m$ may be a function of $k$)

$$\begin{gathered} \forall k \in \mathbb{N},\;{\text{what is the smallest }}m \in \mathbb{N}\;{\text{for which}} \hfill \\ \exists \left( {a_i } \right)_{i = 1}^n \;{\text{where }}\forall i > 0,\;a_i \in \left\{ {0,1, \ldots ,m} \right\}, \hfill \\ {\text{such that }}k = \sum\limits_{i = 1}^n {\frac{{a_i }} {i}} \;\,? \hfill \\ \end{gathered}$$

Last edited: May 3, 2006
2. May 3, 2006

### AKG

Do you have any ideas about this? It looks like a really tough problem. The questions you had asked earlier about expressing r as a linear combination of powers of (p/q), does that help at all with this? A few trivial things to note:

a) For all k, k = k/1 so k itself puts an upper bound on what m can be.
b) If mk is the smallest you can get for k, then the smallest you can get for k+1 is at most mk+1.
c) If there are infinitely many perfect numbers, then for all k except 1, mk can be bounded above by k-1.

3. May 4, 2006

### Nimz

Observation c) is superfluous. If you take b) as a given, m3=2 (3=2/1 + 2/2), from which observation c) follows, without needing infinitely many perfect numbers. Also, m4=2 (4=2/1 + 2/2 + 1/3 + 2/4 + 1/6). Such an exploratory approach won't give any proofs of anything (except upper bounds), but it can help you get a feel for what to expect for mk.

4. May 4, 2006

### AKG

Actually, I forgot to mention that I had found m2 = 1, since 2 = 1 + 1/2 + 1/3 + 1/6, so I don't know why I put c). It would be nice to prove (or disprove) something like that, for every natural number n, we can find a collection of naturals n1, ..., nk greater than n such that $\sum 1/n_i = 1$.

5. May 4, 2006

6. May 4, 2006

### Nimz

Heh. I guess I should've put a $\leq$ for m3 and m4. My original thought was that m could be 1 for all k, but I couldn't get it to work out. If any fraction with odd denominator (in this case, 1) can be written as a finite sum of fractions with 1 in the numerator as that site claims, that'll do it.

7. May 5, 2006

### shmoe

The denominator doesn't have to be odd. Odd denominator meant you could find an Egyptian fraction expansion with odd denominators.

8. Jun 9, 2006

### bomba923

The site claims (citing Martin, 1999) that any positive rational number can be expressed in Egyptian fractions. In other words (the colon here doesn't stand out well in $\LaTeX$),
$$\forall r \in \mathbb{Q}^ + ,\exists \left( {x_1 , \ldots ,x_n } \right) \in \mathbb{Z}^n :x_1 > \cdots > x_n \geqslant 1,r = \sum\limits_{i = 1}^n {x_i^{ - 1} }$$
Where can I find a proof of this?
(Or, how might I begin a proof of this?)

Last edited: Jun 9, 2006
9. Jun 9, 2006

### shmoe

All rationals having Egyptian fractions goes back long before Greg Martin. He proved something about the densities of the denominators (they give a reference for his paper, but you might want to check his website, this work was from his thesis iirc and it used to be on there).

Proving all rationals have a representation stems from

$$\frac{1}{a}=\frac{1}{a+1}+\frac{1}{a(a+1)}$$

Starting with a=2, if you keep performing this split over and over, you keep getting unique denominators, e.g. 1/2=1/3+1/6=1/4+1/12+1/7+1/42=... In this way you can write 1/2 as an egyptian fraction with arbitrarily large denominators. This doesn't take anything fancy to prove, but probably isn't obvious.

Use these expressions for 1/2 to write any p/q as an Egyptian fraction. This is easier than the above.

In any case, you can see:

Owings, J. C., Jr.; Classroom Notes: Another Proof of the Egyptian Fraction Theorem. Amer. Math. Monthly 75 (1968), no. 7, 777--778

10. Jun 15, 2006

### bomba923

A binary tree can be constructed, displaying the [itex]\frac{1}{n} = \frac{1}{{n + 1}} + \frac{1}{{n\left( {n + 1} \right)}} [/tex] expansion along its branches. The first couple of rows are
Code (Text):
1/2
1/3, 1/6
1/4, 1/12, 1/7, 1/42
1/5, 1/20, 1/13, 1/156, 1/8, 1/56 1/43, 1/(42*43)
1/6, 1/30, 1/21, 1/420, 1/14, 1/182, 1/157, 1/(156*157) 1/9, 1/72, 1/57, 1/(56*57) 1/44, 1/(43*44), 1/(42*43+1), 1/(42*43*(42*43+1))
But what about rational numbers greater than one??

$$\begin{gathered} 3 = \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \hfill \\ \frac{1}{2} + \left( {\frac{1}{3} + \frac{1}{6}} \right) + \left( {\frac{1}{4} + \frac{1}{{12}} + \frac{1}{7} + \frac{1}{{42}}} \right) + \left( {\frac{1}{5} + \frac{1}{{20}} + \frac{1}{{13}} + \frac{1}{{156}} + \frac{1}{8} + \frac{1}{{42}} + \frac{1}{{43}} + \frac{1}{{42 \cdot 43}}} \right) + \frac{1}{2}^{*} + \frac{1}{2}^{**} \hfill \\ \end{gathered}$$

*I cannot continue expanding this "1/2" term as 1/6 was added before.
**I cannot continue expanding this "1/2" term as 1/7 was added before.

Of course, I may consider deeper levels/rows, but to show that any natural number can be expanded into Egyptian fractions, I would (likely) have to show that there is an infinite quantity of rows containing no elements in common. How would I do that?

Last edited: Jun 15, 2006
11. Jun 15, 2006

### shmoe

The nth row (call the first row with 1/2 in it the 0th row, the 1/3+1/6 row the 1st row, etc) will have 2^n distinct unit fractions, each with denominator greater than n+2. In this way you can just take a row far enough out to ensure you have nothing in common with a previous row.

In your expansion of 3 for example, the largest so far is 42*43, so you can take row 42*43-1 for the next 1/2, and so on. (A smaller row will likely work as well, but this is about existence, so it's not relevant).

So it's enough to prove the nth row of your tree has 2^n distinct fractions (you know it has 2^n elements), which I'll leave for you to work on.

12. Jun 15, 2006

### bomba923

By the way, is there formula for a non-recursive function f(i,n) that ouputs the ith element in the nth row?

Something like:
$$\begin{gathered} A_0 = \left\{ {\frac{1}{2}} \right\} \hfill \\ A_1 = \left\{ {\frac{1}{3},\frac{1}{6}} \right\} \hfill \\ A_2 = \left\{ {\frac{1}{4},\frac{1}{{12}},\frac{1}{7},\frac{1}{{42}}} \right\} \hfill \\ \vdots \hfill \\ A_n = \bigcup\limits_{i = 1}^{2^n } {\left\{ {f\left( {i,n} \right)} \right\}} \hfill \\ \end{gathered}$$
Where An is the set of elements corresponding to the nth row

Last edited: Jun 15, 2006
13. Jun 19, 2006

### shmoe

I wouldn't think so, but you can retrace the order you applied the transformations a->a+1 and a->a*(a+1) to get to the ith element in the nth row by considering the binary expansion of i-1 with n digits, adding leading 0's as necessary.