Combinatorial products of unique primes

Question

Statement of problem

Given a set of unique, consecutive primes (not necessarily including 2), generate the products of all combinations of first powers of these primes — e.g., no repeats — and also 1. For example, given the set { 2, 3, 5, 7 }, you produce { 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210 } because:

  1  =  1
  2  =  2
  3  =  3
  5  =  5
  6  =  2 x 3
  7  =  7
 10  =  2 x 5
 14  =  2 x 7
 15  =  3 x 5
 21  =  3 x 7
 30  =  2 x 3 x 5
 35  =  5 x 7
 42  =  2 x 3 x 7
 70  =  2 x 5 x 7
105  =  3 x 5 x 7
210  =  2 x 3 x 5 x 7

Note that if the cardinality of your input set is k, this will give you 2^k members in your output set.

Rules/Conditions

1. You can use any language. Aim for the smallest character count of source code.
2. Your solution must be either a complete program or a complete function. The function can be anonymous (if your language supports anonymous functions).
3. Your solution should be able to support products up to at least 2^31. Don't worry about detecting or handling integer overflow if you are passed numbers whose product is too great to represent. However, please state the limits of your calculations.
4. You may accept either a list or a set and produce either a list or a set. You may assume the input is sorted but you are not required to produce sorted output.

Background

When or why is this useful? One place it is very useful is in generating a table of multipliers to race in parallel in an integer factoring algorithm known as Square Forms Factorization. There, each odd multiplier you try decreases the probability of the algorithm failing (to find a factor) by approximately 50% on hard semiprimes. So with the set of generating primes { 3, 5, 7, 11 }, which produces a set of 16 trial multipliers to race in parallel, the algorithm fails approximately 2^–16 of the time on hard semiprimes. Adding 13 to the primes list produces a set of 32 trial multipliers, reducing the chance of failure to approximately 2^–32, giving a drastic improvement in outcome at no additional computational expense (because even with twice as many multipliers racing in parallel, on average it still finds the answer in the same total number of steps).

Answer 1

Pure Bash, 32 bytes

eval echo \$[{1,${1// /\}*{1,}}]

Reads input list (single space separated) passed as a command-line arg.

Three different shell expansions are used:

1. ${1// /\}*{1,} is a parameter expansion that replaces spaces in 2 3 5 7 with }*{1, to give 2}*{1,3}*{1,5}*{1,7. \$[{1, and }] are added to the start and end respectively to give \$[{1,2}*{1,3}*{1,5}*{1,7}]. The \$[ is backslash-escaped to prevent attempts to do arithmetic expansion at this stage.
2. \$[{1,2}*{1,3}*{1,5}*{1,7}] is a brace expansion. Because brace expansion typically happens before parameter expansion, we use have to useeval to force the parameter expansion to happen first. The result of the brace expansion is $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7].
3. $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7] is a list of arithmetic expansions, which are then evaluated to give the list of numbers we require.

Output:

$ ./comboprime.sh "2 3 5 7"
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210
$

Answer 2

CJam, 13 bytes

1aq~{1$f*+}/p

Reads an array (e.g., [2 3 5 7]) from STDIN. Try it online.

An anonymous function would have the same byte count:

{1a\{1$f*+}/}

Example run

$ cjam <(echo '1aq~{1$f*+}/p') <<< '[]'
[1]
$ cjam <(echo '1aq~{1$f*+}/p') <<< '[2 3 5 7]'
[1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210]

How it works

1a               " Push R := [1].              ";
  q~             " Read an array A from STDIN. ";
    {     }/     " For each a ∊ A:             ";
     1$f*+       "     R += { ra : r ∊ R }     ";
            p    " Print.                      ";

Answer 3

Haskell, 22

the solution is an anonymous function:

map product.mapM(:[1])

example usage:

*Main> map product.mapM(:[1]) $ [2,3,5]
[30,6,10,2,15,3,5,1]

explanation:
(:[1]) is a function which given a number x returns the list [x,1].
mapM(:[1]) is a function which given a list of numbers maps the function (:[1]) over them, and returns every possible way to choose an element from every list. for example, mapM(:[1]) $ [3,4] first maps the function to get [[3,1] , [4,1]]. then the possible choices are [3,4] (choosing the first number of both) [3,1] [1,4] and [1,1] so it returns [[3,4],[3,1],[1,4],[1,1]].

then map product maps over all choices and returns their products, which are the wanted output.

this function is polymorphic in its type meaning that it can operate on all types of numbers. you could input it a list of Int and the result would be a list of Int but could also be applied on a list of type Integer and return a list of Integer. this means that overflow behavior is not specified by this function but by the input's type (yay Haskell's expressive type system :) )

Answer 4

Mathematica, 18 17 bytes

1##&@@@Subsets@#&

That's an anonymous function. Call it like

1##&@@@Subsets@#&[{2,3,5,7}]

Answer 5

Update: C (function f), 92

