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

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

[QM]

This discussion and my own (preliminary) benchmarking results have led me to rethink a few things about my real problem.

For instance, when computing F(n), we can make use of the addition formula to break n into 2 pieces:

F(n) = F(i+j) = F(i-1)*F(j) + F(i)*F(j+1)

Then:

j = k**2 = int(sqrt(n))
i = n - j
F(n) = F(i+j) = F(i+k**2)

which we can compute using the first formula above and

F(k**2) = (F(k-1)+F(k+1))*F(k*(k-1)) 
          - ((-1)**k)*F(k*(k-2))

It remains to be seen whether all of this extra work buys anything.

[BrowserUk]

If you haven't already installed Math::Pari for doing your factorisation, do so now. I knew it would be quicker than Math::Big, but you have to see for yourself how much faster it is to believe it. It's not just the C -v- Perl difference, it has a batch of extremely clever algorithms in there, and intelligently chooses the most appropriate one.

The only bug-bear I have with Math::Pari so far, is the lack of a (as far as I can see), function for flattening its two dimensional vectors. The results from factorint() come back as an AoA, where the first nested array conatins the factors, and the second contains the counts, which makes them a tad awkward to maniulate.

[hv]

The results from factorint() come back as an AoA, where the first nested array conatins the factors, and the second contains the counts, which makes them a tad awkward to manipulate.

That second arrayref would be a perfect list of counts to be handing to Algorithm::Loops::NestedLoops though. :)

The obvious alternative (used by some other packages I've tried) would be to return 2250 = [ [ 2, 1 ], [ 3, 2 ], [ 5, 3 ] ] instead of [ [ 2, 3, 5 ], [ 1, 2, 3 ] ], but in general I've found the two forms equally easy to work with for most things.

Hugo