Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Smallest 'm'

  1. May 3, 2006 #1
    ([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: May 3, 2006
  2. jcsd
  3. May 3, 2006 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. May 4, 2006 #3
    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.
     
  5. May 4, 2006 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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. May 4, 2006 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

  7. May 4, 2006 #6
    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.
     
  8. May 5, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    The denominator doesn't have to be odd. Odd denominator meant you could find an Egyptian fraction expansion with odd denominators.
     
  9. Jun 9, 2006 #8
    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: Jun 9, 2006
  10. Jun 9, 2006 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  11. Jun 15, 2006 #10
    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??

    [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: Jun 15, 2006
  12. Jun 15, 2006 #11

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  13. Jun 15, 2006 #12
    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: Jun 15, 2006
  14. Jun 19, 2006 #13

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Smallest 'm'
  1. Smallest Number (Replies: 6)

  2. The smallest prime (Replies: 13)

Loading...