Algorithm for listing all multiples possible by set of numbers than is less than x

Question

I'm trying to work on a sub-problem of an larger algorithm which I am really struggling on!

The Problem

If I had a array of numbers (say A), how can I efficiently list all the numbers that can be made by multiplying the numbers together (which can be used as many times as you want) and is less than another number (say x).

For example, let's say I had A = [7, 11, 13] and x was 1010, the answers would be:

 - 7 = 7
 - 11 = 11
 - 13 = 13
 - 7*7 = 49
 - 7*11 = 77
 - 7*13 = 91
 - 11*11 = 121
 - 11*13 = 143
 - 13*13 = 169
 - 7*7*7 = 343
 - 7*7*11 = 539
 - 7*7*13 = 637
 - 7*11*11 = 847
 - 7*11*13 = 1001

I tried my best not to miss any (but feel free to edit if I have)!

I can tell this is probably some type of recursion but am really struggling on this one!

Optional

A naive solution will also be nice (that's how much I'm struggling).

Running time is also optional.

UPDATE

All numbers in A are all the prime numbers (except 1, 2, 3, 5) got from the sieve of eratosthenes.

UPDATE 2

A is also sorted

UPDATE 3 All numbers in A is under the limit

UPDATE 4 The solution does NOT need to be recursion. That was just an idea I had. And Java or Pseudo code more preferable!

Answer 1

Here is my solution in C++. I use a recursive function. The principle is:

• the recursive function is given a limit, a current which is a composite and a range of primes [start, end(
• it will output all combination of powers of the primes in the given range, multiplied by the current composite

At each step, the function takes the first prime p from the range, and compute all its powers. It then multiplies current by the p as long as the product, cp is under the limit.

We use the fact the array is sorted by leaving as soon as cp is above the limit.

Due to the way we compute the numbers they won't be sorted. But it is easy to add this as a final step once you collected the numbers (in which case ou would use a back_inserter output iterator instead of an ostream_iterator, and do a sort on the collection vector)

#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

template <class It, class Out>
void f(int limit, int current, It start, It end, Out out) {

  // terminal condition                                                                                
  if(start == end) {
    if(current != 1)
      *(out++) = current;
    return;
  }

  // Output all numbers where current prime is a factor                                                
  // starts at p^0 until p^n where p^n > limit                                                         
  int p = *start;
  for(int cp = current; cp < limit; cp *= p) {
    f(limit, cp, start+1, end, out);
  }
}

int main(int argc, char* argv[]) {
  int const N = 1010;
  vector<int> primes{7, 11, 13};

  f(N, 1, begin(primes), end(primes), ostream_iterator<int>(cout, "\n"));
}

Answer 2

Here's solution on Java along with comments. It's pretty straightforward to translate it to other language.

// numbers is original numbers like {7, 11, 13}, not modified
// offset is the offset of the currently processed number (0 = first)
// limit is the maximal allowed product
// current array is the current combination, each element denotes
//   the number of times given number is used. E. g. {1, 2, 0} = 7*11*11
private static void getProducts(int[] numbers, int offset, int limit, int[] current) {
    if(offset == numbers.length) {
        // all numbers proceed: output the current combination
        int product = 1;
        StringBuilder res = new StringBuilder();
        for(int i=0; i<offset; i++) {
            for(int j = 0; j<current[i]; j++) {
                if(res.length() > 0) res.append(" * ");
                res.append(numbers[i]);
                product *= numbers[i];
            }
        }
        // instead of printing you may copy the result to some collection
        if(product != 1)
            System.out.println(" - "+res+" = "+product);
        return;
    }
    int n = numbers[offset];
    int count = 0;
    while(limit >= 1) {
        current[offset] = count;
        getProducts(numbers, offset+1, limit, current);
        count++;
        // here the main trick: we reduce limit for the subsequent recursive calls
        // note that in Java it's integer division
        limit/=n;
    }
}

// Main method to launch    
public static void getProducts(int[] numbers, int limit) {
    getProducts(numbers, 0, limit, new int[numbers.length]);
}

Usage:

public static void main(String[] args) {
    getProducts(new int[] {7, 11, 13}, 1010);
}

Output:

 - 13 = 13
 - 13 * 13 = 169
 - 11 = 11
 - 11 * 13 = 143
 - 11 * 11 = 121
 - 7 = 7
 - 7 * 13 = 91
 - 7 * 11 = 77
 - 7 * 11 * 13 = 1001
 - 7 * 11 * 11 = 847
 - 7 * 7 = 49
 - 7 * 7 * 13 = 637
 - 7 * 7 * 11 = 539
 - 7 * 7 * 7 = 343

The resulting products are sorted in different way, but I guess sorting is not a big problem.

Answer 3

I'd go with using a queue. The algorithm I have in mind would be something like the following (in pseudocode):

multiplyUntil(A, X)
{
    queue q = A.toQueue();
    result;

    while(!q.isEmpty())
    {
        element = q.pop();
        result.add(element); // only if the initial elements are guaranteed to be < X otherwise you should add other checks

        for(int i = 0; i < A.length; i++)
        {
            product = element * A[i];

            // A is sorted so if this product is >= X the following will also be >= X
            if(product >= X)
            {
                // get out of the inner cycle
                break;
            }

            q.add(product);
        }
    }

    return result;
}

Let me know if something is unclear.

P.S: Keep in mind that the result is not guaranteed to be sorted. If you want the result to be sorted you could use a heap instead of a queue or sort the result in the end of the computation.