Re^2: OT: Finding Factor Closest To Square Root

[QM]

Sorry, I was sloppy before...

Math::Big::Factor::factors_wheel() doesn't give all factors, but the prime factorization.

For instance,

factors_wheel(1000) == (2, 2, 2, 5, 5, 5);

[Roy Johnson]

Since you've got them in ascending order, take every other prime factor and multiply. Compare that to the product of the ones you didn't choose. Whichever's closer, there ya go. That's just off the top of my head.

Let's try another way. Pretty clearly, you want roughly half the factors. You can work from the outside in, or the inside out, or do something like this: If you have N factors, take the (N*2)th root of the number. Find the factor closest to that. Divide your number by the square of the chosen factor, decrement N, and repeat until you get further from the square root instead of closer to it.

[QM]

Your first suggestion is practical, and will probably suit my needs.

Your second suggestion, well, perhaps you typoed? I just don't get it.

[talexb]

If you get a list of prime factors in ascending order, then I would take every other member of the list, multiply them together and start with that.

In your example, that would give you 20, which isn't too far from the correct result of 31.

Hmm .. Actually, an even better answer would be

• for a list with an odd number of elements, take all of the odd position numbers and multiply them together;
• for a list with an even number of elements, take the odd numbered elements from 1 to (n/2)-1, and the even numbered elements from n down to (n/2)+2, and multiply them together with the harmonic mean of the (n-1)/2 and n/2 elements.

For your example, that would be 2 * sqrt(2*5) * 5, which turns out to be exactly the correct answer, 31.622..

To try out the odd number, we'll try out 2000, which gives us a list of (2, 2, 2, 2, 5, 5, 5) and a result of 2 * 2 * 5 * 5 or 100. Hmm, a little high.

Well, that's a fascinating question, and good luck with that.

[QM]

For your example, that would be 2 * sqrt(2*5) * 5, which turns out to be exactly the correct answer, 31.622..

I don't need the exact square root, but the largest (possibly composite) integer factor less than or equal to the square root.

Cheers,

[talexb]

Needless to say, but I'll say it anyway, a fascinating problem. Exactly the kind of thing that my Dad eats for breakfast (retired actuary and all that).

After some thought, it seems clear that this is a tough nut to crack. If you start with a sorted list of factors, largest to smallest, and multiply values together, the solution is 25. If you drop the first value, you end up with 20. I can't prove it (not at 0630, anyway), but I expect there are cases where the solution is the product of the first, second and last factors.

In the end, I think the best way to find out the answer is to figure out the integer that's closest to the square root, then go backwards to find the largest number made up of the factors. Assuming you don't want to actually calculate the suqare root, the first part of that can be a straightforward binary search. The second part is where it gets interesting .. you have to find the combination of factors whose product is closest to the approximate square root value you've determined.

And that sounds an awful lot like re-starting the original problem. Ugh.

[dragonchild]

One way to do it, similar to talexb, would be (tested!)

use Math::Big::Factors;

my $val = 2000;

my @x = Math::Big::Factors::factors_wheel( $val );
print "@x\n";

my %factors;
$factors{$_}++ for @x;

use Data::Dumper;
print Dumper \%factors;

my $sqrt = 1;
while (my ($k,$v) = each %factors) {
    while ($v > 1) {
        $sqrt *= $k;
        $v -= 2;
    }

    if ($v) {
         $sqrt *= sqrt( $k );
    }
}

print "$sqrt => ", sqrt( $val ), $/;

This is going to be slower that just taking the sqrt of the value. Just to let you know ...

[QM]

This would also give me a practical answer, though it could be off quite a bit for some cases.

For instance, for N=1000, the factorization is 2**3 * 5**3. Your method gives 2**2 * 5**2 = 100, while the closest factor to the square root is 5**2 = 25 (paired with 40). I'd be happy with either 25 or 40.

[dragonchild]

My method actually gives 2**1.5 * 5 ** 1.5, which is the actual square root of 1000. Coming up with 25 or 40 is going to be ... interesting. I can do further research into the mathematics behind it, if you want. (Number Theory is a pet project of mine.)