21
\$\begingroup\$

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

\$\endgroup\$

13 Answers 13

18
\$\begingroup\$

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
$
\$\endgroup\$
  • 3
    \$\begingroup\$ Mind...blown...wow! \$\endgroup\$ – Todd Lehman Sep 23 '14 at 2:06
  • \$\begingroup\$ Wtf... i get 1 0 \$\endgroup\$ – username.ak Feb 3 '16 at 9:47
  • \$\begingroup\$ @username.ak What is your input? How are you inputting it (command-line args?). What version of bash are you running? bash --version \$\endgroup\$ – Digital Trauma Feb 3 '16 at 16:18
12
\$\begingroup\$

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.                      ";
\$\endgroup\$
  • 4
    \$\begingroup\$ Wow, that's a clever way to iterate through all subsets. \$\endgroup\$ – Martin Ender Sep 21 '14 at 21:07
9
\$\begingroup\$

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 :) )

\$\endgroup\$
  • \$\begingroup\$ Nice! Are there any limits to the number size? \$\endgroup\$ – Todd Lehman Sep 21 '14 at 20:25
  • 1
    \$\begingroup\$ @ToddLehman nope. The default numeric type is Integer, which is an unlimited integer type. There's also Int, a 32-bit integer, but that's mostly just a legacy thing. \$\endgroup\$ – John Dvorak Sep 21 '14 at 20:33
  • \$\begingroup\$ @JanDvorak in practice yes but I love the type system too much to not mention it :). another thing to notice is that because it's anonymous it matters how you use it because the monomorphism restriction may apply in some cases. \$\endgroup\$ – proud haskeller Sep 21 '14 at 20:39
8
\$\begingroup\$

Mathematica, 18 17 bytes

1##&@@@Subsets@#&

That's an anonymous function. Call it like

1##&@@@Subsets@#&[{2,3,5,7}]
\$\endgroup\$
  • \$\begingroup\$ And Martin swoops in with a beautiously short answer! \$\endgroup\$ – Todd Lehman Sep 21 '14 at 20:49
  • \$\begingroup\$ @ToddLehman Now let's wait for the J answer that beats this one. ;) \$\endgroup\$ – Martin Ender Sep 21 '14 at 20:50
  • 1
    \$\begingroup\$ If Mathematica wasn't closed source, somebody could write a golfed version. ×@@@𝒫@# should be unbeatable. \$\endgroup\$ – Dennis Sep 21 '14 at 21:15
  • \$\begingroup\$ @Dennis The Wolfram Language specification is available independently of Mathematica and I think there are one or two (incomplete) open source implementations. Creating a Unicode-aliased version of Mathematica has been suggested a few times, but I don't think it would be very well received on PPCG. ^^ \$\endgroup\$ – Martin Ender Sep 21 '14 at 21:19
  • 2
    \$\begingroup\$ @MartinBüttner Apologies for making you wait: (*/@#~2#:@i.@^#) 16 characters in J ;) \$\endgroup\$ – algorithmshark Nov 27 '14 at 5:11
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ C doesn't rigorously define the order that arguments are evaluated in. In particular, many C function calls have arguments evaluated from right to left. \$\endgroup\$ – COTO Sep 21 '14 at 23:50
  • \$\begingroup\$ From section 6.5.2.2 of ISO/IEC 9899:TC3: The order of evaluation of the function designator, the actual arguments, and subexpressions within the actual arguments is unspecified[.] So, it is up to the compiler in which order a function's arguments are evaluated. With -Wsequence-point or -Wall, GCC will complain. \$\endgroup\$ – Dennis Sep 22 '14 at 2:54
  • \$\begingroup\$ 1. You can change c-=1 to c-- or even use i=--c<<c if you don't mind UB (it seems to work with GCC). 2. Both uses of || can be replaced with ternary operators: p=i%c?p:!!printf("%d ",p) and p*=(i/c>>i%c)&1?1:atoi(v[i%c+1]) \$\endgroup\$ – Dennis Sep 22 '14 at 2:56
  • \$\begingroup\$ @Dennis Thanks for the tips! I posted just before bed so I'd just got the program running. c-=1 is such basic golfing I shouldn't have missed it, but it was a quick bug fix because I'd forgotten that there's one extra string in argv (the program name.) i=..c<<c works on GCC/cygwin, but I've left my original program as it is and moved on to a function. So I've just learned that sizeof doesn't work on arrays passed as function arguments. I've incorporated your suggestions for ternary operators into the function. I've stuck with output to stdout as I see no short way to return an array. \$\endgroup\$ – Level River St Sep 22 '14 at 22:07
  • \$\begingroup\$ Yes, arrays passed as function arguments decay to pointers. -- It is not uncommon in C to pass a pointer to the array that should contain the results as a function parameter. The question says that you can assume that the products are smaller than 2^31, so you can just pass an array of size 512. \$\endgroup\$ – Dennis Sep 22 '14 at 22:23
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Recursive solution! Cool! \$\endgroup\$ – Todd Lehman Sep 21 '14 at 20:26
  • \$\begingroup\$ I think you can drop the space after and if you write the sum the other way around? \$\endgroup\$ – mathmandan Feb 3 '16 at 18:24
  • \$\begingroup\$ @mathmandan Yup, that works, thanks. \$\endgroup\$ – xnor Feb 5 '16 at 20:31
3
\$\begingroup\$

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?)

\$\endgroup\$
2
\$\begingroup\$

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])
\$\endgroup\$
  • 1
    \$\begingroup\$ You could shave 2 bytes by making it an anonymous function (it is allowed by the question) \$\endgroup\$ – proud haskeller Sep 22 '14 at 16:53
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ */@#~2#:@i.@^# is an alternative for 14 bytes. \$\endgroup\$ – miles Jul 15 '16 at 15:18
2
\$\begingroup\$

05AB1E, 2 bytes

æP

Try it online!

Explanation

æ   # powerset
 P  # product
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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";}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.