Smallest 'm'

  • Thread starter bomba923
  • Start date
  • #1
759
0
([itex]m[/itex] may be a function of [itex]k[/itex])

[tex]\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} [/tex]
 
Last edited:

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,565
4
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
81
0
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
AKG
Science Advisor
Homework Helper
2,565
4
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 [itex]\sum 1/n_i = 1[/itex].
 
  • #6
81
0
Heh. I guess I should've put a [itex] \leq [/itex] 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
shmoe
Science Advisor
Homework Helper
1,992
1
The denominator doesn't have to be odd. Odd denominator meant you could find an Egyptian fraction expansion with odd denominators.
 
  • #8
759
0
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 [itex]\LaTeX[/itex]),
[tex]\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} } [/tex]
Where can I find a proof of this?
(Or, how might I begin a proof of this?)
 
Last edited:
  • #9
shmoe
Science Advisor
Homework Helper
1,992
1
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

[tex]\frac{1}{a}=\frac{1}{a+1}+\frac{1}{a(a+1)}[/tex]

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
759
0
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:
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??

[tex]\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} [/tex]

*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:
  • #11
shmoe
Science Advisor
Homework Helper
1,992
1
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
759
0
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:
[tex] \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} [/tex]
Where An is the set of elements corresponding to the nth row
 
Last edited:
  • #13
shmoe
Science Advisor
Homework Helper
1,992
1
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.
 

Related Threads on Smallest 'm'

  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
13
Views
3K
Replies
1
Views
1K
  • Last Post
Replies
16
Views
10K
Replies
7
Views
2K
  • Last Post
Replies
6
Views
6K
Replies
1
Views
5K
Replies
5
Views
3K
Replies
11
Views
966
Replies
2
Views
1K
Top