OK, all you math types....

[rhu]

Here's a math problem I've been struggling with. Well, I've been struggling with its practical application, and I'm going to write an Excel spreadsheet to solve it by brute force, but I wonder if it would fall to an elegant algorithm.

Given a number N and two smaller numbers a and b, find x such that x ∊ [a, b] and N mod x is maximized.

(Practical application: Given 2,711 squares, each color-coded to indicate the status of one member of a sequence, arrange them in a rectangle whose width is between 70 and 90 such that there are the fewest number of unused squares in the lower right-corner. Excel tells me that the answer is width 80, which has 9 leftover squares.)

Comments

from the cs point of view

[rikchik.livejournal.com]

I don't think you can get an algebraic equation, since you can't reverse the mod operation, but at least checking every x from a to b is only O(N).

Are you trying to maximize N mod x or x - N mod x? 85 is a better answer for the first and equivalent for the second.

[rikchik.livejournal.com]

Second solution:

Factor N. If any of its factors (not just prime factors) is in [a,b], x is that factor and the number of unused squares is 0. Otherwise, factor N+1, etc. until you find a factor in the range - that factor is your x and the addition is the number of unused squares. For your case, 2720's prime factors are 2^5, 5, and 17 - 80 is 2^4 * 5 and 85 is 5*17.

Re: from the cs point of view

[rikchik.livejournal.com]

sorry, that should be "minimize x - N mod x" of course.

Re: from the cs point of view

[530nm330hz.livejournal.com]

I'm trying to minimize x-(N mod x). (If N weren't prime that could give a different answer than maximizing N mod x.) I want the fewest unused spaces in the bottom row (x-(N mod x)), or the most used spaces (N mod x).

I know that in general mod is not reversable, but sometimes for specific problems there are good approximations.

Or there might be an approach that takes N mod 2, N mod 3, and N mod 5 and uses that to reduce or at least prioritize the search space.

Re: from the cs point of view

[530nm330hz.livejournal.com]

Yeah, but factoring N, N+1, etc. is probably at least as expensive as simply modding N by each of [a..b]. Looks like brute force was the right way to go.

Re: from the cs point of view

[rikchik.livejournal.com]

This is the less efficient but possibly more elegant way to do it - think of it as the steampunk solution. (Isn't prime factorization the mathematical equivalent of brass gears?)

[ken_r]

Hmm... if N/a1=q1, and N/(a1+1)=q1 also (integer division rounding down), then the remainder N%(a1+1) will have to be smaller than N%a1. You can't get a bigger remainder for increasing divisors until you get one that produces a smaller quotient, that is, where N/a2<q1. Figure out where a2 is, and you can skip over the possible divisors in between.

I guess, looking at it a different way, you could try floor(N/b) through ceil(N/a) as possible quotients, work back to compute the subrange of [a,b] that would produce each quotient, and the smallest number in each subrange would produce the largest remainder. I don't know if that helps or hurts; I think if a>sqrt(N) the new range is probably smaller than [a,b].

Re: from the cs point of view

[cnoocy]

If N mod (yz) is a function of N mod y and N mod z (which seems likely from my quick gut check then you might find an algorithm that only finds N mod x for every prime x and power thereof under b.

[captaino.livejournal.com]

This reduces the number of divisions needed to one:

p = N % b;
q = N / b; (integer division rounding down)
for (c=b-1; c >=a; c--)
{
pnew = ((q + p) % c);
if (pnew < p) q++;
p = pnew;
}

By the way, 85 rows also yields a last row with only 9 unfilled entries.

[captaino.livejournal.com]

Where brute force is impractical, it's possible that Fourier transforms could yield a near-optimal answer. I'd need to get paid to figure out details, though :-).