How many different products can be formed by multiplying $n$ numbers at most once?

$2$ proofs follow, one concerning the desired minimum number of products, the other regarding numbers which do not appear as the number of products.

Proof 1: An alternative proof via an algorithm.

Fix numbers $a_1, \ldots, a_n$ such that none are roots of unity, nor $0$. Call $C$ the set of products we've considered. Place $1$ in $C$, then for each $i$:

If $a_i \not \in C$: add $a_i$ to $C$.

Else: there exists some maximum positive integer $k$ such that $a_i^k \in C$, add $a_i \cdot a_i^k$ to $C$.

Return

The elements of $C$ are always distinct, as $a_i$ is only added if it is new, and $a_i^{k+1}$ cannot be in $C$ previously, as that would imply we've picked $k$ too small! (this also uses the fact that $a_i$ are not roots of unity nor $0$, hence $a_i^k$ are all distinct. An argument via their magnitude or angle in the complex plane suffices)

Note at the end of the algorithm, $|C| = n+1$ regardless of $a_i$ (providing they meet the base conditions). This is because we only add new elements to $C$ from either $a_i$ itself (which has not been previously considered), or $a_i$ times an element already in $C$ (which must have been formed from $a_j$ with $j < i$).

Of course one could add more elements to $C$ and get the entire desired list this way, but the above will always exist at a minimum.

Proof 2: Concerning the study of numbers that do not appear as the number of products of $n$ numbers - there are no nontrivial such values. Every value $v$ between $1$ and $2^n$ has a set of $n$ positive integers $a_i$ such that there are $v$ distinct values that can be formed by products of these $a_i$ (each used at most once). I'll use the notation $a(m,k,i)$ to denote the value of $a_i$ so that there are $m$ possible products using $k$ integers. The proof proceeds by induction.

First, the claim is easy to verify when $n=1$, as then the assignments $1$ and $2$ satisfy.

Now suppose for induction the claim is true for $n=k-1$. Note this implies that $a(m,k-1,i)$ exist and can be well defined for $m \in [1, 2^{k-1}]$. We know that all values in the interval $[1, 2^{k-1}]$ can be achieved by setting $a_k = 1$ and using $a_i = a(m, k-1, i)$ for the other values.

We consider the remaining values in $2$ categories, even and odd. We can get any even number $2m \leq 2^k$ by setting $a_i = a(m, k-1, i)$, and then picking $a_k$ to be a prime larger than any of the $a_i$ (or any number relatively prime to the others - it matters not how we pick it). Since $gcd(a_k, a_i) = 1$, it must be that $a_k \cdot p$ for any $p$ a product of the $a_i$ is new.

For any odd number $2m-1 < 2^n$ (and greater than $1$), we need only pick $a_i = a(m,k-1,i)$ and $$a_k = \max_{S \subset [k-1]} \prod_{i \in S} a_i,$$ in words: the largest number we could form from the first $k-1$ $a_i$. Note because our odd number is greater than $1$, $a_k \neq 1$. Therefore for all products $p$ $a_k \cdot p \geq a_k$, so all products that involve $a_k$ are new values, and since $a_k \cdot p = a_k \cdot p' \iff p = p'$, each of these is unique. Therefore we have $2m$ possible products ($p$ and $a_k \cdot p$), minus one as $a_k = \max_{S \subset [k-1]} \prod_{i \in S} a_i$ is already a possible product.

The case of $1$ is trivial, just set all $a_i = 1$.

Thus every number between $1$ and $2^n$ is a possible size for the set of distinct products. This can be generalized for every number between $n+1$ and $2^n$ without using $1$'s via noticing that the additional base cases $v = n+i$ can all be done using $a_i = 2$ for $i < n$, with $a_n = 2^i$, and using the same induction (which now no longer will have any $a_i$ being $1$'.

Let $\mathcal{P}:=\big\{\prod_{i\in S}\,a_i\,|\,S\subseteq\{1,2,\ldots,n\}\big\}$. We claim that, if none of the $a_i$'s is zero or a primitive root of unity, then $|\mathcal{P}|\geq n+1$. We shall instead prove a stronger statement that $|\mathcal{P}|\geq n+1$ and the equality holds if and only if there exists $a\neq 0$ such that $a_i\in\left\{a,\frac{1}{a}\right\}$ for each $i=1,2,\ldots,n$.

The proof is done by induction on $n$. The base cases $n=1$ and $n=2$ are trivial. Now suppose on the contrary that the claim $|\mathcal{P}|\geq n+1$ fails for some positive integer $n>2$. By removing $a_n$ from the list, we obtain the set $\mathcal{P}'$ of products involving only $a_1,a_2,\ldots,a_{n-1}$. By induction hypothesis, $|\mathcal{P}'|\geq n$. Since $|\mathcal{P}|<n+1$, we conclude that $|\mathcal{P}|=n$, so $\mathcal{P}=\mathcal{P}'$. By induction hypothesis, there exists $a\in\mathbb{C}\setminus\{0\}$ such that $a_i\in\left\{a,\frac{1}{a}\right\}$ for all $i=1,2,\ldots,n-1$. Thus, for some integer $m$ with $0\leq m\leq n$, we have $$\mathcal{P}'=\left\{\frac{1}{a^m},\frac{1}{a^{m-1}},\ldots,a^{n-2-j},a^{n-1-m}\right\}\,.$$ Since $a_n\mathcal{P}'\subseteq\mathcal{P}=\mathcal{P}'$, $a_n=a^k$ for some $k\in\{-m,-m+1,\ldots,n-2-m,n-1-m\}=:T$. Since $a_n$ is not a primitive root of unity, $k\neq0$.

If $k>0$, then $a_na^{n-1-m}=a^{n-1-m+k}\in\mathcal{P}'$, so $a_na^{n-1-m+k}=a^j$ for some $j\in T$. That is, $a^{n-1-m+k-j}=1$. We have $$n-1-m+k-j\geq n-m-j\geq 1\,.$$ Therefore, $a$ is a primitive root of unity, which is absurd. Thus, $|\mathcal{P}|\geq n+1$ must hold. On the other hand, if $k<0$, then $a_na^{-m}=a^l$ for some $l\in T$. That is, $a^{l+m-k}=1$. We have $$l+m-k\geq l+m+1\geq 1\,.$$ Ergo, $a$ is again a primitive root of unity, which is a contradiction.

Now, suppose that $|\mathcal{P}|=n+1$. Consider the set $\mathcal{P}'$ as before. If $\left|\mathcal{P}'\right|=n+1$, then $\mathcal{P}'=\mathcal{P}$ and $a_n\mathcal{P}'=\mathcal{P}'$. That is, $\mathcal{P}'$ is a geometric progression with common ratio $a_n$, but then $a_n^{n+1}=1$ must hold, which violates the requirement that $a_n$ not be a primitive root of unity. Thus, $\left|\mathcal{P}'\right|=n$ must hold. However, it is now an easy exercise, using the induction hypothesis, to show that there exists $a\neq 0$ such that $a_i\in\left\{a,\frac{1}{a}\right\}$ for each $i=1,2,\ldots,n$.