Is There a Better Algorithm for Finding the Minimum Potential Set of Integers that Could Comprise a Given Mean?

Question

I'm trying to find the inverse of the mean, or in other words find the set of positive integers between an inclusive range that equals the mean, when divided by the number of integers identified.

Given a mean or average, such as $4.3$, and a minimum value, such as $1$, and a maximum value, such as $5$, I could use the following set of assumptions to identify one possible set of integers that would result in the average:

1. Multiply the average by powers of ten until the number is whole, for example: $$ 4.3\times10=43 $$
2. Since I multiplied $4.3$ by $10$, create a list of ten integers, with a value of $5$
3. But since $5\times10 = 50$, subtract $1$ from each of seven values to have the sum of $43$

The resulting set of values is:

$$ 5, 5, 5, 4, 4, 4, 4, 4, 4, 4 $$

Checking I get:

$$ (5+5+5+4+4+4+4+4+4+4) / 10=4.3 $$

This feels cumbersome and naive to me, and I feel like there could be a better way to do this than by guessing, but every search I've tried doesn't seem to provide what I'm looking for.

Some other solutions I came up with for this are:

1. $(5+5+5+5+4+4+4+4+4+3)/10=4.3$
2. $(5+5+5+5+5+4+4+4+3+3)/10=4.3$
3. $(5+5+5+5+5+5+4+4+3+2)/10=4.3$

As an aside I can guess other answers that are close to this number, or if rounded or truncated to one decimal place would approximate $4.3$ as well, such as:

• $30/7=4.28571428571428571428$
• $26/6=4.33333333333333333333$
• $17/4=4.25$

The biggest problem I see with all of these is that they are guesses, or assumptions.

I'm trying to identify a better algorithm, if one exists.

I'm thinking this is some kind of a distribution.

Answer 1

The way you've phrased the question makes it more a question about computer programming than mathematics, so let's think about it from a programming perspective.

As you've noticed, the question reduces to "express the mean as a ratio of whole numbers s/n, and then find n numbers that sum to s, subject to certain constraints".

Let's sketch out a recursive algorithm that solves your problem. A recursive algorithm has the form:

• Is there an obvious solution? Then solve the problem, and we're done.
• Is the problem obviously unsolvable? Then fail, and we're done.
• There is no obvious solution.
• Reduce the problem to one or more smaller problems.
• Solve each of the smaller problems.
• If any is unsolvable, fail.
• We solved all the smaller problems.
• Combine the solutions of the smaller problems to solve the larger problem.

A "backtracking" algorithm modifies this basic pattern slightly: we make many attempts to solve many smaller problems, and if one of them succeeds, we succeed; if all of them fail, then we fail.

All right. What's the version of this problem that has an obvious solution? "Find zero numbers that sum to zero", well that's easy, all sequences of zero numbers sum to zero. Moreover, "find zero numbers that sum to non zero" is also easy because we know that is impossible. Let's also assume that all the numbers are positive.

So let's write up our algorithm in pseudocode:

// Find n numbers that sum to s where each is between min and max
FindSums(min, max, s, n)
  if s < 0 then fail
  if n < 0 then fail
  if s > 0 and n = 0 then fail
  if s = 0 and n = 0 then the solution is the empty sequence
  // All right, those were the easy ones.
  // The solution is not obvious, so let's break it down into a smaller
  // problem:
  let c take on values starting from min and going to max
    // c is a proposed first number in our sequence. The
    // remainder of the sequence sums to s - c, and it is of length n - 1
    // So let's find a solution to that problem:
    let tail = FindSums(min, max, s - c, n - 1)
    if that succeeded, then the solution is to append c to tail and we're done.
    if it failed, try again with a different c if there is one
  // If we get here then every attempt failed, so there is no solution.
  fail

Try that algorithm out with pencil and paper for some small examples and see if you can make any progress. It is not very efficient; can you think of ways to make this simple algorithm more efficient?

You say in your question that you are concerned that your algorithm is little better than "make a guess", but lots of algorithms in mathematics and computer programming are of the form "make a guess and then refine it in a principled way". Often the trick to getting an algorithm that performs well is to be smart about making good initial guesses, and fast at rejecting bad ones. This algorithm is poor in both regards; can you improve it?

Answer 2

Given any rational $\frac ab$ and a range of integers $[c,d]$ you want to find $b$ integers that sum to $a$. Unless $c \le \frac ab \le d$ you are not going to have any solution at all. The range of sums you can get is $[bc,bd]$. You can note that if you take all $b$ numbers to be $c$ you get a sum of $bc$. You need to add $a-bc$ to this. One way to do it is to divide $a-bc=q(d-c)+r$. Make $q$ of your numbers $d$ and make one $c+r$. The total will be $a$. This is a well defined algorithm in the cases where there is a solution.