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

Math geniuses: Design a function that gives this output

  1. Dec 25, 2004 #1
    A general algorithm works too.

    Given: a positive integer n
    Return: three positive integers {a,b,c} such that a*b*c=n, the variance of {a,b,c} is minimized, and a>=b>=c.

    The return might also be understood as "give the (integer) dimensions of the cubiest cuboid of volume n".

    I suspect there is only one possible return for each n, though I suppose I don't have any particular reason to guess that.

    While a brute-force style solution is obvious, a mathier solution would be more fun.

    Examples (if I'm not mistaken):
    f(1) = {1,1,1}
    f(2) = {2,1,1}
    f(3) = {3,1,1}
    f(4) = {2,2,1}
    f(5) = {5,1,1}
    f(6) = {3,2,1}
    f(7) = {7,1,1}
    f(8) = {2,2,2}
    f(9) = {3,3,1}
    f(10) = {5,2,1}
    f(11) = {11,1,1}
    f(12) = {3,2,2}
    f(13) = {13,1,1}
    f(14) = {7,2,1}
    f(15) = {5,3,1}
    f(16) = {4,2,2}
    f(17) = {17,1,1}
    f(18) = {3,3,2}
    f(19) = {19,1,1}
    f(20) = {5,2,2}

    Above, note especially f(8), f(12), f(16), f(18), and f(20).

    Any patterns noticed may be productive. A simple example is that, for a prime number p, f(p)={p,1,1}. Another: for a positive integer n, f(n^3)={n,n,n}.

    I'm not sure these results are necessarily unique.
     
  2. jcsd
  3. Dec 25, 2004 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This homework? Anyways, have you tried analyzing the mathematics of the problem yet?
     
  4. Dec 25, 2004 #3
    No, it's not homework.

    I've managed to reduce it to a problem of combinatorially grouping the prime factors of an integer, but more than that is beyond me (i.e. minimizing the difference between the factors chosen and the cube root of the number)
     
  5. Dec 25, 2004 #4
    The other angle of attack I could think of is recursive, with the base case having two cases:

    Case 1:
    Being one integer: n.

    Case 2:
    Given: a positive integer n
    Return: two positive integers {a,b} such that a*b=n, the variance of {a,b} is minimized, and a>=b.

    The return might also be understood as "give the (integer) dimensions of the squarest square of area n".

    Let a(n) = the least divisor of n greater than or equal to the square root of n
    Let b(n) = the greatest divisor of n less than or equal to the square root of n

    Then f(n) = {a(n), b(n)}

    Is there a recursive relationship?
     
  6. Dec 31, 2004 #5
    f(1) = {1,1,1}
    f(2) = {2,1,1}
    f(3) = {3,1,1}
    f(4) = {2,2,1}
    f(5) = {5,1,1}
    f(6) = {3,2,1}
    f(7) = {7,1,1}
    f(8) = {2,2,2}
    f(9) = {3,3,1}
    f(10) = {5,2,1}
    f(11) = {11,1,1}
    f(12) = {3,2,2}
    f(13) = {13,1,1}
    f(14) = {7,2,1}
    f(15) = {5,3,1}
    f(16) = {4,2,2}
    f(17) = {17,1,1}
    f(18) = {3,3,2}
    f(19) = {19,1,1}
    f(20) = {5,2,2}

    Seems to me that when given a prime number, the first of the three values returned by f is the same number.

    Also, when given a perfect square, the first of the three values returned by f is the square root.

    Go wild. :)
     
  7. Dec 31, 2004 #6
    Yep, I noted that in my post :).
     
  8. Dec 31, 2004 #7

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Is it not a case of reducing it down in to its prime factors and if the number of factors is greater than 3 then attempting to use a variation on the dustbin packing algorithm where you attempt to try and get all 3 slots as close to the cube root of the original number?

    If writing up a program to do this that is where I would at least start.
     
  9. Dec 31, 2004 #8
    I have a simple algorithm that should work, I think.

    Reduce n to its prime factors. If there are less than 3 factors, fill up to three with 1's, if there are exactly 3 factors, use those, if there are more than 3 factors, multiply the smallest two factors, continue multiplying the smallest two factors until you have only 3 factors. Use those.
     
  10. Dec 31, 2004 #9
    nevermind, it only works in some cases.
     
  11. Dec 31, 2004 #10
    okay, one more try. I think this will work. Maybe.

    Find x=n^(1/3). This gives you the side of the cube for the given volume, usually non integer. Then increase x to the first integer that is a factor of n. Then decrease x until you find another factor of n that when multiplied by the first factor you found isn't more than n. The third number will be n divided by these two factors.
     
  12. Dec 31, 2004 #11
    doesn't work either ... oh well
     
  13. Dec 31, 2004 #12

    krab

    User Avatar
    Science Advisor

    doesn't work for 64.
     
  14. Jan 1, 2005 #13
    What is the dustbin packing algorithm? Is it polynomial in nature?

    What are the best algorithms for prime factoring? Are they polynomial (guessing no here)?
     
  15. Jan 1, 2005 #14
    Even if I was wrong with how to use it, it really does seem to me that there must be some effecient method starting with the cube root.
     
  16. Jan 1, 2005 #15

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    There are a few different dustbin-packing algorithms but I don't think any ones that accurately (there are efficient ones that don’t work 100%) work are polynomial in nature. Also of course there are no known factorising algorithms that are polynomial but there are some relatively quick ones these days.

    This is really beyond me to work out anything efficient. Have you tried really trying to break the maths down like going of the definition of variance and working out the best way to minimise it?
     
  17. Aug 30, 2009 #16
    Sequence


    1244
    114448
    12818176
    205090816
    _____________

    what the following number
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Math geniuses: Design a function that gives this output
  1. Function design (Replies: 28)

  2. Dual-output Function? (Replies: 10)

Loading...