Math geniuses: Design a function that gives this output

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

 

[Hurkyl]

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

 

[Evil Robot]

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

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)

 

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

 

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

 

[Evil Robot]

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

Yep, I noted that in my post :).

 

[Zurtex]

Is it not a case of reducing it down into 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.

 

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

 

[gonzo]

nevermind, it only works in some cases.

 

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

 

[gonzo]

doesn't work either ... oh well

 

[krab]

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

Go wild. :)

doesn't work for 64.

 

[Evil Robot]

Is it not a case of reducing it down into 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 it 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.

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

 

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

 

[Zurtex]

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

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?

 

[a2m7l5]

Sequence


1244
114448
12818176
205090816
_____________
what the following number