Smallest m for a given k: Solving the Equation

[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}$$

 

[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 m_k is the smallest you can get for k, then the smallest you can get for k+1 is at most m_k+1.
c) If there are infinitely many perfect numbers, then for all k except 1, m_k can be bounded above by k-1.

 

[Nimz]

Observation c) is superfluous. If you take b) as a given, m₃=2 (3=2/1 + 2/2), from which observation c) follows, without needing infinitely many perfect numbers. Also, m₄=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 m_k.

 

[AKG]

Actually, I forgot to mention that I had found m₂ = 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 n₁, ..., n_k greater than n such that $\sum 1/n_i = 1$.

 

[shmoe]

See http://mathworld.wolfram.com/EgyptianFraction.html or any other source on "Egyptian Fractions"

 

[Nimz]

Heh. I guess I should've put a $\leq$ for m₃ and m₄. 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.

 

[shmoe]

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

 

[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?)

 

[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

 

[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

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?

 

[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.

 

[bomba923]

By the way, is there formula for a non-recursive function f(i,n) that ouputs the i^th element in the n^th 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 A_n is the set of elements corresponding to the n^th row

 

[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.