Even as a function, this is still the longest entry here. It's the first time I've passed an array of unknown length as a function argument in C, and apparently there is no way for a C function to know the length of an array passed to it, as the argument is passed as a pointer (regardless of the syntax used). Hence a second argument is required to indicate the length.

I kept the output to stdout, because setting up an integer array and returning it would almost certainly be longer.

Thanks to Dennis for the tips.

See the function f (92 characters excluding unnecessary whitespace) in the test programs below.

Output via printf

j;

f(int c,int*x){
  int p=1,i;
  for(i=c<<c;i--;p=i%c?p:!!printf("%d ",p))p*=(i/c>>i%c)&1?1:x[i%c];
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y);
}

Output via array pointer

j,q[512];

f(int c,int*x,int*p){
    for(int i=-1;++i-(c<<c);p[i/c]*=(i/c>>i%c)&1?1:x[i%c])i%c||(p[i/c]=1);
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y,q);
  for(j=1<<d;j--;)printf("%d ",q[j]);
}

C (program),108

excluding unnecessary whitespace.

p=1,i;
main(int c,char**v){
  c-=1;
  for(i=c<<c;i--;i%c||(printf("%d ",p),p=1))(i/c>>i%c)&1||(p*=atoi(v[i%c+1]));
}

Input from commandline, output to stdout. C isn't going to win here, but maybe I will try converting to a function tomorrow.

Basically we iterate through all 1<<c combinations of primes, with each bit of i/c being associated with the presence or absence of a particular prime in the product. The "inner loop" i%c runs through the primes, multiplying them according to the value of i/c. When i%c reaches 0, the product is output, then set to 1 for the next "outer" iteration.

curiously, printf("%d ",p,p=1) does not work (it always prints a 1.) This is not the first time I have seen odd behaviour when a value is used in a printf and assigned later in the same bracket. It is possible in this case that the second comma is not being treated as an argument separator, but rather as an operator.

Usage

$ ./a 2 3 5 7
1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210

Answer 6

Python: 55 chars

f=lambda l:l and[x*l[0]for x in f(l[1:])]+f(l[1:])or[1]

Recursively generates the products by choosing to include or exclude each number in turn.

Answer 7

Haskell, 27 bytes

This is a Haskell implementation of @sudo's CJam answer as an anonymous function. It won't beat the awesome Haskell solution of @proud haskeller, but I'll drop it here anyway.

foldr((=<<)(++).map.(*))[1]

Explanation: foldr takes in a binary function, a value, and a list. Then it replaces each cons cell in the list by an application of the function, and the end of the list by the value, like this: foldr f v [a,b,c] == f a (f b (f c v)). Our value is a one-element list containing 1, and the binary function is f = (=<<)(++).map.(*). Now, f takes a number n, makes a function (n*) that multiplies by n, makes from it a function g = map(n*) that applies that function to all elements of a list, and feeds that function to (=<<)(++). Here, (++) is the concatenation function, and (=<<) is monadic bind, which in this case takes in (++) and g, and gives a function that takes in a list, applies g to a copy of it, and concatenates the two.

In short: start with [1], and for each number n in the input list, take a copy of the current list, multiply everything by n, and append it to the current list.

Answer 8

PARI/GP, 26 bytes

v->divisors(factorback(v))

Longer versions include

v->divisors(prod(i=1,#v,v[i]))

(30 bytes) and

v->divisors(fold((x,y)->x*y,v))

(31 bytes).

Note that if the input was a factorization matrix rather than a set, 18 bytes could be saved using divisors alone. But converting a set to a factorization matrix seems to take more than 18 bytes. (I can do it in 39 bytes directly as v->concat(Mat(v~),Mat(vectorv(#v,i,1))) or 24 bytes by multiplying and re-factoringv->factor(factorback(v)), can anyone do better?)

Answer 9

Sage – 36 34

Essentially, the same as Martin Büttner’s solution, if I understand it correctly. As I mentioned it in a comment, I might as well post it as an answer.

lambda A:map(prod,Combinations(A))

This is an anonymous function, which can for example be called as follows:

(lambda A:map(prod,Combinations(A)))([2,3,5,7])

Answer 10

J (20)

This turned out longer than I hoped or expected.Still: shorter than haskel!

*/@:^"1#:@i.@(2&^)@#

Usage:

    f=:*/@:^"1#:@i.@(2&^)@#
    f 2 3 5 7
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210

This works for any set of numbers, not just primes. Also, the primes can be of unlimited size, as long as the array has the postfix x: 2 3 5 7x

Answer 11

05AB1E, 2 bytes

æP

Try it online!

Explanation

æ   # powerset
 P  # product

Answer 12

R, 56 bytes

r=1;for(i in 1:length(s))r=c(r,apply(combn(s,i),2,prod))

I'm considering here that s is the set (and a list). I'm sure it can be made even shorter. I'll see.

Answer 13

PHP, 97 Bytes

<?for(;$i++<array_product($a=$_GET[a]);){$t=$i;foreach($a as$d)$t%$d?:$t/=$d;if($t<2)echo"$i\n";}