# Math geniuses: Design a function that gives this output

1. Dec 25, 2004

### Evil Robot

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. Dec 25, 2004

### Hurkyl

Staff Emeritus
This homework? Anyways, have you tried analyzing the mathematics of the problem yet?

3. Dec 25, 2004

### Evil Robot

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)

4. Dec 25, 2004

### Evil Robot

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?

5. Dec 31, 2004

### Sartak

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. :)

6. Dec 31, 2004

### Evil Robot

Yep, I noted that in my post :).

7. Dec 31, 2004

### Zurtex

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.

8. Dec 31, 2004

### gonzo

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.

9. Dec 31, 2004

### gonzo

nevermind, it only works in some cases.

10. Dec 31, 2004

### gonzo

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.

11. Dec 31, 2004

### gonzo

doesn't work either ... oh well

12. Dec 31, 2004

### krab

doesn't work for 64.

13. Jan 1, 2005

### Evil Robot

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

14. Jan 1, 2005

### gonzo

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.

15. Jan 1, 2005

### Zurtex

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?

16. Aug 30, 2009

### a2m7l5

Sequence

1244
114448
12818176
205090816
_____________

what the following number

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook