With $N$ integers, how many different GCDs can you make by taking subsets of them? More formally:


Let $S$ be a set of non-negative integers. 


Define $G(S)$ as $\{gcd(T) : T \subseteq S \}$


Define $f(N)$ as $\max\_{|S| = N} \{|G(S)|\}$


For example:


* $f(0) = 1$
* $f(1) = 2$
* $f(2) = 4$ (e.g. $S = \{4, 6\}$, $G(S) = \{0, 2, 4, 6\}$)
* $f(3) = 8$ (e.g. $S = \{12, 20, 30\}$, $G(S) = \{0, 2, 4, 6, 10, 12, 20, 30\}$)


Is it the case that $f(N) = 2^N$?



What is the maximum number of distinct GCDs you can make out of a set of integers?
Yes, it is possible for each subset to have a different gcd, giving $2^{N}$ distinct gcds.


Let $\mathcal{P}$ be the set consisting of the first $N$ odd primes and let $P$ be the product of the first $N$ odd primes. Then if $S = \lbrace \frac{2P}{q} : q\in \mathcal{P}\rbrace$, each subset $T\subset S$ has a unique gcd, (we can recover $T$ from its gcd $x$ by seeing which primes do not divide $x$. I.e., $\frac{2P}{q}\in T\Leftrightarrow q\nmid x$.)


(The factor of $2$ takes care of the weird convention that $gcd(\emptyset)=1$, otherwise the empty set and the whole set would have the same gcd.)


